Levenshtein Distance
La distancia de Levenshtein es el número mínimo de inserciones, eliminaciones y sustituciones de un solo carácter necesarias para hacer idénticas dos cadenas.
Propósito
Mide la diferencia de edición entre cadenas; se usa para coincidencia difusa y corrección ortográfica.
Mecanismo
Programación dinámica: d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+cost), donde cost es 0 si los caracteres coinciden y 1 en caso contrario. Tiempo y espacio son O(m×n); el espacio se puede optimizar a O(min(m,n)).
Casos de uso
- Corrección ortográfica
- Alineación de secuencias de ADN
- Búsqueda difusa y deduplicación
- Procesamiento del lenguaje natural
Ejemplos
- entrada
kitten → sittingOutput3Substitute k→s, e→i, and insert g
Errores comunes
- Full O(mn) computation is too slow for long strings
- Use a BK-tree or early termination by threshold
Términos relacionados
Hamming Distance
La distancia de Hamming es el número de posiciones en las que difieren los caracteres correspondientes entre dos cadenas de igual longitud; solo se aplica a comparaciones de igual longitud. GLOSARIO
Jaro-Winkler Distance
La distancia Jaro-Winkler es un refinamiento de la distancia Jaro que pondera los prefijos comunes, haciéndola más apta para comparar cadenas cortas como nombres de persona donde el prefijo importa. GLOSARIO
Edit Distance
La distancia de edición es el mínimo número de operaciones de edición de un solo carácter (inserción, borrado, sustitución) necesarias para transformar una cadena en otra; la distancia de Levenshtein es su forma más común. GLOSARIO
Fuzzy Search
La búsqueda difusa es una técnica de búsqueda tolerante a variaciones ortográficas que empareja resultados aproximados basándose en distancia de edición, n-gramas o algoritmos fonéticos. GLOSARIO