Edit distance

Summary

The edit distance between two strings is the least number of elementary edits needed to turn one into the other. In its most common form, the Levenshtein distance, the allowed edits are inserting, deleting or substituting one symbol. It is a metric on the set of strings, and it can be computed by dynamic programming. It is used in spelling correction and in comparing biological sequences. Restricting the edits gives other distances, such as the Hamming distance, which allows only substitutions.