Distancia Damerau-Levenshtein

En teoría de la información y ciencias de la computación , la distancia Damerau-Levenshtein (nombrada en honor a Frederick J. Damerau y Vladimir I. Levenshtein ^[1]^[2]^[3] ) es una métrica de cadena para medir la distancia de edición entre dos secuencias. De manera informal, la distancia Damerau-Levenshtein entre dos palabras es el número mínimo de operaciones (que consisten en inserciones, eliminaciones o sustituciones de un solo carácter, o transposición de dos caracteres adyacentes) necesarias para cambiar una palabra en otra.

La distancia Damerau-Levenshtein se diferencia de la distancia Levenshtein clásica al incluir transposiciones entre sus operaciones permitidas además de las tres operaciones clásicas de edición de un solo carácter (inserciones, eliminaciones y sustituciones). ^[4]^[2]

En su artículo seminal, ^[5] Damerau afirmó que en una investigación de errores ortográficos para un sistema de recuperación de información, más del 80% eran resultado de un solo error de uno de los cuatro tipos. El artículo de Damerau consideró solo errores ortográficos que podían corregirse con una sola operación de edición como máximo. Si bien la motivación original era medir la distancia entre errores ortográficos humanos para mejorar aplicaciones como los correctores ortográficos , la distancia Damerau-Levenshtein también se ha utilizado en biología para medir la variación entre secuencias de proteínas. ^[6]

Definición

Para expresar la distancia Damerau–Levenshtein entre dos cadenas y , se define una función cuyo valor es una distancia entre un prefijo -símbolo (subcadena inicial) de cadena y un prefijo -símbolo de . ${\estilo de visualización a}$ ${\estilo de visualización b}$ $Estilo de visualización d_{a,b}(i,j)}$ ${\estilo de visualización i}$ ${\estilo de visualización a}$ ${\estilo de visualización j}$ ${\estilo de visualización b}$

La función de distancia restringida se define recursivamente como: ^[7]^{: A:11} donde la función indicadora es igual a 0 cuando y es igual a 1 en caso contrario. $d_{a,b}(i,j)=\min {\begin{cases}0&{\text{si }}i=j=0,\\d_{a,b}(i-1,j)+1&{\text{si }}i>0,\\d_{a,b}(i,j-1)+1&{\text{si }}j>0,\\d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}&{\text{si }}i,j>0,\\d_{a,b}(i-2,j-2)+1_{(a_{i}\neq b_{j})}&{\text{si }}i,j>1{\text{ y }}a_{i}=b_{j-1}{\text{ y }}a_{i-1}=b_{j},\\\fin{de los casos}}$ $1_{(a_{i}\neq b_{j})}$ $a_{i}=b_{j}$

Cada llamada recursiva coincide con uno de los casos cubiertos por la distancia Damerau-Levenshtein:

$d_{a,b}(i-1,j)+1$ corresponde a una eliminación (de a a b ),
$d_{a,b}(i,j-1)+1$ corresponde a una inserción (de a a b ),
$d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}$ corresponde a una coincidencia o desajuste, dependiendo de si los respectivos símbolos son los mismos,
$d_{a,b}(i-2,j-2)+1_{(a_{i}\neq b_{j})}$ corresponde a una transposición entre dos símbolos sucesivos.

La distancia Damerau-Levenshtein entre $a$ y $b$ viene dada entonces por el valor de la función para cadenas completas: , donde denota la longitud de la cadena $a$ , y es la longitud de $b$ . $d_{a,b}{\big (}|a|,|b|{\big )}$ $i=|a|$ $j=|b|$

Algoritmo

Aquí se presentan dos algoritmos: el primero, ^[8] más simple, calcula lo que se conoce como la distancia óptima de alineación de cadenas o distancia de edición restringida , ^[7] mientras que el segundo ^[9] calcula la distancia Damerau-Levenshtein con transposiciones adyacentes. Agregar transposiciones agrega una complejidad significativa. La diferencia entre los dos algoritmos consiste en que el algoritmo de alineación óptima de cadenas calcula el número de operaciones de edición necesarias para hacer que las cadenas sean iguales bajo la condición de que ninguna subcadena se edite más de una vez , mientras que el segundo no presenta tal restricción.

Tomemos como ejemplo la distancia de edición entre CA y ABC . La distancia Damerau–Levenshtein LD( CA , ABC ) = 2 porque CA → AC → ABC , pero la distancia de alineación de cadena óptima OSA( CA , ABC ) = 3 porque si se utiliza la operación CA → AC , no es posible utilizar AC → ABC porque eso requeriría que la subcadena se edite más de una vez, lo que no está permitido en OSA, y por lo tanto la secuencia más corta de operaciones es CA → A → AB → ABC . Tenga en cuenta que para la distancia de alineación de cadena óptima, la desigualdad triangular no se cumple: OSA( CA , AC ) + OSA( AC , ABC ) < OSA( CA , ABC ), y por lo tanto no es una métrica verdadera.

Distancia óptima de alineación de cuerdas

La distancia óptima de alineación de cuerdas se puede calcular utilizando una extensión sencilla del algoritmo de programación dinámica de Wagner-Fischer que calcula la distancia de Levenshtein . En pseudocódigo :

