Edit Distance

You may insert a letter, delete a letter, or substitute one letter for another, each at cost 1. The edit distance from A to B is the fewest operations that turn A into B.

KITTEN → SITTING takes 3: substitute K → S, substitute E → I, insert G at the end. The figure lines the two words up so you can see it: equal letters stacked on each other cost nothing, mismatched pairs are substitutions, and a letter facing a gap is an insertion (or a deletion in the other direction).

Every way of editing A into B is such an alignment, so the question becomes: which alignment has the fewest mismatches and gaps? Trying them all is exponential. As with LCS, the way in is to ask the question about prefixes.

Fill the (m+1) × (n+1) table row by row; the bottom right cell is the answer. For KITTEN → SITTING it is 3.

To list the operations, walk back from the corner exactly like LCS: a diagonal step with equal letters is “keep”, a diagonal step with different letters is “substitute”, a step up is “delete”, a step left is “insert”. Collect them and reverse.

Cost: O(m·n) time; for the distance alone, two rows give O(n) memory.

Variations come from changing the weights or the moves: only insert and delete gives m + n − 2·LCS (so LCS solves it); allowing swaps of neighbouring letters gives the Damerau distance; giving a substitution a different price gives sequence alignment scores used in biology. The table and the walk back never change.