7
$\begingroup$

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)

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The link is no longer valid. How would you define "operations occur from left to right" mathematically? Could you expand on why for any two strings u, v, there's always a sequence of edit operations transforming u into v that is of minimal length for this property and that happens to be "left to right" (again, I'm not sure how to define "left to right" here). $\endgroup$ – John Smith Optional Sep 3 at 14:21
  • $\begingroup$ I've updated the link. I would define "operations occur from left to right" mathematically as "first perform the leftmost operation, and then recursively preform the rest". See the recurrence in the textbook. $\endgroup$ – Jeffε Sep 3 at 18:01
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.