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.
Propósito
Cuantificar el grado de diferencia entre cadenas, usado para coincidencia difusa y corrección de errores.
Mecanismo
Marco general: definir el conjunto de operaciones permitidas y sus costes, y usar programación dinámica para hallar el coste total mínimo. Levenshtein permite inserción/borrado/sustitución (coste 1 cada una); Damerau-Levenshtein añade la transposición de caracteres adyacentes; Hamming solo permite sustitución.
Casos de uso
- Corrección ortográfica
- Alineación de secuencias de ADN
- Corrección de errores OCR
- Desduplicación difusa
Ejemplos
- entrada
cat → cutOutput1 (substituting a→u)Levenshtein
Errores comunes
- Confusing different edit-distance variants
- Make the operation set and costs explicit
Términos relacionados
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. GLOSARIO
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
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