(Multiple) Sequence Dynamic Programming

Edit distance

Let $A[1~..~m]$ and $B[1~..~n]$ be two strings over the same alphabet. We’d like to compare them somehow, say, to help with spell checking or for a bioinformatics application. The edit distance (or Levenshtein distance or Ulam distance or, in a more fair world, the Vintsyuk distance) between $A$ and $B$ is the minimum number of character insertions, deletions, and substitutions to change $A$ into $B$ . For example, ALGORITHM becomes ALTRUISTIC by

deleting the G,
substituting a T for the O,
inserting a U after the R,
inserting an S after the I,
substituting an I for the H, and
substituting a C for the M.

Therefore, the edit distance between ALGORITHM and ALTRUISTIC is at most 6 (although there might be a shorter sequence of edits we haven’t discovered yet).

The main goal for today is to find a dynamic programming algorithm to compute the edit distance between $A$ and $B$ .

Specification

The first stage of the process is to find a recursive backtracking solution to the problem, but where do we begin? I’ll attempt to show you a hint of the thinking process I imagine I’d undergo if I forgot this problem existed but I still had the benefit of experience. Somehow. And that means going down at least one dead end.

So, the definition of the problem tells us we’re making a sequence of edits. So maybe we need to decide an edit to do to the first input string? From there, we’d recursively work on the resulting string, suggesting the resulting string becomes the next parameter.

I’m already starting to get nervous for two reasons:

We may have just increased the length of the string by doing an insertion. Doing so is going to make the Recursion Fairy very very angry unless we can argue that some other hidden parameter has actually decreased.
There are a lot of possible strings we could create doing even a handful of arbitrary edits. It’s going to take a very very long time to solve all of these subproblems even if we use memoization.

OK, so it looks like we need a bit more organization to our approach. Something that might help with both issues is to recognize that each edit we do should serve to do something to “move on” from a character of $A$ or “move toward” a character of $B$ . To see what I mean, it might help to visualize the editing process by writing one string above the other with a gap in the first word for each insertion and a gap in the second word for each deletion.

A L G O R   I   T H M
A L   T R U I S T I C

We interpret the above words as follows: If a character appears above a copy of itself, we didn’t do anything to that character. A character above a gap means we deleted that character. A character below a gap means we inserted that character. Finally, a character above a distinct character means we did a substitution.

OK, so that already limits the kinds of strings we might have to consider, but we still need to figure out what is the correct sequence of decisions to make to generate the smaller set of strings. Well, the two (spaced out) sequence atop one another itself looks like a sequence of columns. Let’s decide what each column should be in this representation. (Taking advantage of future knowledge on how the iteration will turn out) I suggest we decide on a column to write down column-by-column in right-to-left order.

For example, if we’re partway through making our decisions, the world may look like the following:

ALGOR | I   T H M
ALTRU | I S T I C

In the representation above, we’ve decided what the final five columns should look like. In other words, we’ve decided to

substitute the M for the C
substitute the H for the I
leave the T alone
insert the S, and
leave the I alone

Now it’s time to figure out what else to do, and it looks like the specific decisions to the right of the vertical bars have no baring! We now want the smallest sequence of edits to turn ALGOR into ALTRU. That’s the edit distance of those two strings, the problem we’re trying to solve.

Also, both of those strings are prefixes of the input strings, and there aren’t too many pairs of prefixes.

Accordingly, let $\textit{Edit}(i, j)$ denote the edit distance between $A[1~..~i]$ and $B[1~..~j]$ . In particular, the edit distance between the original input strings $A$ and $B$ is $\textit{Edit}(m, n)$

Solution

Now it’s time to solve the problem recursively. This part of the process is arguably easier than picking a problem. Probably because you already half did this step in the process of picking the subproblem. And it’s kind of like preparing those induction proofs we’ve been doing since day 1. We’ll go case-by-case and see where it leads us.

Given $A[1~..~i]$ and $B[1~..~j]$ with sufficiently large $i$ and $j$ , there are three possible cases for the best rightmost column labeled below by what edit operation they represent:

Insertion: Maybe the first row of the best rightmost column is empty. We’ll have to pay $1$ for the insertion we’re doing, and then, having already put $B[j]$ into a column, we’ll want to compute the edit distance between $A[1~..~i]$ and $B[1~..~j-1]$ . In this case, the edit distance is equal to $\textit{Edit}(i, j - 1) + 1$ .
Deletion: Maybe the second row of the best rightmost column is empty, meaning we’re doing a deletion. It’s still a cost of $1$ for the operation, but now we’ll want to recursively find the edit distance of $A[1~..~i - 1]$ and $B[1~..~j]$ . The total is $\textit{Edit}(i - 1, j) + 1$ .
Substitution/No edit: Maybe both rows of the best rightmost column have a character. We’ll want the edit distance between $A[1~..~i-1]$ and $B[1~..~j-1]$ , but the cost of the “operation” depends on whether $A[i] = B[j]$ . We can write the total cost concisely as $\textit{Edit}(i - 1, j - 1) + \left[A[i] \neq B[j]\right]$ where that box at the end is equal to $1$ if the not equal position is true and equal to $0$ otherwise.¹

The actual best choice for rightmost column is the one that gives us the minimum of those three costs. Two or three of those cases aren’t possible if either $i$ or $j$ is $0$ , but those base cases are easy to solve.

$\textit{Edit}(0, j) = j$ , because we need $j$ insertions to turn the empty string into a string of length $j$ .
Similarly, $\textit{Edit}(i, 0) = i$ for the $i$ deletions we’d need. And for $\textit{Edit}(0, 0)$ … oh, that’s already taken care of by either case above. It equals $0$ as you’d hope.

