Levenshtein distance (Edit distance)

Min operations to convert String A to String B.

Related to Longest common subsequence (LCS)

Operations are character-level

  • Insert, Delete, replace, (transpose)

The edit distance from dof to dog is 1.

From cat to act is 2. (just 1 with transpose)

Computing Edit Distance

E(i, j) = min { E(i, j-1) + 1
              , E(i-1, j) + 1
              , E(i-1, j-1) + m
              }

where m | Pi != Tj = 1
        | otherwise = 0
logo