En lingüística computacional y ciencias de la computación , la distancia de edición es una forma de cuantificar cuán diferentes son dos cadenas (por ejemplo, palabras) entre sí contando el número mínimo de operaciones necesarias para transformar una cadena en la otra. Las distancias de edición encuentran aplicaciones en el procesamiento del lenguaje natural , donde la corrección ortográfica automática puede determinar las posibles correcciones para una palabra mal escrita seleccionando palabras de un diccionario que tienen una distancia baja a la palabra en cuestión. En bioinformática , se puede utilizar para cuantificar la similitud de las secuencias de ADN , que pueden verse como cadenas de las letras A, C, G y T.
Las diferentes definiciones de una distancia de edición utilizan diferentes conjuntos de operaciones de cadena. Las operaciones de distancia de Levenshtein son la eliminación, inserción o sustitución de un carácter en la cadena. Siendo la métrica más común, el término distancia de Levenshtein a menudo se usa indistintamente con distancia de edición . [1]
Tipos de distancia de edición
Los diferentes tipos de distancia de edición permiten diferentes conjuntos de operaciones de cadena. Por ejemplo:
- La distancia de Levenshtein permite la eliminación, inserción y sustitución.
- La distancia de subsecuencia común más larga (LCS) permite solo la inserción y eliminación, no la sustitución.
- La distancia de Hamming solo permite la sustitución, por lo tanto, solo se aplica a cuerdas de la misma longitud.
- La distancia Damerau-Levenshtein permite la inserción, eliminación, sustitución y transposición de dos caracteres adyacentes.
- La distancia de Jaro solo permite la transposición .
Algunas distancias de edición se definen como una métrica parametrizable calculada con un conjunto específico de operaciones de edición permitidas, y a cada operación se le asigna un costo (posiblemente infinito). Esto se generaliza aún más mediante algoritmos de alineación de secuencias de ADN , como el algoritmo Smith-Waterman , que hacen que el costo de una operación dependa de dónde se aplique.
Definición y propiedades formales
Dadas dos cadenas a y b en un alfabeto Σ (por ejemplo, el conjunto de caracteres ASCII , el conjunto de bytes [0..255], etc.), la distancia de edición d ( a , b ) es la serie de edición de peso mínimo operaciones que transforman a en b . Uno de los conjuntos de operaciones de edición más simples es el definido por Levenshtein en 1966: [2]
- Inserción de un solo símbolo. Si a = u v , insertar el símbolo x produce u x v . Esto también se puede denotar ε → x , usando ε para denotar la cadena vacía.
- La eliminación de un solo símbolo cambia u x v a u v ( x → ε).
- La sustitución de un solo símbolo x por un símbolo y ≠ x cambia u x v por u y v ( x → y ).
En la definición original de Levenshtein, cada una de estas operaciones tiene costo unitario (salvo que la sustitución de un personaje por sí mismo tiene coste cero), por lo que la distancia Levenshtein es igual al mínimo el número de operaciones necesarias para transformar una a b . Una definición más general asocia funciones de ponderación no negativas w ins ( x ), w del ( x ) y w sub ( x , y ) con las operaciones. [2]
Se han sugerido operaciones primitivas adicionales. La distancia Damerau-Levenshtein cuenta como una sola edición, un error común: la transposición de dos caracteres adyacentes, caracterizada formalmente por una operación que cambia u x y v en u y x v . [3] [4] Para la tarea de corregir la salida de OCR , se han utilizado operaciones de fusión y división que reemplazan un solo carácter en un par de ellos o viceversa. [4]
Otras variantes de la distancia de edición se obtienen restringiendo el conjunto de operaciones. La distancia de subsecuencia común más larga (LCS) es la distancia de edición con inserción y eliminación como las dos únicas operaciones de edición, ambas a costo unitario. [1] : 37 De manera similar, al permitir solo sustituciones (nuevamente a costo unitario), se obtiene la distancia de Hamming ; esto debe restringirse a cadenas de igual longitud. [1] La distancia Jaro-Winkler se puede obtener a partir de una distancia de edición en la que solo se permiten transposiciones.
Ejemplo
La distancia de Levenshtein entre "gatito" y "sentado" es 3. Un guión de edición mínimo que transforma el primero en el segundo es:
- k itten → s itten (sustituye "s" por "k")
- sitt e n → sitt i n (sustituye "i" por "e")
- sittin → sittin g (inserte "g" al final)
La distancia LCS (solo inserciones y eliminaciones) proporciona una distancia diferente y un script de edición mínimo:
- k itten → itten (eliminar "k" en 0)
- itten → s itten (inserte "s" en 0)
- sitt e n → sittn (eliminar "e" en 4)
- sittn → sitt i n (inserte "i" en 4)
- sentado → sittin g (inserto "g" en 6)
para un costo / distancia total de 5 operaciones.
Propiedades
La distancia de edición con costo no negativo satisface los axiomas de una métrica , dando lugar a un espacio métrico de cadenas, cuando se cumplen las siguientes condiciones: [1] : 37
- Cada operación de edición tiene un costo positivo;
- para cada operación, hay una operación inversa con el mismo costo.
Con estas propiedades, los axiomas métricos se satisfacen de la siguiente manera:
- d ( a , b ) = 0 si y solo si a = b, ya que cada cadena se puede transformar trivialmente a sí misma usando exactamente cero operaciones.
- d ( a , b )> 0 cuando a ≠ b , ya que esto requeriría al menos una operación a un costo distinto de cero.
- d ( a , b ) = d ( b , a ) por igualdad del costo de cada operación y su inverso.
- Desigualdad del triángulo: d ( a , c ) ≤ d ( a , b ) + d ( b , c ). [5]
La distancia de Levenshtein y la distancia LCS con costo unitario satisfacen las condiciones anteriores y, por lo tanto, los axiomas métricos. También se han considerado en la literatura variantes de la distancia de edición que no son métricas adecuadas. [1]
Otras propiedades útiles de las distancias de edición de costo unitario incluyen:
- La distancia LCS está limitada por la suma de las longitudes de un par de cuerdas. [1] : 37
- La distancia LCS es un límite superior en la distancia de Levenshtein.
- Para cuerdas de la misma longitud, la distancia de Hamming es un límite superior en la distancia de Levenshtein. [1]
Independientemente del costo / peso, la siguiente propiedad se aplica a todas las distancias de edición:
- Cuando una y b comparten un prefijo común, este prefijo no tiene efecto en la distancia. Formalmente, cuando a = uv y b = uw , entonces d ( a , b ) = d ( v , w ). [4] Esto permite acelerar muchos cálculos relacionados con la distancia de edición y los scripts de edición, ya que los prefijos y sufijos comunes se pueden omitir en tiempo lineal.
Cálculo
El primer algoritmo para calcular la distancia mínima de edición entre un par de cadenas fue publicado por Damerau en 1964. [6]
Algoritmo común
Usando las operaciones originales de Levenshtein, la distancia de edición (no simétrica) desde a es dado por , definido por la recurrencia [2]
Este algoritmo se puede generalizar para manejar transposiciones agregando otro término en la minimización de la cláusula recursiva. [3]
La forma sencilla y recursiva de evaluar esta recurrencia requiere un tiempo exponencial . Por lo tanto, generalmente se calcula usando un algoritmo de programación dinámica que comúnmente se le atribuye a Wagner y Fischer , [7] aunque tiene un historial de múltiples inventos. [2] [3] Después de completar el algoritmo de Wagner-Fischer, se puede leer una secuencia mínima de operaciones de edición como un seguimiento de las operaciones utilizadas durante el algoritmo de programación dinámica a partir de.
Este algoritmo tiene una complejidad de tiempo de Θ ( m n ). Cuando se construye la tabla de programación dinámica completa, su complejidad espacial también es Θ ( m n ) ; esto se puede mejorar a Θ (min ( m , n )) observando que en cualquier instante, el algoritmo solo requiere dos filas (o dos columnas) en la memoria. Sin embargo, esta optimización hace que sea imposible leer la serie mínima de operaciones de edición. [3] El algoritmo de Hirschberg ofrece una solución de espacio lineal a este problema . [8] : 634
Algoritmos mejorados
Mejorando el algoritmo de Wagner-Fisher descrito anteriormente, Ukkonen describe varias variantes, [9] una de las cuales toma dos cadenas y una distancia máxima de edición s , y devuelve min ( s , d ) . Lo logra simplemente calculando y almacenando una parte de la tabla de programación dinámica alrededor de su diagonal. Este algoritmo toma tiempo O ( s × min ( m , n )) , donde m y n son las longitudes de las cuerdas. La complejidad del espacio es O ( s 2 ) u O ( s ) , dependiendo de si es necesario leer la secuencia de edición. [3]
Las mejoras adicionales de Landau , Myers y Schmidt [1] dan un algoritmo de tiempo O ( s 2 + max ( m , n )) . [10]
Aplicaciones
Editar distancia encuentra aplicaciones en biología computacional y procesamiento del lenguaje natural, por ejemplo, la corrección de errores ortográficos o de OCR, y la coincidencia aproximada de cadenas , donde el objetivo es encontrar coincidencias para cadenas cortas en muchos textos más largos, en situaciones en las que hay pocas diferencias es de esperar.
Existen varios algoritmos que resuelven problemas además del cálculo de la distancia entre un par de cadenas, para resolver tipos de problemas relacionados.
- El algoritmo de Hirschberg calcula la alineación óptima de dos cadenas, donde la optimización se define como minimizar la distancia de edición.
- Se puede formular una correspondencia aproximada de cadenas en términos de distancia de edición. El algoritmo de 1985 de Ukkonen toma una cadena p , llamada patrón, y una constante k ; luego construye un autómata determinista de estado finito que encuentra, en una cadena arbitraria s , una subcadena cuya distancia de edición ap es como máximo k [11] (cf. el algoritmo Aho-Corasick , que de manera similar construye un autómata para buscar cualquiera de varios patrones, pero sin permitir operaciones de edición). Un algoritmo similar para la coincidencia aproximada de cadenas es el algoritmo bitap , también definido en términos de distancia de edición.
- Los autómatas de Levenshtein son máquinas de estados finitos que reconocen un conjunto de cadenas dentro de la distancia de edición limitada de una cadena de referencia fija. [4]
Distancia de edición del idioma
Una generalización de la distancia de edición entre cadenas es la distancia de edición del idioma entre una cadena y un idioma, generalmente un idioma formal . En lugar de considerar la distancia de edición entre una cadena y otra, la distancia de edición del idioma es la distancia de edición mínima que se puede alcanzar entre una cadena fija y cualquier cadena tomada de un conjunto de cadenas. Más formalmente, para cualquier idioma L y cadena x sobre un alfabeto Σ , la distancia de edición del idioma d ( L , x ) viene dada por [12], dónde es la distancia de edición de la cadena. Cuando el lenguaje L está libre de contexto , hay un algoritmo de programación dinámica de tiempo cúbico propuesto por Aho y Peterson en 1972 que calcula la distancia de edición del lenguaje. [13] Para familias de gramáticas menos expresivas, como las gramáticas regulares , existen algoritmos más rápidos para calcular la distancia de edición. [14]
La distancia de edición de idiomas ha encontrado muchas aplicaciones diversas, como el plegado de ARN, la corrección de errores y las soluciones al problema de generación de pila óptima. [12] [15]
Ver también
- Distancia de edición del gráfico
- Problema de corrección de cuerda a cuerda
- Métrica de cadena
- Distancia de edición de distorsión de tiempo
Referencias
- ^ a b c d Daniel Jurafsky; James H. Martin. Procesamiento del habla y el lenguaje . Pearson Education International. págs. 107-111.
- ^ a b c d e Esko Ukkonen (1983). Sobre la coincidencia aproximada de cadenas . Fundamentos de la teoría de la computación. Saltador. págs. 487–495. doi : 10.1007 / 3-540-12689-9_129 .
- ^ a b c d Schulz, Klaus U .; Mihov, Stoyan (2002). "Corrección rápida de cadenas con autómatas de Levenshtein" . Revista Internacional de Análisis y Reconocimiento de Documentos . 5 (1): 67–85. CiteSeerX 10.1.1.16.652 . doi : 10.1007 / s10032-002-0082-8 .
- ^ Lei Chen; Raymond Ng (2004). Sobre la unión de las normas L p y la distancia de edición (PDF) . Proc. 30.a Conf. Internacional en bases de datos muy grandes (VLDB). 30 . doi : 10.1016 / b978-012088469-8.50070-x .
- ^ Kukich, Karen (1992). "Técnicas para corregir automáticamente palabras en texto" (PDF) . Encuestas de computación ACM . 24 (4): 377–439. doi : 10.1145 / 146370.146380 . Archivado desde el original (PDF) el 27 de septiembre de 2016 . Consultado el 9 de noviembre de 2017 .
- ^ R. Wagner; M. Fischer (1974). "El problema de la corrección de cuerda a cuerda". J. ACM . 21 : 168-178. doi : 10.1145 / 321796.321811 . S2CID 13381535 .
- ^ Skiena, Steven (2010). El Manual de diseño de algoritmos (2ª ed.). Springer Science + Business Media . Bibcode : 2008adm..book ..... S . ISBN 978-1-849-96720-4.
- ^ Ukkonen, Esko (1985). "Algoritmos para la coincidencia aproximada de cadenas" (PDF) . Información y control . 64 (1-3): 100-118. doi : 10.1016 / S0019-9958 (85) 80046-2 .
- ^ Landó; Myers; Schmidt (1998). "Comparación de cadenas incrementales". Revista SIAM de Computación . 27 (2): 557–582. CiteSeerX 10.1.1.38.1766 . doi : 10.1137 / S0097539794264810 .
- ^ Esko Ukkonen (1985). "Encontrar patrones aproximados en cadenas". J. Algoritmos . 6 : 132-137. doi : 10.1016 / 0196-6774 (85) 90023-9 .
- ^ a b Bringmann, Karl; Grandoni, Fabrizio; Saha, Barna; Williams, Virginia Vassilevska (2016). "Algoritmos verdaderamente subcúbicos para la distancia de edición de idiomas y el plegado de ARN a través del producto Min-Plus de diferencia rápida acotada" (PDF) . 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) . págs. 375–384. arXiv : 1707.05095 . doi : 10.1109 / focs.2016.48 . ISBN 978-1-5090-3933-3.
- ^ Aho, A .; Peterson, T. (1 de diciembre de 1972). "Un analizador de corrección de errores de distancia mínima para lenguajes sin contexto". Revista SIAM de Computación . 1 (4): 305–312. doi : 10.1137 / 0201022 . ISSN 0097-5397 .
- ^ Wagner, Robert A. (1974). "Corrección de orden-n para idiomas regulares". Comunicaciones de la ACM . 17 (5): 265–268. doi : 10.1145 / 360980.360995 . S2CID 11063282 .
- ^ Saha, B. (1 de octubre de 2014). El problema de la distancia de edición del lenguaje Dyck en tiempo casi lineal . 2014 IEEE 55th Annual Symposium on Foundations of Computer Science . págs. 611–620. doi : 10.1109 / FOCS.2014.71 . ISBN 978-1-4799-6517-5. S2CID 14806359 .