Distancia de Levenshtein
Levenshtein distance
- Fecha
- 1965 · fiabilidad alta
- Lugar
- Moscú, Rusia
- Autoría
- Vladimir Levenshtein
- Ámbito
- Saber y símbolos
Qué se descubrió
Levenshtein definió, dentro de la teoría de códigos correctores de errores, una métrica que cuenta el número mínimo de inserciones, borrados o sustituciones de un símbolo necesarias para transformar una cadena en otra. Se convirtió en la base de los algoritmos de comparación de secuencias en programación dinámica, formulados por Wagner y Fischer en 1974.
A qué dio paso
- Algoritmo de programación dinámica de Wagner-Fischer (1974)
- Autómatas de Levenshtein y métodos bit-paralelos
- Corrección ortográfica y comparación de secuencias de ADN
Se apoya en
- Teoría de códigos correctores de errores