0
$\begingroup$

I'm interested in creating a graphs whose vertices are strings, and whose edges represent the relation of having an edit distance of 1 under a given string metric.

An obvious approach is to make all $\frac{n^2-n}{2}$ comparisons among the $n$ vertices, giving us $O(n^2)$ time complexity.

Excluding parallelizing the comparisons, is there a better algorithm in terms of time complexity?

I'm interested in string metrics where strings of different length are allowed.

$\endgroup$
3
$\begingroup$

In the worst case any such algorithm will work $\Omega(n^2)$ because your graph can have $\Omega(n^2)$ edges.

By the way, are you interested in some particular string metric?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Now that you mention it, I'm interested in string metrics where strings of different length are allowed. Not a particular metric, however. $\endgroup$ – Galen Apr 19 at 17:20
  • $\begingroup$ I like where you're going with the worst possible case; it feels intuitively right. Can you formalize into a logical argument so I can feel assured that it is nessarily the case? $\endgroup$ – Galen Apr 20 at 7:06
  • 1
    $\begingroup$ Just assume that there are at least two strings $s_1$ and $s_2$ with edit distance equal 1 (under given metric). Then for each $n$ we can construct graph which has half of its nodes equal to $s_1$ and other half of nodes equal to $s_2$. Obviously, such graph has $\frac{n^2}{4}$ edges. $\endgroup$ – Vladislav Bezhentsev Apr 20 at 11:03
  • $\begingroup$ On the other hand, for any $n$ you can always construct a graph which contains arbitrary few vertices. So the best case complexity can be more optimistic (depending on particular metric). However, without some a priory knowledge about a metric it's highly unlikely that we can do something better than full pairwise comparison of graph vertices. $\endgroup$ – Vladislav Bezhentsev Apr 20 at 11:19
  • 1
    $\begingroup$ It should be "... a graph which contains arbitrary few EDGES." in my previous comment. $\endgroup$ – Vladislav Bezhentsev Apr 20 at 17:28
0
$\begingroup$

It's possible to use BK-Trees to speed this up. Inserting $n$ elements into the tree takes $O(n \log n)$ time. After this you can query the tree for all strings whose edit distance is exactly one away from your input. Doing this for all strings again takes $O(n^2)$ complexity, however with a very small constant factor (this page mentions only 5-8% of the tree needs to be inspected per query).

Here's a short description of how it works:

Data structure

A BK-Tree is either

  • Empty
  • A node with a root value $r$ and a set of indexed children $c_i$, each a BK-Tree (implemented using hash map, dynamic array, or similar)

A metric (important!) distance function $d(x,y)$ is used for insertion and queries.

Inserting string $s$

  • If the tree is empty, make it a new node with $s$ as the root value and no children
  • If the tree is a node with root $r$ and children $c_i$, let $k=d(r,s)$.
    • If $k=0$, skip insertion as $s$ is already at the root
    • Otherwise recursively insert $s$ into the $k$-th child tree $c_k$.

The last step makes sure that all nodes in $c_i$ have distance $i$ to the root

Querying string $s$

  • If the tree is empty, return no results
  • If the tree is a node with root $r$ and children $c_i$, let $k=d(r,s)$.
    • If $k=1$, add $r$ as a result (Note: This step is different from usual BK-Tree queries)
    • In addition, recursively query $s$ from the children $c_{d-1}$, $c_d$ and $c_{d+1}$. Return all results from those queries as well

The last step there is the magic of BK-Trees, as it doesn't need to check the other children due to the distance being metric. Here's a partial proof of why others don't need to be checked:

Let's assume there was some string $x$ which has distance one from our query, so $d(s, x)=1$, but it's in the child tree $c_{k+2}$. We know that $d(r, x)=k+2$ from the insertion procedure. This however (with the triangle inequality for metric spaces) gives

$$ k+2=d(r, x)\leq d(r, s)+d(s,x)=k+1 $$

But this is a contradiction! Similar can be done for all children with $i>k+1$ and $i<k-1$. This means that all strings in other children won't have distance one by construction, so we don't need to even check them, which saves processing time.

Edit: Another explanation: https://signal-to-noise.xyz/post/bk-tree/

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.