Editar distancia

En lingüística computacional e informática , la distancia de edición es una métrica de cadenas , es decir, una forma de cuantificar la disimilitud entre dos cadenas (por ejemplo, palabras), que se mide contando el número mínimo de operaciones necesarias para transformar una cadena en la otra. Las distancias de edición tienen 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 tengan una baja distancia 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 las letras A , C , G y T.

Las distintas definiciones de distancia de edición utilizan diferentes conjuntos de operaciones similares. Las operaciones de distancia de Levenshtein consisten en 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 se usa a menudo indistintamente con distancia de edición . ^{[ 1 ]}

Tipos de distancia de edición

Los distintos tipos de distancia de edición permiten diferentes conjuntos de operaciones de cadena. 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 coste (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 coste de una operación dependa de dónde se aplique.

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 peso mínimo de operaciones de edición que transforma $a$ en $b$ . Uno de los conjuntos más simples de operaciones de edición 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 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

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 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. ^[²^]

Se han sugerido operaciones primitivas adicionales. La distancia de Damerau-Levenshtein considera 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 únicas dos 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 ; 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ínimo que transforma el primero en el segundo es:

k itten → s itten (sustituir "s" por "k")
sitt e n → sitt i n (sustituye "i" por "e")
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:

k itten → itten (borrar "k" en 0)
itten → s itten (insertar "s" en 0)
sitt e n → sittn (eliminar "e" en 4)
sittn → sitt i n (inserte "i" en 4)
sentado → sentado g (insertar "g" en 6)

para un coste/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 coste positivo;
Para cada operación, existe una operación inversa con el mismo coste.

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 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 coste distinto de cero.

d

(

a

,

b

) =

d

(

b

,

a

) por igualdad del costo de cada operación y su inverso.

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 propias. ^{[ 1 ]}

Otras propiedades útiles de las distancias de edición de costo unitario incluyen:

La distancia LCS está limitada superiormente por la suma de las longitudes de un par de cadenas. ^{[ 1 ]}^{: 37}
La distancia LCS es un límite superior para la distancia de Levenshtein.
Para cadenas de la misma longitud, la distancia de Hamming es una cota 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 afecta 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 de edición mínima entre un par de cadenas fue publicado por Damerau en 1964. ^{[ 6 ]}

Algoritmo común

Utilizando las operaciones originales de Levenshtein, la distancia de edición (no simétrica) de $a=a_{1}\ldots a_{m}$ a $b=b_{1}\ldots b_{n}$ es dado por $d_{mn}$ , definido por la recurrencia ^{[ 2 ]}

{\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 puede generalizarse para manejar transposiciones agregando otro término en la minimización de la cláusula recursiva. ^{[ 3 ]}

La forma directa 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 rastreo inverso de las operaciones utilizadas durante el algoritmo de programación dinámica comenzando en $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$ )) al observar que en cualquier instante, el algoritmo solo requiere dos filas (o dos columnas) en 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 a este problema . ^{[ 8 ]}^{: 634} Chowdhury, Le y Ramachandran dan 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 de edición máxima $s$ , y devuelve min( $s$ , $d$ ) . Lo logra calculando y almacenando solo una parte de la tabla de programación dinámica alrededor de su diagonal. Este algoritmo toma un tiempo O( $s$ ×min( $m$ , $n$ )) , donde $m$ y $n$ son las longitudes de las cadenas. La complejidad espacial es O( $s$ ² ) u O( $s$ ) , dependiendo de si se necesita leer la secuencia de edición. ^{[ 3 ]}

Nuevas mejoras realizadas por Landau , Myers y Schmidt.Proporcionar un algoritmo con 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 un tiempo de ejecución en el peor de los casos de O(nm/logn).

Aplicaciones

Edit distance finds applications in computational biology and natural language processing, e.g. the correction of spelling mistakes or OCR errors, and approximate string matching, where the objective is to find matches for short strings in many longer texts, in situations where a small number of differences is to be expected.

Various algorithms exist that solve problems beside the computation of distance between a pair of strings, to solve related types of problems.

