Proof of dynamic programming calculation of Levenshtein distance

Question

Let s1 and s2 are 2 arbitrary strings with lengths l1 and l2.

Levenshtein distance $lev(A, B)$ between strings $A$ and $B$ is a minimal number of insert, delete and replace that is required to perform on string A to become string B. Inserting, deleting and replacing is allowed to perform at any point of the strings (not just at the beginning or end).

Let's define a matrix $M$ with size $l1 \times l2$ such that: $$M[i][j] = lev(s1[0..i], s2[0..j])$$ s1[0..i] is a substring of s1 staring index 0 (inclusive) ending index i (exclusive).

s2[0..j] is a substring of s2 staring index 0 (inclusive) ending index j (exclusive).

Prove that $$M[i][j] = \min (M[i-1][j-1] + 1, M[i - 1][j] + 1, M[i][j-1] + 1), s1[i] \ne s2[j]$$$$M[i][j] = M[i-1][j-1], s1[i] = s2[j]$$

---

This is in fact a proof of correctness of Wagner–Fischer algorithm to compute the Levenshtein distance using dynamic programming, but it's completely not obvious to me why this is correct.

My first thought was to go with induction performing the step, but in case, say $s1[i]=s2[j]$ how is it possible to prove that every alternative path would be at least $M[i−1][j−1]$ long.

The complicated thing about the problem is that a shortest path is definitely not unique.

Answer 1

The easiest way to think about it is to view $\text{lev}(s1[0..i], s2[0..j])$ as the minimum cost of an alignment between $s1[0..i]$ and $s2[0..j]$.

For example $\texttt{AAACCCDDD}$ and $\texttt{ABBACCCDD}$ have an optimal alignment of cost 3.

$\texttt{AA-ACCCDDD}\\ \texttt{ABBACCCDD-}$

The cost of such an alignment is the minimum of:

• the cost of all alignments ending on insertion ($\texttt{-}$ on the top row, letter on the bottom row), which is $\text{lev}(s1[0..i], s2[0..j-1]) + \text{lev}(\epsilon, s2[j]) = M[i][j-1] + 1$
• the cost of all alignments ending on deletion (letter on the top row, $\texttt{-}$ on the bottom row), which is $\text{lev}(s1[0..i-1], s2[0..j]) + \text{lev}(s1[i], \epsilon) = M[i-1][j] + 1$
• the cost of all alignments ending on match/replacement (letters on both rows), which is $\text{lev}(s1[0..i-1], s2[0..j-1]) + \text{lev}(s1[i], s2[j]) = \begin{cases}M[i-1][j-1] &\text{if}\quad s1[i] = s2[j]\\ M[i-1][j-1] + 1 &\text{if}\quad s1[i] \neq s2[j] \end{cases}$

Note that when $s1[i] = s2[j]$ and the minimum cost alignment ends in a deletion (resp. insertion), we can move $s2[j]$ (resp. $s1[i]$) to the end of the alignment without increasing the cost. For example,

$\texttt{AA-ACCCDDD.....->.....AA-ACCCDDD}\\ \texttt{ABBACCCDD-............ABBACCCD-D}$

Thus in the cases $s1[i] = s2[j]$, the third option always has minimum cost and $M[i][j] = M[i-1][j-1]$.