Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Levenshtein distance
Summary
In information theory, linguistics, and computer science, the Levenshtein distance is 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 (insertions, deletions or substitutions) required to change one word into the other. It is named after the Soviet mathematician Vladimir Levenshtein, who considered this distance in 1965.
Levenshtein distance may also be referred to as edit distance, although that term may also denote a larger family of distance metrics known collectively as edit distance. It is closely related to pairwise string alignments.
The Levenshtein distance between two strings (of length and respectively) is given by where
where the of some string is a string of all but the first character of , and is the th character of the string , counting from 0.
Note that the first element in the minimum corresponds to deletion (from to ), the second to insertion and the third to replacement.
This definition corresponds directly to the naive recursive implementation.
For example, the Levenshtein distance between "kitten" and "sitting" is 3, since the following 3 edits change one into the other, and there is no way to do it with fewer than 3 edits:
kitten → sitten (substitution of "s" for "k"),
sitten → sittin (substitution of "i" for "e"),
sittin → sitting (insertion of "g" at the end).
The Levenshtein distance has several simple upper and lower bounds. These include:
It is at least the absolute value of the difference of the sizes of the two strings.
It is at most the length of the longer string.
It is zero if and only if the strings are equal.
If the strings have the same size, the Hamming distance is an upper bound on the Levenshtein distance. The Hamming distance is the number of positions at which the corresponding symbols in the two strings are different.
The Levenshtein distance between two strings is no greater than the sum of their Levenshtein distances from a third string (triangle inequality).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.