<p>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.</p>

<p>See section 3.7 of <a href="http://algorithms.wtf" rel="nofollow noreferrer">this textbook</a>.</p>

CC BY-SA 4.0
2019-09-03T14:21:33.197Z
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).
John Smith Optional
CC BY-SA 4.0
2019-09-03T18:01:01.460Z
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.
Jeffε
CC BY-SA 4.0
2021-01-09T13:36:47.423Z
can you send a link directly to the proof?
Nathan G
CC BY-SA 4.0
2012-02-26T15:48:07.653Z
2019-09-03T17:59:49.970Z
2019-09-03T17:59:49.970Z
Jeffε
<p>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 &quot;there is an optimal edit sequence that proceeds left-to-right&quot; or &quot;we start by lining up the two words in columns vertically....&quot;</p>
<p>(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.)</p>
<p>There are definitely other ways to do it, maybe more elegant ones, but this should work.</p>
<p><strong>Lemma.</strong> In an optimal sequence of edits from string <span class="math-container">$X$</span> to <span class="math-container">$Y$</span>, the only possible operations are the following forms:</p>
<ul>
<li>deletion of a character in <span class="math-container">$X$</span></li>
<li>insertion of a character in <span class="math-container">$Y$</span></li>
<li>modification of a character in <span class="math-container">$X$</span> to a different character in <span class="math-container">$Y$</span></li>
</ul>
<p><em>Proof sketch.</em> Given an edit sequence that contains an edit not of the above form, we can modify it to a strictly shorter (or &quot;lower cost&quot;) sequence. For example, suppose we delete a character that was not originally in <span class="math-container">$X$</span>. 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 <span class="math-container">$X$</span> into <span class="math-container">$Y$</span>, 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 <span class="math-container">$X$</span> into <span class="math-container">$Y$</span>, but is one step shorter. Similarly, one can check that edit sequences containing insertions or modifications not of the above form are strictly suboptimal. <span class="math-container">$\square$</span></p>
<p><strong>Claim.</strong> Given strings <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> of length <span class="math-container">$m$</span> and <span class="math-container">$n$</span>, let <span class="math-container">$d[i,j]$</span> be the edit distance between the prefix of <span class="math-container">$X$</span> of length <span class="math-container">$i$</span> and the prefix of <span class="math-container">$Y$</span> of length <span class="math-container">$j$</span>. Then for <span class="math-container">$1 \leq i \leq m$</span> and <span class="math-container">$1 \leq j \leq n$</span>,
<span class="math-container">$$ 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} . $$</span></p>
<p><em>Proof sketch.</em> Consider an optimal edit sequence transforming <span class="math-container">$X[1:i]$</span> into <span class="math-container">$Y[1:j]$</span>. Because <span class="math-container">$X_i$</span> and <span class="math-container">$Y_j$</span> are the final characters in their respective strings, the <strong>Lemma</strong> implies (with some thought) that at least one of the following must occur:</p>
<ol>
<li><p><span class="math-container">$X_i$</span> is deleted</p>
</li>
<li><p><span class="math-container">$Y_j$</span> is inserted</p>
</li>
<li><p><span class="math-container">$X_i$</span> becomes <span class="math-container">$Y_j$</span>, either by being unchanged (if <span class="math-container">$X_i==Y_j$</span>) or by being modified.</p>
</li>
</ol>
<p>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 <span class="math-container">$X[1:i-1]$</span> into <span class="math-container">$Y[1:j]$</span>, so the total length is <span class="math-container">$d[i-1,j] + 1$</span>. Cases 2 and 3 are analogous. Since these are the only three possibilities, the optimal edit sequence is the minimum of them. <span class="math-container">$\square$</span></p>

