The Levenshtein Algorithm
The Levenshtein distance is a string metric for measuring difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other. It is named after Vladimir Levenshtein , who considered this distance in 1965. Levenshtein distance may also be referred to as edit distance , although it may also denote a larger family of distance metrics. It is closely related to pairwise string alignments. Definition Mathematically, the Levenshtein distance between two strings a, b (of length |a| and |b| respectively) is given by leva,b(|a|,|b|) where: Levenshtein distance between two strings where 1(ai≠bi) is the indicator function equal to 0 when ai≠bi and equal to 1 otherwise, and leva, b(i,j) is the distance between the first i characters of a and the first j characters of b. Note that the first element in th...