Levenshtein distance
Distancia de Levenshtein
- Date
- 1965 · confidence high
- Place
- Moscow, Russia
- Credited to
- Vladimir Levenshtein
- Field
- Knowledge & symbols
What was discovered
Within the theory of error-correcting codes, Levenshtein defined a metric that counts the minimum number of single-symbol insertions, deletions or substitutions needed to transform one string into another. It became the basis for dynamic-programming sequence-comparison algorithms, formulated by Wagner and Fischer in 1974.
What it led to
- Wagner-Fischer dynamic-programming algorithm (1974)
- Levenshtein automata and bit-parallel methods
- Spell-checking and DNA sequence comparison
Built on
- Theory of error-correcting codes