Levenshtein distance
In computer science, the Levenshtein distance is a metric for measuring the amount of difference between two sequences (the edit distance).
Often used in spell checkers.
The edit distance between “kitten” and “sitting” is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits:
- kitten → sitten (substitution of ‘s’ for ‘k’)
- sitten → sittin (substitution of ‘i’ for ‘e’)
- sittin → sitting (insert ‘g’ at the end).
It can be considered a generalization of the Hamming distance
Thanks for pointer Michael Wakim, Fidus / MIT
