Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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)
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.
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.