Hirschberg's algorithm computes the optimal alignment of two strings, where optimality is defined as minimizing edit distance.
Approximate string matching can be formulated in terms of edit distance. Ukkonen's 1985 algorithm takes a string $p$ , called the pattern, and a constant $k$ ; it then builds a deterministic finite state automaton that finds, in an arbitrary string $s$ , a substring whose edit distance to $p$ is at most $k$ ^[13] (cf. the Aho–Corasick algorithm, which similarly constructs an automaton to search for any of a number of patterns, but without allowing edit operations). A similar algorithm for approximate string matching is the bitap algorithm, also defined in terms of edit distance.
Levenshtein automata are finite-state machines that recognize a set of strings within bounded edit distance of a fixed reference string.^[4]

Language edit distance

A generalization of the edit distance between strings is the language edit distance between a string and a language, usually a formal language. Instead of considering the edit distance between one string and another, the language edit distance is the minimum edit distance that can be attained between a fixed string and any string taken from a set of strings. More formally, for any language L and string x over an alphabet $Σ$ , the language edit distance d(L, x) is given by^[14] $d(L,x)=\min _{y\in L}d(x,y)$ , where $d(x,y)$ is the string edit distance. When the language L is context free, there is a cubic time dynamic programming algorithm proposed by Aho and Peterson in 1972 which computes the language edit distance.^[15] For less expressive families of grammars, such as the regular grammars, faster algorithms exist for computing the edit distance.^[16]

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

Véase también

Referencias

1 2 3 4 5 6 7 Navarro, Gonzalo (1 de marzo de 2001). "Una visita guiada a la coincidencia aproximada de cadenas" (PDF) . ACM Computing Surveys . 33 (1): 31–88 . CiteSeerX 10.1.1.452.6317 . doi : 10.1145/375360.375365 . S2CID 207551224. Recuperado el 19 de marzo de 2015 .
1 2 3 4 Daniel Jurafsky; James H. Martin. Procesamiento del habla y del lenguaje . Pearson Education International. págs. 107–111 .
1 2 3 4 5 Esko Ukkonen (1983). Sobre la coincidencia 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 .
1 2 3 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 .
↑ Lei Chen; Raymond Ng (2004). Sobre el matrimonio de las normas L _p y la distancia de edición (PDF) . Actas de la 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 la corrección automática de palabras en texto" (PDF) . ACM Computing Surveys . 24 (4): 377– 439. doi : 10.1145/146370.146380 . S2CID 5431215. Archivado del original (PDF) el 27 de septiembre de 2016. Recuperado el 9 de noviembre de 2017 .
↑ R. Wagner; M. Fischer (1974). "El problema de corrección de cadena a cadena" . J. ACM . 21 : 168–178 . doi : 10.1145/321796.321811 . S2CID 13381535 .
↑ Skiena, Steven (2010). Manual de diseño de algoritmos (2.ª ed.). Springer Science+Business Media . Bibcode : 2008adm..book.....S . ISBN 978-1-849-96720-4.
↑ Chowdhury, Rezaul; Le, Hai-Son; Ramachandran, Vijaya (julio de 2010). "Programación dinámica independiente de la caché para bioinformática". IEEE/ACM Transactions on Computational Biology and Bioinformatics . 7 (3): 495– 510. Bibcode : 2010ITCBB...7..495C . doi : 10.1109/TCBB.2008.94 . PMID 20671320 . S2CID 2532039 .
↑ Ukkonen, Esko (1985). "Algoritmos para la coincidencia aproximada de cadenas" (PDF) . Information and Control . 64 ( 1–3 ): 100–118 . doi : 10.1016/S0019-9958(85)80046-2 .
↑ Landau; Myers; Schmidt (1998). "Comparación incremental de cadenas". SIAM Journal on Computing . 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 para calcular distancias de edición de cadenas" . Journal of Computer and System Sciences . 20 (1): 18– 31. doi : 10.1016/0022-0000(80)90002-1 . hdl : 1721.1/148933 . ISSN 0022-0000 .
↑ Esko Ukkonen (1985). "Encontrar patrones aproximados en cadenas". J. Algoritmos . 6 : 132– 137. doi : 10.1016/0196-6774(85)90023-9 .
1 2 Bringmann, Karl; Grandoni, Fabrizio; Saha, Barna ; Williams, Virginia Vassilevska (2016). "Algoritmos verdaderamente subcúbicos para la distancia de edición de lenguaje y el plegado de ARN mediante el producto min-plus de diferencia acotada rápida" (PDF) . 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) . pp. 375–384 . arXiv : 1707.05095 . doi : 10.1109/focs.2016.48 . ISBN 978-1-5090-3933-3. S2CID 17064578 .
↑ Aho, A.; Peterson, T. (1972-12-01). "Un analizador sintáctico corrector de errores de distancia mínima para lenguajes libres de contexto". SIAM Journal on Computing . 1 (4): 305– 312. doi : 10.1137/0201022 . ISSN 0097-5397 .
↑ Wagner, Robert A. (1974). "Corrección de orden n para lenguajes regulares" . Communications of the 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 de Dyck en tiempo casi lineal . 55.º Simposio Anual de la IEEE sobre Fundamentos de la Informática, 2014. págs. 611–620 . doi : 10.1109/FOCS.2014.71 . ISBN 978-1-4799-6517-5. S2CID 14806359 .

