4
$\begingroup$

In a coding challenge an answer claimed to be able to compute the expected edit distance between two binary strings of length $n$ in $O(2^{3n/2})$ edit distance calculations by dynamic programming. A naive solution would requite $O(2^{2n})$ edit distance calculations.

The answer gives optimized code but no mathematical or algorithmic explanation. I cannot see how to achieve the claimed complexity. How is this possible?

$\endgroup$
5
+25
$\begingroup$

Heh…for the record, all I said was that the time seems to scale as approximately $\tilde O(2^{1.5n})$. If this was anything more than a conjecture based on the timing data that I included in the post, I would have said something more specific!

I’m sure you’re familiar with the usual Wagner–Fischer algorithm for Levenshtein distance, where we compute $d_{i,j} = d(a_{[0, i)}, b_{[0, j)})$ based on $a_{i-1}, b_{j-1}, d_{i-1,j-1}, d_{i-1,j}, d_{i,j-1}$. From there, my algorithm is based on two observations.

Firstly, each column $d_{*,j}$ is a function of the previous column $d_{*,j-1}$, the string $a$, and the bit $b_{j-1}$. We iterate over all strings $a$ (modulo symmetries), but instead of iterating over all strings $b$, we map each possible column $d_{*,j-1}$ to the two possible columns $d_{*,j}$, storing the collection of possible columns in a hash map with a counter for duplicates. This allows us to deduplicate some work when many different prefixes $b_{[0, j)}$ lead to the same column $d_{*,j}$.

Secondly, using a separate dynamic programming algorithm, we can precompute an upper bound $w_{i,j}$ on $d(a_{[i, n)}, b_{[j, n)})$ based only on $a$. Then, given a column $d_{*,j}$, the final distance $d_{n,n}$ can never be more than $m = \min_i (d_{i,j} + w_{i,j})$, so we can replace each $d_{i,j}$ with $\min \{d_{i,j}, m - |i - j|\}$ without affecting the final result. This lets us recognize more columns as duplicates and deduplicate more work.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Combining identical columns is a neat idea -- how much computation does it save? E.g., what are the values of nDistinctColsAtPos[i] / 2^i? $\endgroup$ – j_random_hacker Feb 3 at 20:46
2
$\begingroup$

I didn't try reading the source code there, but here is one way to achieve $O(2^{3n/2})$ edit distance computations (but NOT $O^*(2^{3n/2})$ time overall).

Let's define $D(a, b)$ as the Levenshtein edit distance between two strings $a$ and $b$ -- that is, the minimum number of single-character insertions, deletions or substitutions required to turn one into the other. Let $a = cd$. Then there is some $e$ and $f$ such that $b = ef$ and $D(a, b) = D(c, e) + D(d, f)$. That is, regardless of how we split $a$ into two parts, there is a way to split $b$ into two parts so that the edit distances of corresponding pairs sum to the original edit distance. Moreover, of all the ways of splitting $b$ into $e$ and $f$, the one(s) that produce a minimum total value for $D(c, e) + D(d, f)$ are the one(s) that give you the true value of $D(a, b)$. (You can always get an alignment of $a$ to $b$ by placing the alignment of $c$ to $e$ next to the alignment of $d$ to $f$, so clearly no partition can result in a distance lower than $D(a, b)$ -- that would imply an alignment of $a$ to $b$ with lower distance than the lowest possible distance.)

Assuming $n$ is even, it's enough to precompute a table $T(x, y)$ that gives the edit distance for every pair of binary strings $(x, y)$ in which $|x| = n/2$ and $|y| \le n$. (Note that even though we let $y$ have any length up to $n$ here, this is not so bad: there are only twice as many binary strings of length up to $n$ as there are binary strings of length exactly $n$.) We can then compute the distance between any pair of length-$n$ binary strings $(a, b)$ in $O(n)$ time as follows:

$D(a, b) = \min_i(T(a[1 \dots n/2], b[1 \dots i]) + T(a[n/2 + 1 \dots n], b[i+1 \dots n])$

I haven't thought much about the case where $n$ is odd -- in the worst case, you might need a DP matrix twice the size, one to hold the answer for all pairs of strings $(a, b)$ in which $|a|=\lfloor n/2 \rfloor$ and one for $|a|=\lceil n/2 \rceil$. But I think it can be handled with less work than that.

The approach I'm suggesting here still involves $O^*(2^{2n})$ steps, since it still considers each pair of length-$n$ strings, but cuts the number of edit distance computations down to $O^*(2^{3n/2})$. Each of these computations still takes $O(n^2)$ time. Overall it takes $O(2^{3n/2}n^2 + 2^{2n}n) = O(2^{2n}n)$ time and $O(2^{3n/2})$ space. Note that this is faster than the naive $O(2^{2n}n^2)$ algorithm by a factor of $n$ -- but due to the space usage, it's probably not usable above about $n=20$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Looking at the running times which increase by roughly 3 for each increased n, do you think this can be what they did? $\endgroup$ – fomin Jan 25 at 16:36
  • $\begingroup$ I can't tell what their code is doing. But the times they give are cumulative, so it looks to me more like a factor of 2 for each increase in $n$. $\endgroup$ – j_random_hacker Jan 25 at 17:51
  • $\begingroup$ A factor of 2 seems better than either your algorithm or $2^{3n/2}$ unless I am mistaken...? $\endgroup$ – fomin Jan 25 at 21:52
  • $\begingroup$ Yes, much better! I suggest just asking them for more information. $\endgroup$ – j_random_hacker Jan 26 at 8:05
  • $\begingroup$ They were asked in the comments but haven't replied. $\endgroup$ – fomin Jan 26 at 8:56

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.