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?
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.
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$.