[navarnarutoro-1] 1 2 3 4 5 6 7 Navarro, Gonzalo (1 de marzo de 2001). "Una visita guiada a la coincidencia aproximada de cadenas" (PDF) . ACM Computing Surveys . 33 (1): 31–88 . CiteSeerX 10.1.1.452.6317 . doi : 10.1145/375360.375365 . S2CID 207551224. Recuperado el 19 de marzo de 2015 .

[slp-2] 1 2 3 4 Daniel Jurafsky; James H. Martin. Procesamiento del habla y del lenguaje . Pearson Education International. págs. 107–111 .

[ukkonen83-3] 1 2 3 4 5 Esko Ukkonen (1983). Sobre la coincidencia 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 .

[ssm-4] 1 2 3 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 el matrimonio de las normas L _p y la distancia de edición (PDF) . Actas de la 30.ª Conferencia Internacional sobre Bases de Datos Muy Grandes (VLDB). Vol. 30. doi : 10.1016/b978-012088469-8.50070-x .

[6] Kukich, Karen (1992). "Técnicas para la corrección automática de palabras en texto" (PDF) . ACM Computing Surveys . 24 (4): 377– 439. doi : 10.1145/146370.146380 . S2CID 5431215. Archivado del original (PDF) el 27 de septiembre de 2016. Recuperado el 9 de noviembre de 2017 .

[7] R. Wagner; M. Fischer (1974). "El problema de corrección de cadena a cadena" . J. ACM . 21 : 168–178 . doi : 10.1145/321796.321811 . S2CID 13381535 .

[8] Skiena, Steven (2010). Manual de diseño de algoritmos (2.ª ed.). Springer Science+Business Media . Bibcode : 2008adm..book.....S . ISBN 978-1-849-96720-4.

[CLR-08-9] Chowdhury, Rezaul; Le, Hai-Son; Ramachandran, Vijaya (julio de 2010). "Programación dinámica independiente de la caché para bioinformática". IEEE/ACM Transactions on Computational Biology and Bioinformatics . 7 (3): 495– 510. Bibcode : 2010ITCBB...7..495C . doi : 10.1109/TCBB.2008.94 . PMID 20671320 . S2CID 2532039 .

[10] Ukkonen, Esko (1985). "Algoritmos para la coincidencia aproximada de cadenas" (PDF) . Information and Control . 64 ( 1–3 ): 100–118 . doi : 10.1016/S0019-9958(85)80046-2 .

[11] Landau; Myers; Schmidt (1998). "Comparación incremental de cadenas". SIAM Journal on Computing . 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" . Journal of Computer and System Sciences . 20 (1): 18– 31. doi : 10.1016/0022-0000(80)90002-1 . hdl : 1721.1/148933 . 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 .

[:0-14] 1 2 Bringmann, Karl; Grandoni, Fabrizio; Saha, Barna ; Williams, Virginia Vassilevska (2016). "Algoritmos verdaderamente subcúbicos para la distancia de edición de lenguaje y el plegado de ARN mediante el producto min-plus de diferencia acotada rápida" (PDF) . 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) . pp. 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 corrector de errores de distancia mínima para lenguajes libres de contexto". SIAM Journal on Computing . 1 (4): 305– 312. doi : 10.1137/0201022 . ISSN 0097-5397 .

[16] Wagner, Robert A. (1974). "Corrección de orden n para lenguajes regulares" . Communications of the 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 de Dyck en tiempo casi lineal . 55.º Simposio Anual de la IEEE sobre Fundamentos de la Informática, 2014. págs. 611–620 . doi : 10.1109/FOCS.2014.71 . ISBN 978-1-4799-6517-5. S2CID 14806359 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[13]

[15]

[16]

[ 17 ]