Proof of Levenshtein distance

Question

In the article Levenshtein distance Wikipedia says about the proof of invariant that:

This proof fails to validate that the number placed in d[i,j] is in fact minimal; this is more difficult to show, and involves an argument by contradiction in which we assume d[i,j] is smaller than the minimum of the three, and use this to show one of the three is not minimal.

So how can I show that d[i,j] is actually minimal? (informal proof is ok)

Answer 1

There is an optimal edit sequence in which the edit operations occur in order from left to right. There are only three options for the last edit operation: insert the last character of the target string, delete the last character of the source string, or replace the last character. Everything before the last edit operation must be optimal.

See section 3.7 of this textbook.

Answer 2

I looked into this last year while teaching. The other answers, including Prof. Erickson's excellent book, feel incomplete, because they handwave a step along the lines of "there is an optimal edit sequence that proceeds left-to-right" or "we start by lining up the two words in columns vertically...."

(Even if that feels obvious, can you easily answer: does the proof generalize if we are given a different nonnegative cost for each possible insertion, deletion, and modification? I only found the answer in one of the original edit distance papers, I forget which. It does generalize if the optimal edit cost satisfies the conditions of a distance metric, as you can probably see from the following proof sketch.)

There are definitely other ways to do it, maybe more elegant ones, but this should work.

Lemma. In an optimal sequence of edits from string $X$ to $Y$, the only possible operations are the following forms:

• deletion of a character in $X$
• insertion of a character in $Y$
• modification of a character in $X$ to a different character in $Y$

Proof sketch. Given an edit sequence that contains an edit not of the above form, we can modify it to a strictly shorter (or "lower cost") sequence. For example, suppose we delete a character that was not originally in $X$. Then this character was either originally inserted at some point, or it was modified at some point. In the first case, we can remove the insertion and deletion steps entirely, and obtain an edit sequence that still transforms $X$ into $Y$, but is two steps shorter. In the second case, we can remove the previous modification step, but leave the deletion step. Now the edit sequence still transforms $X$ into $Y$, but is one step shorter. Similarly, one can check that edit sequences containing insertions or modifications not of the above form are strictly suboptimal. $\square$

Claim. Given strings $X$ and $Y$ of length $m$ and $n$, let $d[i,j]$ be the edit distance between the prefix of $X$ of length $i$ and the prefix of $Y$ of length $j$. Then for $1 \leq i \leq m$ and $1 \leq j \leq n$, $$ d[i,j] = \min\begin{cases} d[i-1,j] + 1 \\ d[i,j-1] + 1 \\ d[i-1,j-1] + \mathbb{1}[X_i \neq Y_j] \end{cases} . $$

Proof sketch. Consider an optimal edit sequence transforming $X[1:i]$ into $Y[1:j]$. Because $X_i$ and $Y_j$ are the final characters in their respective strings, the Lemma implies (with some thought) that at least one of the following must occur:

1. $X_i$ is deleted

2. $Y_j$ is inserted

3. $X_i$ becomes $Y_j$, either by being unchanged (if $X_i==Y_j$) or by being modified.

Now we observe that in any of these cases, we can make that edit the final edit in the sequence, because they are independent of all other edits in the sequence. In Case 1, the previous edits transform $X[1:i-1]$ into $Y[1:j]$, so the total length is $d[i-1,j] + 1$. Cases 2 and 3 are analogous. Since these are the only three possibilities, the optimal edit sequence is the minimum of them. $\square$

Answer 3

I'll put my two cents here. First we claim that

d[i+1,j+1] >= d[i,j]

Here we don't care when s1[j+1] == s2[i+1], but we can use a simple contradiction to prove that in this case d[i+1,j+1]=d[i][j]. Now we consider when s1[j+1] != s2[i+1]. If we want to make d[i+1,j+1] < d[i,j], by intuition, we have to make either s1[i+1] or s[j+1] match something. Best case scenario, one of them matches a floating (to be removed), and the other one will have to be removed. For example

[...ca]b

[... c ]a

added 'a' matches with floating 'a', and b is to be removed. In this case, d[i,j]=d[i+1,j+1].

Now suppose s1[i+1]!=s2[j+1] and

d[i+1,j+1] < min(d[i,j]+1,d[i+1,j]+1,d[i,j+1]+1).

d[i+1,j+1] has to be equal to d[i,j]. Using the same example,

d[i,j+1] < d[i,j]=d[i+1,j+1]

contradicts with the assumption.

Answer 4

This is my proof:

To get from string A to B we perform an optimal set of operations from left to right. There are 4 operations: EQ (keep the character), SWAP (change the character), INS (insert a character), DEL (delete a character).

Define the length of A as a, and the Length of B as b.

Define d[a,b] as the edit distance between the first a characters of A and the first b characters of B, which means the number of operations (besides EQ) required to do on A in order to get to B.

If we look at an optimal series of operations (there must be one), there are 4 options for the last operation. We don’t know the last operation, so we check all 4 options and take the best one (best means MINIMUM edit distance).

If the last operation was EQ that means that A[a]==B[b] and that the edit distance equals to d[a-1, b-1], because EQ is not considered as an “edit distance” cost.

If the last operation was SWAP that means that A[a]!=B[b] and that the edit distance equals to d[a-1, b-1] + 1.

If the operation was INS it means that edit distance is d[a, b-1] + INS(to B) If the operation was DEL it means that the edit distance is d[a-1, b] + DEL(from A)

We simply try all combinations of the 4 operations from LAST to FIRST until we find the best path. Actually it’s 3 operations every step, because we can decide if to check EQ or SWAP depending on if the current characters are equal or not. (if they are equal, no need to check SWAP operation and vice versa).

Since we try all possible operations, the recursion formula must be true.