Editar distancia

Métrica informática de similitud de cadenas

En lingüística computacional y ciencias de la computación , la distancia de edición es una métrica de cadena , es decir, una forma de cuantificar cuán diferentes son dos cadenas (por ejemplo, palabras) entre sí, que se mide 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 correcciones candidatas para una palabra mal escrita seleccionando palabras de un diccionario que tienen una distancia baja con la palabra en cuestión. En bioinformática , se puede utilizar para cuantificar la similitud de secuencias de ADN , que pueden verse como cadenas de las letras A, C, G y T.

Las distintas definiciones de distancia de edición utilizan distintos conjuntos de operaciones similares. Las operaciones de distancia de Levenshtein son la eliminación, inserción o sustitución de un carácter en la cadena. Al ser la métrica más común, el término distancia de Levenshtein suele usarse indistintamente con distancia de edición . ^[1]

Tipos de distancia de edición

Los distintos tipos de distancia de edición permiten distintos conjuntos de operaciones con cadenas. Por ejemplo:

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 alineamiento de secuencias de ADN como el algoritmo Smith-Waterman , que hacen que el costo de una operación dependa de dónde se aplica.

Definición formal y propiedades

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 operaciones de edición de peso mínimo que transforma 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 , entonces al insertar el símbolo x se obtiene u x v . Esto también se puede representar como ε→ x , utilizando ε para indicar 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 a u y v ( x → y ).

En la definición original de Levenshtein, cada una de estas operaciones tiene un costo unitario (excepto que la sustitución de un carácter por sí mismo tiene un costo cero), por lo que la distancia de Levenshtein es igual al número mínimo de operaciones requeridas para transformar a en b . Una definición más general asocia las funciones de peso 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 de Damerau–Levenshtein cuenta como una edición única un error común: la transposición de dos caracteres adyacentes, formalmente caracterizado 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 únicas dos operaciones de edición, ambas con un costo unitario. ^{[1] : 37} De manera similar, al permitir solo sustituciones (de nuevo con un costo unitario), se obtiene la distancia de Hamming ; esta debe restringirse a cadenas de igual longitud. ^[1] La distancia de Jaro-Winkler se puede obtener a partir de una distancia de edición donde solo se permiten transposiciones.

Ejemplo

La distancia de Levenshtein entre "gatito" y "sentado" es 3. Un script de edición mínima que transforma el primero en el segundo es:

1. k itten → s itten (sustituye "s" por "k")
2. sitt e n → sitt i n (sustituye "i" por "e")
3. sentado → sentado g (insertar "g" al final)

La distancia LCS (solo inserciones y eliminaciones) proporciona una distancia diferente y un script de edición mínimo:

1. k itten → itten (borrar "k" en 0)
2. itten → s itten (insertar "s" en 0)
3. sitt e n → sittn (elimine "e" en 4)
4. sittn → sitt i n (inserte "i" en 4)
5. sentado → sentado g (insertar "g" en 6)

por un coste total/distancia de 5 operaciones.

Propiedades

La distancia de edición con coste 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 coste positivo;
• para cada operación, existe una operación inversa con igual costo.

Con estas propiedades, los axiomas métricos se satisfacen como sigue:

d ( a , b ) = 0 si y sólo si a=b, ya que cada cadena puede transformarse trivialmente en sí misma usando exactamente cero operaciones.

d ( a , b ) > 0 cuando a ≠ b , ya que esto requeriría al menos una operación con coste distinto de cero.

d ( a , b ) = d ( b , a ) por igualdad del coste de cada operación y su inversa.

Desigualdad triangular: 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. En la literatura también se han considerado variantes de la distancia de edición que no son métricas adecuadas. ^[1]

Otras propiedades útiles de las distancias de edición de costos unitarios incluyen:

• La distancia LCS está limitada anteriormente por la suma de las longitudes de un par de cadenas. ^{[1] : 37}
• La distancia LCS es un límite superior de la distancia de Levenshtein.
• Para cuerdas de la misma longitud, la distancia de Hamming es un límite superior de la distancia de Levenshtein. ^[1]

Independientemente del costo/peso, la siguiente propiedad se cumple para todas las distancias de edición:

• Cuando a y b comparten un prefijo común, este prefijo no tiene efecto sobre la distancia. Formalmente, cuando a = uv y b = uw , entonces d ( a , b ) = d ( v , w ). ^[4] Esto permite acelerar muchos cálculos que involucran distancia de edición y 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) de a está dada por , definida por la recurrencia ^[2] ${\displaystyle a=a_{1}\ldots a_{m}}$ ${\displaystyle b=b_{1}\ldots b_{n}}$ ${\displaystyle d_{mn}}$

${\displaystyle {\begin{aligned}d_{i0}&=\sum _{k=1}^{i}w_{\mathrm {del} }(a_{k}),&&\quad {\text{for}}\;1\leq i\leq m\\d_{0j}&=\sum _{k=1}^{j}w_{\mathrm {ins} }(b_{k}),&&\quad {\text{for}}\;1\leq j\leq n\\d_{ij}&={\begin{cases}d_{i-1,j-1}&{\text{for}}\;a_{i}=b_{j}\\\min {\begin{cases}d_{i-1,j}+w_{\mathrm {del} }(a_{i})\\d_{i,j-1}+w_{\mathrm {ins} }(b_{j})\\d_{i-1,j-1}+w_{\mathrm {sub} }(a_{i},b_{j})\end{cases}}&{\text{for}}\;a_{i}\neq b_{j}\end{cases}}&&\quad {\text{for}}\;1\leq i\leq m,1\leq j\leq n.\end{aligned}}}$

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 utilizando un algoritmo de programación dinámica que comúnmente se atribuye a Wagner y Fischer , ^[7] aunque tiene un historial de invención múltiple. ^{[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 inverso de las operaciones utilizadas durante el algoritmo de programación dinámica que comienza en . ${\displaystyle d_{mn}}$

Este algoritmo tiene una complejidad temporal de Θ( m n ) donde m y n son las longitudes de las cadenas. 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 imposible leer la serie mínima de operaciones de edición. ^{[3] El} algoritmo de Hirschberg ofrece una solución de espacio lineal para este problema . ^{[8] : 634} Chowdhury, Le y Ramachandran ofrecen un marco general recursivo de divide y vencerás para resolver tales recurrencias y extraer una secuencia óptima de operaciones de manera eficiente en caché en un espacio lineal en el tamaño de la entrada. ^[9]

Algoritmos mejorados

Mejorando el algoritmo de Wagner-Fisher descrito anteriormente, Ukkonen describe varias variantes, ^[10] una de las cuales toma dos cadenas y una distancia máxima de edición s , y devuelve min( s , d ) . Esto se logra calculando y almacenando solo 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 cadenas. La complejidad espacial es O( s ² ) o O( s ) , dependiendo de si la secuencia de edición necesita ser leída. ^[3]

Las mejoras posteriores de Landau , Myers y Schmidt [1] dan como resultado un algoritmo de tiempo O( s ² + max( m , n )) . ^[11]

Para un alfabeto finito y costos de edición que son múltiplos entre sí, el algoritmo exacto más rápido conocido es el de Masek y Paterson ^[12], cuyo tiempo de ejecución en el peor de los casos es O(nm/logn).

Aplicaciones

La distancia de edición 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 se espera una pequeña cantidad de diferencias.

Existen varios algoritmos que resuelven problemas además del cálculo de la distancia entre un par de cuerdas, para resolver tipos de problemas relacionados.

• El algoritmo de Hirschberg calcula la alineación óptima de dos cadenas, donde la optimalidad se define como minimizar la distancia de edición.
• La coincidencia aproximada de cadenas se puede formular en términos de distancia de edición. El algoritmo de Ukkonen de 1985 toma una cadena p , llamada patrón, y una constante k ; luego construye un autómata de estado finito determinista que encuentra, en una cadena arbitraria s , una subcadena cuya distancia de edición a p es como máximo k ^[13] (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 una 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 lenguaje entre una cadena y un lenguaje, normalmente un lenguaje formal . En lugar de considerar la distancia de edición entre una cadena y otra, la distancia de edición del lenguaje 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 lenguaje L y cadena x sobre un alfabeto Σ , la distancia de edición del lenguaje d( L , x ) está dada por ^[14] , donde es la distancia de edición de la cadena. Cuando el lenguaje L es 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. ^[15] 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. ^[16] ${\displaystyle d(L,x)=\min _{y\in L}d(x,y)}$ ${\displaystyle d(x,y)}$

La distancia de edición del lenguaje ha encontrado muchas aplicaciones diversas, como el plegamiento de ARN, la corrección de errores y las soluciones al problema de generación de pila óptima. ^{[14] [17]}

Véase también

• Distancia de edición del gráfico
• Problema de corrección de cadena a cadena
• Métrica de cadena
• Distancia de edición de distorsión temporal

Referencias

1. Navarro, Gonzalo (1 de marzo de 2001). "Una visita guiada a la aproximación de la correspondencia de cadenas" (PDF) . ACM Computing Surveys . 33 (1): 31–88. CiteSeerX  10.1.1.452.6317 . doi :10.1145/375360.375365. S2CID  207551224 . Consultado el 19 de marzo de 2015 .
2. Daniel Jurafsky; James H. Martin. Procesamiento del habla y del lenguaje . Pearson Educación Internacional. págs. 107–111.
3. Esko Ukkonen (1983). Sobre la correspondencia aproximada de cadenas . Fundamentos de la teoría de la computación. Springer. págs. 487–495. doi :10.1007/3-540-12689-9_129.
4. 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. S2CID  207046453. 
5. Lei Chen; Raymond Ng (2004). Sobre la unión de las normas Lp y la distancia de edición (PDF) . Actas de la 30.ª Conferencia Internacional sobre Bases de Datos de Gran Tamaño (VLDB). Vol. 30. doi :10.1016/b978-012088469-8.50070-x.
6. Kukich, Karen (1992). "Técnicas para corregir automáticamente palabras en texto" (PDF) . ACM Computing Surveys . 24 (4): 377–439. doi :10.1145/146370.146380. S2CID  5431215. Archivado desde el original (PDF) el 2016-09-27 . Consultado el 2017-11-09 .
7. 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.
8. Skiena, Steven (2010). Manual de diseño de algoritmos (2.ª edición). Springer Science+Business Media . Bibcode :2008adm..book.....S. ISBN 978-1-849-96720-4.
9. Chowdhury, Rezaul; Le, Hai-Son; Ramachandran, Vijaya (julio de 2010). "Programación dinámica sin caché para bioinformática". Transacciones IEEE/ACM sobre biología computacional y bioinformática . 7 (3): 495–510. doi :10.1109/TCBB.2008.94. PMID  20671320. S2CID  2532039.
10. Ukkonen, Esko (1985). "Algoritmos para la correspondencia aproximada de cadenas" (PDF) . Información y control . 64 (1–3): 100–118. doi : 10.1016/S0019-9958(85)80046-2 .
11. Landau; Myers; Schmidt (1998). "Comparación incremental de cadenas". Revista SIAM de informática . 27 (2): 557–582. CiteSeerX 10.1.1.38.1766 . doi :10.1137/S0097539794264810. 
12. Masek, William J.; Paterson, Michael S. (febrero de 1980). "Un algoritmo más rápido para calcular distancias de edición de cadenas". Revista de Ciencias de la Computación y de Sistemas . 20 (1): 18–31. doi : 10.1016/0022-0000(80)90002-1 . ISSN  0022-0000.
13. Esko Ukkonen (1985). "Encontrar patrones aproximados en cadenas". J. Algoritmos . 6 : 132-137. doi :10.1016/0196-6774(85)90023-9.
14. Bringmann, Karl; Grandoni, Fabrizio; Saha, Barna ; Williams, Virginia Vassilevska (2016). "Algoritmos verdaderamente subcúbicos para la distancia de edición del lenguaje y el plegamiento de ARN mediante un producto min-plus de diferencia acotada rápida" (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.S2CID 17064578  .
15. Aho, A.; Peterson, T. (1972-12-01). "Un analizador sintáctico con corrección de errores de distancia mínima para lenguajes libres de contexto". Revista SIAM de Computación . 1 (4): 305–312. doi :10.1137/0201022. ISSN  0097-5397.
16. Wagner, Robert A. (1974). "Corrección de orden n para lenguajes regulares". Comunicaciones de la ACM . 17 (5): 265–268. doi : 10.1145/360980.360995 . S2CID  11063282.
17. 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. Número de identificación del sujeto  14806359.