Edit Distance

Edit Distance is a way of measuring how different two strings are, by counting the minimum number of operations needed to transform one into the other.

The most common version is Levenshtein Distance, which allows insertions, deletions and substitutions. Damerau Levenshtein distance also allows transpositions of adjacent characters.

For example, the Levenshtein distance between "kitten" and "sitting" is 3: substitute "k" for "s", substitute "e" for "i", then insert "g".