Search This Blog

Tuesday, November 13, 2018

Levenshtein distance - a string metric for measuring the difference between two sequences

Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertion, deletion, substitution) required to change one word into the other. The phrase edit distance is often used to refer specifically to Levenshtein distance. It is named after Vladimir Levenshtein, who considered this distance in 1965.

kitten → sitten (substitution of "s" for "k")