CC BY-SA 4.0
2021-05-18T02:51:46.017Z
how do you prove that when X_i = Y_j, the optimal of d[i, j] is d[i-1, j-1]? See link here https://en.wikipedia.org/wiki/Edit_distance
Izana
CC BY-SA 4.0
2021-05-19T16:07:00.820Z
@Izana I think like this: The Lemma implies that if $X_i = Y_j$, nothing else happens to $X_i$ or to $Y_j$. Therefore, the other edits transform the rest of $X$ into the rest of $Y$. By definition $d[i-1][i-j]$ is the best way to do so.
usul
CC BY-SA 4.0
2021-05-19T17:44:45.417Z
yeah, but the lemma doesn't stop you from deleting or inserting. I referenced your answer: https://cs.stackexchange.com/questions/140466/edit-distance-proof-when-last-chars-of-2-strings-are-the-same. Feel free to post your thoughts there!
Izana
CC BY-SA 4.0
2021-05-21T14:53:00.980Z
@Izana, oh, I see. I didn't claim in this answer that, when $X_i=Y_j$, the third option achieves the minimum. It is true though.
usul
CC BY-SA 4.0
2023-02-06T06:29:19.353Z
I just tried. It is actually very complicated to prove the lemma you provided, although intuitively it definitely holds. A lot of lemmas are needed to prove the lemma rigorously...
Ziqi Fan
CC BY-SA 4.0
2021-01-11T01:23:10.823Z
2021-01-11T01:23:10.823Z
usul
<p>I'll put my two cents here. First we claim that</p>
<blockquote>
<p>d[i+1,j+1] &gt;= d[i,j]</p>
</blockquote>
<p>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] &lt; 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</p>
<blockquote>
<p>[...ca]b</p>
<p>[... c ]a</p>
</blockquote>
<p>added 'a' matches with floating 'a', and b is to be removed. In this case, d[i,j]=d[i+1,j+1].</p>
<p>Now suppose s1[i+1]!=s2[j+1] and</p>
<blockquote>
<p>d[i+1,j+1] &lt; min(d[i,j]+1,d[i+1,j]+1,d[i,j+1]+1).</p>
</blockquote>
<p>d[i+1,j+1] has to be equal to d[i,j]. Using the same example,</p>
<blockquote>
<p>d[i,j+1] &lt; d[i,j]=d[i+1,j+1]</p>
</blockquote>
<p>contradicts with the assumption.</p>

CC BY-SA 3.0
2017-04-16T14:25:05.037Z
2017-04-16T14:25:05.037Z
2020-06-17T09:38:08.363Z
tartaruga_casco_mole
<p>This is my proof:</p>
<p>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).</p>
<p>Define the length of A as a, and the Length of B as b.</p>
<p>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.</p>
<p>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).</p>
<p>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.</p>
<p>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.</p>
<p>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)</p>
<p>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).</p>
<p>Since we try all possible operations, the recursion formula must be true.</p>

CC BY-SA 4.0
2021-01-09T14:12:00.067Z
2021-01-09T14:12:00.067Z
Nathan G
<p>In the article <a href="http://en.wikipedia.org/wiki/Levenshtein_distance" rel="noreferrer">Levenshtein distance</a> Wikipedia says about the proof of invariant that:</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

<ds.algorithms><proofs><edit-distance>
Proof of Levenshtein distance
Nutel
# Proof of Levenshtein distance

(Asked by: username_0 on 2012-02-26)

In the article [Levenshtein distance](http://en.wikipedia.org/wiki/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)

**Tags:** ds.algorithms, proofs, edit-distance


---

## 4 answers

### Answer by username_1 on 2012-02-26. Score: 11

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](http://algorithms.wtf).

> **Comments:**
> **username_2**: 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).  
> **username_1**: 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.  
> **username_3**: can you send a link directly to the proof?  

---

### Answer by username_4 on 2021-01-11. Score: 5

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$

> **Comments:**
> **username_5**: how do you prove that when X_i = Y_j, the optimal of d[i, j] is d[i-1, j-1]? See link here https://en.wikipedia.org/wiki/Edit_distance  
> **username_4**: @username_5 I think like this: The Lemma implies that if $X_i = Y_j$, nothing else happens to $X_i$ or to $Y_j$. Therefore, the other edits transform the rest of $X$ into the rest of $Y$. By definition $d[i-1][i-j]$ is the best way to do so.  
> **username_5**: yeah, but the lemma doesn't stop you from deleting or inserting. I referenced your answer: https://cs.stackexchange.com/questions/140466/edit-distance-proof-when-last-chars-of-2-strings-are-the-same. Feel free to post your thoughts there!  
> **username_4**: @username_5, oh, I see. I didn't claim in this answer that, when $X_i=Y_j$, the third option achieves the minimum. It is true though.  
> **username_6**: I just tried. It is actually very complicated to prove the lemma you provided, although intuitively it definitely holds. A lot of lemmas are needed to prove the lemma rigorously...  

---

### Answer by username_7 on 2017-04-16. Score: 1

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 by username_3 on 2021-01-09. Score: 0

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.


---