El algoritmo OSA-distancia tiene  como entrada : cadenas a[1..length(a)], b[1..length(b)] salida : distancia, número entero  sea d[0..length(a), 0..length(b)] una matriz 2-d de números enteros, dimensiones length(a)+1, length(b)+1 // tenga en cuenta que d tiene índice cero, mientras que a y b tienen índice uno.  para i := 0 hasta longitud(a) inclusive  hacer d[i, 0] := i para j := 0 hasta longitud(b) inclusive  hacer d[0, j] := j  para i := 1 hasta longitud(a) inclusive  hacer  para j := 1 hasta longitud(b) inclusive  hacer  si a[i] = b[j] entonces costo := 0 demás costo := 1 d[i, j] := mínimo(d[i-1, j] + 1, // eliminación d[i, j-1] + 1, // inserción d[i-1, j-1] + coste) // sustitución  si i > 1 y j > 1 y a[i] = b[j-1] y a[i-1] = b[j] entonces d[i, j] := mínimo(d[i, j], d[i-2, j-2] + 1) // transposición  devuelve d[longitud(a), longitud(b)]

La diferencia con el algoritmo para la distancia de Levenshtein es la adición de una recurrencia:

si i > 1 y j > 1 y a[i] = b[j-1] y a[i-1] = b[j] entonces d[i, j] := mínimo(d[i, j], d[i-2, j-2] + 1) // transposición

Distancia con transposiciones adyacentes

El siguiente algoritmo calcula la verdadera distancia Damerau–Levenshtein con transposiciones adyacentes; este algoritmo requiere como parámetro adicional el tamaño del alfabeto $Σ$ , de modo que todas las entradas de las matrices estén en $[0, |Σ|)$ : ^[7]^{: A:93}

El algoritmo DL-distancia tiene  como entrada : cadenas a[1..length(a)], b[1..length(b)] salida : distancia, número entero  da := nueva matriz de enteros |Σ| para i := 1 hasta |Σ| inclusive  hacer da[i] := 0  sea d[−1..length(a), −1..length(b)] una matriz 2-d de números enteros, dimensiones length(a)+2, length(b)+2 // note que d tiene índices que comienzan en −1, mientras que a, b y da tienen índice uno.  maxdist := longitud(a) + longitud(b) d[−1, −1] := distancia máxima para i := 0 hasta longitud(a) inclusive  hacer d[i, −1] := distancia máxima d[i, 0] := i para j := 0 hasta longitud(b) inclusive  hacer d[−1, j] := distancia máxima d[0, j] := j  para i := 1 hasta longitud(a) inclusive  hacer base de datos := 0 para j := 1 hasta longitud(b) inclusive  hacer k := da[b[j]] ℓ := db si a[i] = b[j] entonces costo := 0 db :=j demás costo := 1 d[i, j] := mínimo(d[i−1, j−1] + coste, //sustitución d[i, j−1] + 1, //inserción d[i−1, j ] + 1, //eliminación d[k−1, ℓ−1] + (i−k−1) + 1 + (j-ℓ−1)) //transposición da[a[i]] := yo devuelve d[longitud(a), longitud(b)]

Para diseñar un algoritmo adecuado para calcular la distancia Damerau–Levenshtein sin restricciones, tenga en cuenta que siempre existe una secuencia óptima de operaciones de edición, donde las letras una vez transpuestas nunca se modifican después. (Esto es válido siempre que el coste de una transposición, , sea al menos el promedio del coste de una inserción y una eliminación, es decir, . ^[9] ) Por lo tanto, necesitamos considerar solo dos formas simétricas de modificar una subcadena más de una vez: (1) transponer letras e insertar un número arbitrario de caracteres entre ellas, o (2) eliminar una secuencia de caracteres y transponer letras que se vuelven adyacentes después de la eliminación. La implementación directa de esta idea da un algoritmo de complejidad cúbica: , donde M y N son longitudes de cadena. Usando las ideas de Lowrance y Wagner, ^[9] este algoritmo ingenuo se puede mejorar para que esté en el peor de los casos, que es lo que hace el pseudocódigo anterior. $Estilo de visualización: W_{T}$ $2W_{T}\geq W_{I}+W_{D}$ $O{\big (}M\cdot N\cdot \max(M,N){\big )}$ $O(M\cdot N)$

Es interesante que el algoritmo bitap se pueda modificar para procesar la transposición. Véase la sección de recuperación de información de ^[1] para ver un ejemplo de dicha adaptación.

Aplicaciones

La distancia de Damerau–Levenshtein juega un papel importante en el procesamiento del lenguaje natural . En los lenguajes naturales, las cadenas son cortas y el número de errores (faltas de ortografía) rara vez supera los 2. En tales circunstancias, la distancia de edición restringida y la real difieren muy raramente. Oommen y Loke ^[8] incluso mitigaron la limitación de la distancia de edición restringida al introducir transposiciones generalizadas . Sin embargo, hay que recordar que la distancia de edición restringida normalmente no satisface la desigualdad triangular y, por lo tanto, no se puede utilizar con árboles métricos .

