Levenshtein distance

Edit-distance matrix for two words using substitution cost 1 and insertion/deletion cost 0.5. Because the costs are not all 1, this illustrates a weighted edit distance rather than the classical unit-cost Levenshtein distance.

In information theory, linguistics, and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences. For two strings, it is the minimum number of single-symbol edits—insertions, deletions, or substitutions—required to transform one string into the other. Each edit has unit cost in the classical definition.

The distance is named after Soviet mathematician Vladimir Levenshtein, who introduced it in 1965 in the context of error-correcting codes. Levenshtein distance is a particular form of edit distance; the latter term is also used for broader models in which the set of allowed operations or their costs differ. It is closely related to sequence alignment.