Editar distancia

En lingüística computacional e informática , la distancia de edición es una métrica de cadena , es decir, una forma de cuantificar qué tan 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 misma. otro. Editar distancias encuentra aplicaciones en el procesamiento del lenguaje natural , donde la corrección ortográfica automática puede determinar las correcciones candidatas para una palabra mal escrita seleccionando palabras de un diccionario que tienen una distancia baja con respecto a 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 letras A, C, G y T.

Diferentes definiciones de distancia de edición utilizan diferentes 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

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 (LCS) más larga solo permite la inserción y eliminación, no la sustitución.
La distancia de Hamming sólo permite sustitución, por lo tanto, sólo se aplica a cuerdas de la misma longitud.
La distancia Damerau-Levenshtein permite la inserción, eliminación, sustitución y transposición (intercambio) de dos caracteres adyacentes.
La distancia de Jaro sólo 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 de 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 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

, entonces 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

u

v

(

x

→ε).

La sustitución de un solo símbolo

x

por un símbolo

y

≠

x

cambia

u

x

v

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 personaje por sí solo tiene costo cero), por lo que la distancia de Levenshtein es igual al número mínimo de operaciones necesarias para transformar $a$ en $b$ . Una definición más general asocia 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 Damerau-Levenshtein cuenta como una edición única, un error común: la transposición de dos caracteres adyacentes, formalmente caracterizada por una operación que cambia $u$ $x$ $y$ $v$ en $u$ $y$ $x$ $v$ . ^[3]^[4] Para la tarea de corregir la salida 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 distancia de edición se obtienen restringiendo el conjunto de operaciones. La distancia de subsecuencia común (LCS) más larga es la distancia de edición con inserción y eliminación como las dos únicas operaciones de edición, ambas con costo unitario. ^[1]^{: 37} De manera similar, al permitir solo sustituciones (nuevamente al 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 donde solo se permiten transposiciones.

Ejemplo

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

k itten → s itten (sustituye "k" por "s")
sitt e n → sitt i n (sustituye "i" por "e")
sentado → sentado 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 (borrar "k" en 0)
itten → s itten (inserte "s" en 0)
sitt e n → sittn (elimine "e" en 4)
sittn → sitt i n (inserte "i" en 4)
sentado → sentado g (inserte "g" en 6)

para un costo/distancia total de 5 operaciones.

Propiedades

Editar distancia 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 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 un costo distinto de cero.

d

(

a

b

) =

d

(

b

a

) por igualdad del coste de cada operación y su inversa.

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. En la literatura también se han considerado variantes de 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 por la suma de las longitudes de un par de cuerdas. ^[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 aplica a todas las distancias de edición:

Cuando $a$ y $b$ comparten un prefijo común, este prefijo no tiene ningún 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 relacionados con la distancia de edición y los guiones de edición, ya que los prefijos y sufijos comunes se pueden omitir en tiempo lineal.

Cálculo

Damerau publicó el primer algoritmo para calcular la distancia mínima de edición entre un par de cadenas en 1964. ^[6]

Algoritmo común

Usando las operaciones originales de Levenshtein, la distancia de edición (no simétrica) desde a está dada por , definida por la recurrencia ^[2] $a=a_{1}\ldots a_{m}$ $b=b_{1}\ldots b_{n}$ $d_{mn}$

{\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 una historia de múltiples invenciones. ^[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 . $d_{mn}$

Este algoritmo tiene una complejidad temporal de Θ ( $m$ $n$ ) donde $myn$ 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 en el espacio lineal a este problema . ^[8]^{: 634} Chowdhury, Le y Ramachandran proporcionan un marco general recursivo de divide y vencerás para resolver tales recurrencias y extraer una secuencia óptima de operaciones con eficiencia de almacenamiento 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 de edición máxima $s$ , y devuelve min( $s$ , $d$ ) . Lo logra calculando y almacenando únicamente una parte de la tabla de programación dinámica alrededor de su diagonal. Este algoritmo toma tiempo O( $s$ ×min( $m$ , $n$ )) , donde $myn$ son las longitudes de $las$ cadenas. La complejidad del espacio es O( $s$ ² ) u O( $s$ ) , dependiendo de si es necesario leer la secuencia de edición. ^[3]

Otras mejoras realizadas por Landau , Myers y Schmidt [1] dan 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], que tiene el peor tiempo de ejecución de 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 hay un pequeño número de 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.
La coincidencia de cadenas aproximada 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 determinista de estado finito 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 de 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 de idioma

Una generalización de la distancia de edición entre cadenas es la distancia de edición de idioma entre una cadena y un idioma, generalmente un lenguaje 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 ^[14] , donde es la distancia de edición de la cadena. Cuando el lenguaje L no tiene contexto , existe 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. ^[dieciséis] $d(L,x)=\min _{y\in L}d(x,y)$ $d(x,y)$

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

Ver también

Referencias

^ abcdefg Navarro, Gonzalo (1 de marzo de 2001). "Una visita guiada para aproximar la coincidencia de cadenas" (PDF) . Encuestas de Computación ACM . 33 (1): 31–88. CiteSeerX 10.1.1.452.6317 . doi :10.1145/375360.375365. S2CID 207551224 . Consultado el 19 de marzo de 2015 .
^ abcd Daniel Jurafsky; James H. Martín. Procesamiento del habla y el lenguaje . Internacional de la Educación Pearson. págs. 107-111.
^ abcde 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.
^ abcd Schulz, Klaus U.; Mihov, Stoyan (2002). "Corrección rápida de cuerdas con autómatas 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.
^ Lei Chen; Raymond Ng (2004). Sobre la unión de las normas Lp y la distancia de edición (PDF) . Proc. 30ª Conferencia Internacional. sobre bases de datos muy grandes (VLDB). vol. 30. doi :10.1016/b978-012088469-8.50070-x.
^ Kukich, Karen (1992). «Técnicas para corregir palabras automáticamente en un texto» (PDF) . Encuestas de Computación ACM . 24 (4): 377–439. doi :10.1145/146370.146380. S2CID 5431215. 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 cadena a cadena". 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 Ciencia + Medios comerciales . Bibcode : 2008adm..libro.....S. ISBN 978-1-849-96720-4.
^ Chowdhury, Rezaul; Le, Hai-Son; Ramachandran, Vijaya (julio de 2010). "Programación dinámica sin memoria 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.
^ 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áu; Myers; Schmidt (1998). "Comparación incremental de cadenas". Revista SIAM de Computación . 27 (2): 557–582. CiteSeerX 10.1.1.38.1766 . doi :10.1137/S0097539794264810.
^ Masek, William J.; Paterson, Michael S. (febrero de 1980). "Un algoritmo más rápido que calcula las 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.
^ Esko Ukkonen (1985). "Encontrar patrones aproximados en cadenas". J. Algoritmos . 6 : 132-137. doi :10.1016/0196-6774(85)90023-9.
^ ab Bringmann, Karl; Grandoni, Fabricio; Saha, Barna ; Williams, Virginia Vassilevska (2016). "Algoritmos verdaderamente subcúbicos para la distancia de edición del lenguaje y el plegado de ARN mediante un producto Min-Plus de diferencia acotada rápida" (PDF) . 57º Simposio anual del IEEE de 2016 sobre fundamentos de la informática (FOCS) . págs. 375–384. arXiv : 1707.05095 . doi :10.1109/focs.2016.48. ISBN 978-1-5090-3933-3. S2CID 17064578.
^ Ah, A.; Peterson, T. (1 de diciembre de 1972). "Un analizador de 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.
^ Wagner, Robert A. (1974). "Corrección Order-n para idiomas habituales". 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" . 55º Simposio anual del IEEE de 2014 sobre fundamentos de la informática. págs. 611–620. doi :10.1109/FOCS.2014.71. ISBN 978-1-4799-6517-5. S2CID 14806359.