ADN

Dado que el ADN sufre con frecuencia inserciones, deleciones, sustituciones y transposiciones, y cada una de estas operaciones se produce aproximadamente en la misma escala de tiempo, la distancia Damerau-Levenshtein es una métrica adecuada de la variación entre dos cadenas de ADN. ^[6] Más común en las tareas de alineación de ADN, proteínas y otras tareas relacionadas con la bioinformática es el uso de algoritmos estrechamente relacionados, como el algoritmo Needleman-Wunsch o el algoritmo Smith-Waterman . ^{[ cita requerida ]}

Detección de fraude

El algoritmo se puede utilizar con cualquier conjunto de palabras, como los nombres de los proveedores. Dado que la entrada es manual por naturaleza, existe el riesgo de introducir un proveedor falso. Un empleado defraudador puede introducir un proveedor real, como "Rich Heir Estate Services", en lugar de un proveedor falso, como "Rich Hier State Services". El defraudador crearía entonces una cuenta bancaria falsa y haría que la empresa enviara los cheques al proveedor real y al proveedor falso. El algoritmo Damerau-Levenshtein detectará la letra transpuesta y omitida y llamará la atención de un examinador de fraudes sobre los elementos.

Control de exportaciones

El gobierno de los EE. UU. utiliza la distancia Damerau-Levenshtein con su API de lista de detección consolidada. ^[10]

Véase también

Ispell – Sugiere correcciones que se basan en una distancia Damerau-Levenshtein de 1
Typosquatting : forma de ciberocupación que se basa en errores al ingresar la dirección de un sitio web.

Referencias

^ Brill, Eric; Moore, Robert C. (2000). Un modelo de error mejorado para la corrección ortográfica de canales ruidosos (PDF) . Actas de la 38.ª reunión anual de la Asociación de Lingüística Computacional. págs. 286-293. doi : 10.3115/1075218.1075255 . Archivado desde el original (PDF) el 21 de diciembre de 2012.
^ ab Bard, Gregory V. (2007), "Frases de contraseña independientes del orden y tolerantes a errores ortográficos mediante la métrica de distancia de edición de cadenas Damerau–Levenshtein", Actas del quinto simposio de Australasia sobre las fronteras de la ACSW: 2007, Ballarat, Australia, 30 de enero - 2 de febrero de 2007, Conferencias de investigación y práctica en tecnología de la información, vol. 68, Darlinghurst, Australia: Australian Computer Society, Inc., págs. 117-124, ISBN 978-1-920682-49-1.
^ Li; et al. (2006). Exploración de modelos basados en similitud distributiva para la corrección ortográfica de consultas (PDF) . Actas de la 21.ª Conferencia Internacional sobre Lingüística Computacional y la 44.ª reunión anual de la Asociación de Lingüística Computacional. págs. 1025–1032. doi : 10.3115/1220175.1220304 . Archivado desde el original (PDF) el 1 de abril de 2010.
^ Levenshtein, Vladimir I. (febrero de 1966), "Códigos binarios capaces de corregir eliminaciones, inserciones e inversiones", Soviet Physics Doklady , 10 (8): 707–710, Bibcode :1966SPhD...10..707L
^ Damerau, Fred J. (marzo de 1964), "Una técnica para la detección y corrección de errores ortográficos por ordenador", Communications of the ACM , 7 (3): 171–176, doi : 10.1145/363958.363994 , S2CID 7713345
^ de Majorek, Karolina A.; Dunin-Horkawicz, Stanisław; et al. (2013), "La superfamilia de ARNasas tipo H: nuevos miembros, análisis estructural comparativo y clasificación evolutiva", Nucleic Acids Research , 42 (7): 4160–4179, doi :10.1093/nar/gkt1414, PMC 3985635 , PMID 24464998
^ abc Boytsov, Leonid (mayo de 2011). "Métodos de indexación para búsquedas aproximadas en diccionarios". Journal of Experimental Algorithmics . 16 : 1. doi :10.1145/1963190.1963191. S2CID 15635688.
^ ab Oommen, BJ; Loke, RKS (1997). "Reconocimiento de patrones de cadenas con sustituciones, inserciones, eliminaciones y transposiciones generalizadas". Reconocimiento de patrones . 30 (5): 789–800. Bibcode :1997PatRe..30..789O. CiteSeerX 10.1.1.50.1459 . doi :10.1016/S0031-3203(96)00101-X.
^ abc Lowrance, Roy; Wagner, Robert A. (abril de 1975), "Una extensión del problema de corrección de cuerda a cuerda", J ACM , 22 (2): 177–183, doi : 10.1145/321879.321880 , S2CID 18892193
^ "API de lista de selección consolidada". Portal para desarrolladores de Trade.gov . Administración de Comercio Internacional, Departamento de Comercio de los EE. UU. Archivado desde el original el 30 de octubre de 2019.

Lectura adicional

Navarro, Gonzalo (marzo de 2001), "Una visita guiada a la aproximación de la correspondencia de cadenas", ACM Computing Surveys , 33 (1): 31–88, doi :10.1145/375360.375365, S2CID 207551224