Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

On Wikipedia, an implementation for the bottom-up dynamic programming scheme for the edit distance is given. It does not follow the definition completely; inner cells are computed thus:

if s[i] = t[j] then  
  d[i, j] := d[i-1, j-1]       // no operation required
else
  d[i, j] := minimum
             (
               d[i-1, j] + 1,  // a deletion
               d[i, j-1] + 1,  // an insertion
               d[i-1, j-1] + 1 // a substitution
             )
}

As you can see, the algorithm always chooses the value from the upper-left neighbour if there is a match, saving some memory accesses, ALU operations and comparisons.

However, deletion (or insertion) may result in a smaller value, thus the algorithm is locally incorrect, i.e. it breaks with the optimality criterion. But maybe the mistake does not change the end result -- it might be cancelled out.

Is this micro-optimisation valid, and why (not)?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

I don't think that the algorithm is flawed. If two strings are matched, we compare first its last two characters (and then recurse). If they are the same, we can match them to get an optimal alignment. For example, consider the strings test and testat. If you don't match the two last ts, than one of the ts remains unmatched, since otherwise your matching would look like this:

enter image description here

This is impossible, since the arrows are not allowed to "cross". The matched t induces several inserts (green boxes in the figure), as depicted on the left:

enter image description here

But then you can simply find an equally good alignment, depicted on the right. In both cases you match a t and you have two inserts.

The argument for a substitution of one of the last ts is the same. So if you substitute one of the last ts, then you can instead match the last two t, and get a better alignment (see the picture).

enter image description here

share|improve this answer
    
Ah, a top-down argument for a bottom-up problem. Nice! –  Raphael Aug 2 '12 at 8:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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