<p>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).</p>

CC BY-SA 3.0
2012-08-31T16:28:47.173Z
2012-08-31T16:28:47.173Z
Yuval Filmus
<p>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 href="http://dl.acm.org/citation.cfm?id=360861" rel="noreferrer">A linear space algorithm for computing maximal common subsequences.</a>  <em>Commun. ACM</em> 18(6):341–343, 1975.)</p>

<p>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:</p>

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

<p>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.</p>

<p><img src="https://i.sstatic.net/5Pjr7.png" alt="enter image description here"></p>

<p>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) &amp; \text{if $m\le 1$}\\
  O(m) &amp; \text{if $n\le 1$}\\
  O(mn) + \max_h \left( T(m/2,h) + T (m/2, n−h)\right)  &amp; \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.)</p>

CC BY-SA 3.0
2012-09-01T15:09:25.737Z
Because I missed this when Dan asked me on my qualifying exam, that's why.
Jeffε
CC BY-SA 3.0
2012-09-01T17:29:28.003Z
i remember having this as a (guided) exercise and thinking it was pretty cool
Sasho Nikolov
CC BY-SA 3.0
2012-09-01T15:08:08.063Z
2012-09-01T15:08:08.063Z
Jeffε
<p>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))$.</p>

<p>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?</p>

<cc.complexity-theory><dynamic-algorithms><edit-distance><space-time-tradeoff>
Space complexity to compute the optimal string alignment for the Levenshtein edit distance
Antoine Amarilli 'a3nm'
# Space complexity to compute the optimal string alignment for the Levenshtein edit distance

(Asked by: username_0 on 2012-08-31)

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?

**Tags:** cc.complexity-theory, dynamic-algorithms, edit-distance, space-time-tradeoff

---

## 2 answers

### Answer by username_2 on 2012-09-01. Score: 15 | Accepted answer

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.](http://dl.acm.org/citation.cfm?id=360861) *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 $im/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](https://i.sstatic.net/5Pjr7.png)

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.)

> **Comments:**
> **username_2**: Because I missed this when Dan asked me on my qualifying exam, that's why.  
> **username_3**: i remember having this as a (guided) exercise and thinking it was pretty cool  

---

### Answer by username_1 on 2012-08-31. Score: 3

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).


---

