12
$\begingroup$

If we are given two strings of size $n_1$ and $n_2$, the standard Levenshtein edit distance computation is by a dynamic algorithm with time complexity $O(n_1 n_2)$ and space complexity $O(n_1 n_2)$. (Some improvements can be made as a function of the edit distance $d$, but we make no assumption on $d$ being especially small.) If you are only interested in the value of the edit distance (i.e., the minimal number of edits), a well-known improvement of the usual algorithm (where you only keep the previous and current row of the alignment table) reduces the space complexity to $O(\max(n_1, n_2))$.

However, if you want to get the actual edits of an optimal edit script, is it possible to do better than $O(n_1 n_2)$ memory usage, possibly at the expense of running time?

$\endgroup$
15
$\begingroup$

There is no need for the tradeoff that Yuval suggests. The entire optimal editing sequence can be computed in $O(nm)$ time and $O(n+m)$ space, using a mixture of dynamic programming and divide-and-conquer first described by Dan Hirschberg. (A linear space algorithm for computing maximal common subsequences. Commun. ACM 18(6):341–343, 1975.)

Intuitively, Hirschberg's idea is to compute a single editing operation halfway through the optimal edit sequence, and then recursively compute the two halves of the sequence. If we think of the optimal edit sequence as a path from one corner of the memoization table to the other, we need a modified recurrence to record where this path crosses the middle row of the table. One recurrence that works is the following:

$$ Half(i,j) = \begin{cases} \infty & \text{if $i<m/2$}\\ j & \text{if $i=m/2$}\\ Half(i-1,j) & \text{if $i>m/2$ and $Edit(i,j) = Edit(i-1,j)+1$}\\ Half(i,j-1) & \text{if $i>m/2$ and $Edit(i,j) = Edit(i,j-1)+1$}\\ Half(i-1,j-1) & \text{otherwise} \end{cases} $$

The values of $Half(i,j)$ can be computed at the same time as the edit distance table $Edit(i,j)$, using $O(mn)$ time. Since each row of the memoization table depends only on the row above it, computing both $Edit(m,n)$ and $Half(m,n)$ requires only $O(m+n)$ space.

enter image description here

Finally, the optimal editing sequence transforming the input strings $A[1..m]$ into $B[1..n]$ consists of the optimal sequences transforming $A[1 .. m/2]$ into $B[1 .. Half(m, n)]$ followed by the optimal sequence transforming $A[m/2 + 1 .. m]$ into $B[Half(m, n) + 1 .. n]$. If we compute those two subsequences recursively, the overall running time obeys the following recurrence: $$ T(m,n) = \begin{cases} O(n) & \text{if $m\le 1$}\\ O(m) & \text{if $n\le 1$}\\ O(mn) + \max_h \left( T(m/2,h) + T (m/2, n−h)\right) & \text{otherwise} \end{cases} $$ It's not hard to prove that $T(m,n) = O(mn)$. Similarly, since we only require space for one dynamic-programming pass at a time, the total space bound is still $O(m+n)$. (The space for the recursion stack is negligible.)

$\endgroup$
  • 5
    $\begingroup$ Because I missed this when Dan asked me on my qualifying exam, that's why. $\endgroup$ – Jeffε Sep 1 '12 at 15:09
  • $\begingroup$ i remember having this as a (guided) exercise and thinking it was pretty cool $\endgroup$ – Sasho Nikolov Sep 1 '12 at 17:29
3
$\begingroup$

The algorithm you describe that runs in space $O(n_1 + n_2)$ actually recovers the final edit, and the state just before the final edit. So if you run this algorithm $O(n_1 + n_2)$ times, you can recover the entire edit sequence, at the expense of increasing the runtime. In general, there is a time-space trade-off which is controlled by the number of rows you retain at the time. The two extreme points of this trade-off are space $O(n_1n_2)$ and space $O(n_1+n_2)$, and between these, the product of time and space is constant (up to big O).

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