3
$\begingroup$

from Wagner–Fischer_algorithm:

I understand substitution cost needs to be adjusted, either 0 or 1:

 for j from 1 to n:
      for i from 1 to m:
          if s[i] = t[j]:
            substitutionCost := 0
          else:
            substitutionCost := 1

          d[i, j] := minimum(d[i-1, j] + 1,                   // deletion
                             d[i, j-1] + 1,                   // insertion
                             d[i-1, j-1] + substitutionCost)  // substitution

But in later proof part, it claims when s[i] == t[j], d[i, j] = d[i-1, j-1]:

If s[i] = t[j], and we can transform s[1..i-1] to t[1..j-1] in k operations, then we can do the same to s[1..i] and just leave the last character alone, giving k operations.

I don't understand, shouldn't it be d[i, j] = min(d[i-1, j-1], d[i-1, j] + 1, d[i, j-1]+1)?

It's also mentioned in edit distance wiki

enter image description here

How do you prove if the last chars are matched, d[i, j] is d[i-1, j-1]?


following the lemma here,

I can think one way to prove this is to assert minimal is not from d[i-1, j-1] when s[i] = t[j]. Then draw contradiction.

if minimal is not from d[i-1, j-1], the minimum must come from

  1. deleting last char from s, s[i].
  2. or inserting last char from t, t[j].

If we go with 1, we need to match s[0..i-1] with t[0..j].

A: if s[i-1] != t[j],

  1. insert t[j] to end of s, we are rewinding to the original state.
  2. modify s[i-1] to t[j], it's equvilent to deleting s[i-1] (+1) when matching s[i-1] with t[j-1], whose minimum is d[i-1, j-1].
  3. delete s[i-1] -> only viable way

B: if s[i-1] = t[j],

  1. no insert t[j], otherwise the previous deletion is redundant.
  2. no modification: equivalent to 2nd point in discussion A.
  3. deletion -> viable

Combine A and B, only deletion is acceptable and it's impossible to match if only deletion is performed on s.

Do you guys think this proof is correct?

$\endgroup$
2
  • $\begingroup$ Consider $s = a$ and $t = aa$. You could delete the second $a$, which would be optimal. What the equation means is that there is always an optimal solution which matches the last symbols, if they agree. $\endgroup$ – Yuval Filmus May 18 at 20:34
  • $\begingroup$ yeah, here I want to prove that choosing d[i-1][j-1] is always one of the optimal. $\endgroup$ – Izana May 20 at 18:57
0
$\begingroup$

Let's show that if $s$ and $t$ end with the same symbol, then there is always an optimal solution in which the final letters are left alone. Note that there could be other optimal solution in which this is not the case. For example, if $s = a$ and $t = aa$, then an optimal solution would be to delete the final $a$ from $t$. All we are claiming is that some optimal solution leaves these letters alone.

Instead of deleting letters from $s$, let's add them to $t$. The situation thus looks as follows: starting with $s,t$, we add some letters to both, and change some letters in $s$, so that the resulting strings $s',t'$ coincide.

If the final letters in $s',t'$ were both added, then we can improve the solution by not adding them, so we can assume that this is not the case.

If the final letter in $s'$ resulted from changing the last letter in $s$, then necessarily the last letter in $t'$ was added; we can instead not change the last letter in $s$, and add a different letter in $t'$, improving the solution, so we can assume that this is not the case.

Thus either the last letter in $s'$ is that of $s$, or the last letter of $t'$ is that of $t$, or both; in the latter case, there is nothing to prove. The two remaining cases are symmetric, so let's suppose that the last letter in $s'$ is that of $s$, say $\sigma$, while there is a suffix of $t'$, say $r\sigma$ (it must end with $\sigma$!), which was added after the last letter in $t$, which is also $\sigma$.

Instead of adding $r\sigma$ at the very end of $t'$, we add $\sigma r$ just before the final letter of $t$. In both cases this results in an identical suffix $\sigma r \sigma$, so we have converted the given solution to a solution with identical cost in which the final letters of $s,t$ are left untouched.


Finally, let me comment that the original paper doesn't seem to make this optimization.

$\endgroup$
7
  • $\begingroup$ > The situation thus looks as follows: starting with 𝑠,𝑡, we add some letters to both. This is against the lemma? $\endgroup$ – Izana May 20 at 19:02
  • $\begingroup$ Instead of deleting a character from $s$, you can add it to $t$. It's completely equivalent. $\endgroup$ – Yuval Filmus May 20 at 19:05
  • $\begingroup$ right! It would be nice if you state it there. $\endgroup$ – Izana May 20 at 19:11
  • $\begingroup$ > If the final letter in 𝑠′ resulted from changing the last letter in 𝑠, then necessarily the last letter in 𝑡′ was added; -> the last letter of t' can still be the original one. $\endgroup$ – Izana May 20 at 19:12
  • $\begingroup$ I wrote "Instead of deleting letters from 𝑠, let's add them to 𝑡." $\endgroup$ – Yuval Filmus May 20 at 19:12

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.