We want the best of the three or fewer options, so we get the following recurrence: $\mathit{Edit}(i, j) = \begin{cases} i & \text{if $j = 0$} \\ j & \text{if $i = 0$} \\ \min \left\{ \begin{gathered} \mathit{Edit}(i, j - 1) + 1, \\ \mathit{Edit}(i - 1, j) + 1, \\ \mathit{Edit}(i - 1, j - 1) + \left[A[i] \neq B[j]\right] \end{gathered} \right\} & \text{otherwise} \end{cases}$

Whew!

We could use (a[i] != b[i]) in C or (a[i] != b[i]) as inttype in an actual strongly typed language.

Dynamic programming

We’re past the hard part, so it’s time to do memoization.

Subproblems

We hit a base case when either $i$ or $j$ is $0$ , and we pass in $i = m$ and $j = n$ as the topmost call. Therefore, we need to handle all pairs $(i, j)$ where $0 \leq i \leq m$ and $0 \leq j \leq n$ .

Running time

We can solve any one subproblem in $O(1)$ time, and there are $O(mn)$ subproblems, so our algorithm will take $O(1) \cdot O(mn) = O(mn)$ time, whatever our algorithm ends up being.

Memoization data structure

Our parameters are two integers, so let’s use a 2D array, say, $\textit{Edit}[0~..~m, 0~..~n]$ .

Dependencies

A generic entry in the array depends upon the one immediately above it, the one immediately, to the left, and the one diagonally up and left. A representation of the dependencies for Edit(i, j)

Evaluation order

It feels more “natural” to use $i$ in an outer loop, so let’s go in standard row-major order, row-by-row from top down, each row from left-to-right. A representation of the evaluation order for Edit(i, j)

If this were a homework problem, we’d have done enough for full credit. However, we’re so close to having actual pseudocode that we may as well see it.

Pseudocode

The pseudocode below is slightly different from what appears in Erickson’s Algorithms 3 to further emphasize that we can just “copy-paste” the recurrence into the nested for loops.

$\text{EditDistance}(A[1~..~m], B[1~..~n])$ :

for i \gets \text{$0$ to $m$}
- for j \gets \text{$0$ to $n$}
  - if j = 0
    - $\mathit{Edit}[i, j] \gets i$
  - else if i = 0
    - $\mathit{Edit}[i, j] \gets j$
  - else
    - $\mathit{ins} \gets \mathit{Edit}[i, j - 1] + 1$
    - $\mathit{del} \gets \mathit{Edit}[i - 1, j] + 1$
    - if A[i] = B[j]
      - $\mathit{rep} \gets \mathit{Edit}[i - 1, j - 1]$
    - else
      - $\mathit{rep} \gets \mathit{Edit}[i - 1, j - 1] + 1$
    - $\mathit{Edit}[i, j] \gets \min \{ \mathit{ins}, \mathit{del}, \mathit{rep} \}$
return $\mathit{Edit}[m, n]$

Sure enough, the doubly nested for loops lead to $O(mn)$ time.

Per the rubrics, writing the pseudocode is also fine for a homework solution instead of writing the recurrence and separately explaining evaluation order. However, the pseudocode must still be accompanied by a self-contained explanation of what each entry $\textit{Edit}[i, j]$ contains at the end (the edit distance from $A[1~..~i]$ to $B[1~..~j]$ ) along with the running time ( $O(mn)$ ). I strongly recommend going with the explicit recurrence and evaluation order route, because it is easier for us to read, and it encourages you to go through the full backtracking process.

Finding the edits

Unless we explicitly tell you otherwise, finding the value of an optimal solution is sufficient for your algorithm to get full credit. In this case, it’s enough to find the edit distance between $A$ and $B$ as opposed to the actual sequence of edits.

However, suppose for a moment that we want to know the edits themselves. To that end, let’s take a look at the memoization table after we fill it out. This table, borrowed from Erickson, appears to use $A = \text{ALTRUISTIC}$ and $B = \text{ALGORITHM}$ . The full memoization table for computing the edit distance between ALTRUISTIC and ALGORITHM

The arrows in the table show which of the three cases could have been used to compute each $\textit{Edit}[i, j]$ . A horizontal arrow indicates an insertion would have worked for the last column, a vertical arrow is a deletion, and a diagonal arrow is a substitution. The thick red diagonal arrows are the “free” substitutions between identical characters.

To find an optimal sequence of edits, we can start at position $(m, n)$ and follow arrows backwards toward $(0, 0)$ , choosing arbitrarily if there is more than one incoming arrow. The arrows we take tell us precisely what the best edits are. In this table, there are exactly three paths from $(m, n)$ backwards to $(0, 0)$ leading to these three optimal edit sequences:

A L T R U I S T I C  
A L G O R I   T H M

A L   T R U I S T I C
A L G O R   I   T H M

A L T   R U I S T I C
A L G O R   I   T H M

It’s possible to compute the edit distance in slightly faster $O(mn / \log(mn))$ time using the “Method of Four Russians”. It’s sometimes described in CS 473.

We probably can’t do much better, though. There’s a widely held conjecture from complexity theory called the Strong Exponential Time Hypothesis (SETH) about the time it takes to solve a certain NP-hard problems called $k$ -SAT. There is a reduction from $k$ -SAT to (very large instances of) edit distance that implies the following:

Theorem: Assuming SETH, for every constant $\varepsilon > 0$ , there exists no $O(mn^{1 - \varepsilon})$ time algorithm for edit distance.