Edit distance

Problem

Input: two strings $A[\mathrm{1..}n]$ and $B[\mathrm{1..}m]$ where each index is a character

Output: how many edits can we make? An edit is considered either an insertion of a character, deletion of a character, or substitution.

Alignment

If we want to go from $A$ to $B$, an alignment tells us what characters are missing from $B$, and what are missing from $A$, and do both have. Let’s use character $\perp$ as “blank,” meaning one string doesn’t have a character that the other does.

Given an alignment, the number of edits is given by

$$\sum _{i=1}^{l}1\left\{\text{if l-th column is unequal}\right\}$$

The solution space is the set of all alignments. The objective is the cost function (number of edits) from an input alignment. The constants are the alignment of $A$ and $B$.

High-level question

What is the first column? We have three finite answers: either both $A[1]$ and $B[1]$, either $A[1]$ and $\perp$, or $\perp$ and $B[1]$.

• $(A[1],B[1])$: the subproblem is to align $A[\mathrm{2..}n],B[\mathrm{2..}m]$.
• $(A[1],\perp )$: the subproblem is to align $A[\mathrm{2..}n],B[\mathrm{1..}m]$.
• $(\perp ,B[1])$: the subproblem is to align $A[\mathrm{1..}n],B[\mathrm{2..}m]$.

$G$-function

We generalize the subproblems encountered above. We can define a function $G(i,j)$ which equals the min cost alignment of $A[i..n]$ and $B[j..m]$. Here, $i$ varies between $\mathrm{1..}n$, and $j$ varies between $\mathrm{1..}m$.

Recursively, we now have three cases to consider, because there are three possible subproblems to recurse on.

$$G(i,j)=\{\begin{array}{ll}1+G(i+1,j)& \text{if A has a letter, B doesn’t}\\ 1+G(i,j+1)& \text{if B has a letter, A doesn’t}\\ 1\left\{A[i]\ne B[i]\right\}+G(i+1,j+1)& \text{if both have a letter}\end{array}$$

Runtime analysis

There are $mn$ subproblems, and it takes $O(1)$ to compute the edit for each subproblem. So total runtime is given by $O(mn)$.