En teoría de la información e informática , la distancia Damerau-Levenshtein (llamada así por 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 por la otra.
La distancia Damerau-Levenshtein difiere de la distancia clásica de Levenshtein 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 fundamental, [5] Damerau declaró que en una investigación de errores ortográficos para un sistema de recuperación de información, más del 80% eran el resultado de un solo error de uno de los cuatro tipos. El artículo de Damerau consideró solo los errores ortográficos que podrían corregirse con como máximo una operación de edición. 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 Una función está definido, cuyo valor es una distancia entre un –Símbolo prefijo (subcadena inicial) de la cadena y un –Prefijo de símbolo de .
La función de distancia restringida se define de forma recursiva como :, [7] : A: 11
dónde es la función del indicador igual a 0 cuando e igual a 1 en caso contrario.
Cada llamada recursiva coincide con uno de los casos cubiertos por la distancia Damerau-Levenshtein:
- corresponde a una supresión (de a a b).
- corresponde a una inserción (de a a b).
- corresponde a una coincidencia o discordancia, dependiendo de si los símbolos respectivos son iguales.
- corresponde a una transposición entre dos símbolos sucesivos.
La distancia Damerau-Levenshtein entre una y b viene dada entonces por el valor de la función para las cadenas completas: dónde denota la longitud de la cadena de una yes la longitud de b .
Algoritmo
Aquí se presentan dos algoritmos: el primero, [8] uno más simple, calcula lo que se conoce como la distancia de alineación de cuerda óptima 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 de cadenas óptima calcula el número de operaciones de edición necesarias para igualar las cadenas con la condición de que ninguna subcadena se edite más de una vez , mientras que el segundo no presenta tal restricción.
Tomemos, por 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 óptima de alineación de la cuerda OSA ( CA , ABC ) = 3 porque si se usa la operación CA → AC , no es posible usar AC → ABC porque eso requeriría que la subcadena se edite más de una vez, lo cual 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 del triángulo no se mantiene: OSA ( CA , AC ) + OSA ( AC , ABC )
Distancia óptima de alineación de cuerdas
La distancia de alineación óptima de la cuerda 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 :
algoritmo OSA-distancia es entrada : cadenas a [1..longitud (a)], b [1..longitud (b)] salida : distancia, entero sea d [0..length (a), 0..length (b)] una matriz bidimensional de enteros, dimensiones longitud (a) +1, longitud (b) +1 // note que d es cero- indexados, mientras que ayb tienen un índice. para i: = 0 a la longitud (a) inclusive hacer d [i, 0]: = i para j: = 0 a la longitud (b) inclusive hacer d [0, j]: = j para i: = 1 a la longitud (a) inclusive hacer para j: = 1 a la 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] + costo ) // 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 return 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 Σ , por lo que todas las entradas de las matrices están en [0, | Σ |) : [7] : A: 93
algoritmo DL-distancia es entrada : cadenas a [1..longitud (a)], b [1..longitud (b)] salida : distancia, entero da: = nueva matriz de | Σ | enteros para i: = 1 a | Σ | inclusivo hacer da [i]: = 0 sea d [−1..length (a), −1..length (b)] sea una matriz 2-d de enteros, dimensiones length (a) +2, length (b) +2 // note que d tiene índices que comienzan en -1, mientras que a, by da tienen un índice. maxdist: = longitud (a) + longitud (b) d [−1, −1]: = maxdist para i: = 0 a la longitud (a) inclusive hacer d [i, −1]: = maxdist d [i, 0]: = i para j: = 0 a la longitud (b) inclusive hacer d [−1, j]: = maxdist d [0, j]: = j para i: = 1 a la longitud (a) inclusive hacer db: = 0 para j: = 1 a la 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] + costo, // 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]]: = i return 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 mientras el costo de una transposición,, es al menos el promedio del costo de una inserción y 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 sencilla implementación de esta idea proporciona un algoritmo de complejidad cúbica:, donde M y N son longitudes de cuerda. Usando las ideas de Lowrance y Wagner, [9] este ingenuo algoritmo puede mejorarse para ser en el peor de los casos, que es lo que hace el pseudocódigo anterior.
Es interesante que el algoritmo bitap pueda modificarse para procesar la transposición. Consulte la sección de recuperación de información de [1] para ver un ejemplo de tal adaptación.
Aplicaciones
La distancia 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 (errores ortográficos) rara vez excede 2. En tales circunstancias, la distancia de edición restringida y 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 no suele satisfacer la desigualdad del triángulo y, por tanto, no se puede utilizar con árboles métricos .
ADN
Dado que el ADN experimenta con frecuencia inserciones, deleciones, sustituciones y transposiciones, y cada una de estas operaciones ocurre aproximadamente en la misma escala de tiempo, la distancia Damerau-Levenshtein es una métrica apropiada de la variación entre dos cadenas de ADN. Más común en el ADN, las proteínas y otras tareas de alineación relacionadas con la bioinformática es el uso de algoritmos estrechamente relacionados, como el algoritmo Needleman-Wunsch o el algoritmo Smith-Waterman .
Detección de fraudes
El algoritmo se puede utilizar con cualquier conjunto de palabras, como nombres de proveedores. Dado que el ingreso es manual por naturaleza, existe el riesgo de ingresar un proveedor falso. Un empleado estafador puede ingresar un proveedor real como "Rich Heir Estate Services" versus un proveedor falso "Rich Hier State Services". El defraudador crearía 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 descartada y llamará la atención sobre los elementos a un examinador de fraudes.
Control de exportación
El gobierno de EE. UU. Utiliza la distancia Damerau-Levenshtein con su API de lista de cribado consolidada. [10]
Ver también
- Ispell sugiere correcciones que se basan en una distancia Damerau-Levenshtein de 1
- Typosquatting
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.
- ^ a b Bard, Gregory V. (2007), "Frases de paso independientes del orden, tolerante a errores ortográficos a través de la métrica de distancia de edición de cadenas de Damerau-Levenshtein", Actas del Quinto Simposio de Australasia sobre las fronteras de ACSW: 2007, Ballarat, Australia, enero 30 - 2 de febrero de 2007 , Conferencias sobre investigación y práctica en tecnología de la información, 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 similitudes de distribución 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 y reversiones", Física soviética Doklady , 10 (8): 707–710
- ^ Damerau, Fred J. (marzo de 1964), "Una técnica para la detección y corrección de errores ortográficos por computadora", Comunicaciones del ACM , 7 (3): 171-176, doi : 10.1145 / 363958.363994 , S2CID 7713345
- ^ El método utilizado en: Majorek, Karolina A .; Dunin-Horkawicz, Stanisław; et al. (2013), "La superfamilia similar a la RNasa 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
- ^ a b c Boytsov, Leonid (mayo de 2011). "Métodos de indexación para la búsqueda aproximada de diccionarios". Revista de algoritmos experimentales . 16 : 1. doi : 10.1145 / 1963190.1963191 . S2CID 15635688 .
- ^ a b Oommen, BJ; Loke, RKS (1997). "Reconocimiento de patrones de cadenas con sustituciones, inserciones, eliminaciones y transposiciones generalizadas". Reconocimiento de patrones . 30 (5): 789–800. CiteSeerX 10.1.1.50.1459 . doi : 10.1016 / S0031-3203 (96) 00101-X .
- ^ a b c Lowrance, Roy; Wagner, Robert A. (abril de 1975), "An Extension of the String-to-String Correction Problem", J ACM , 22 (2): 177–183, doi : 10.1145 / 321879.321880 , S2CID 18892193
- ^ http://developer.trade.gov/consolidated-screening-list.html
Otras lecturas
- Navarro, Gonzalo (marzo de 2001), "Una visita guiada para aproximar la coincidencia de cadenas", Encuestas de computación de ACM , 33 (1): 31–88, CiteSeerX 10.1.1.452.6317 , doi : 10.1145 / 375360.375365 , S2CID 207551224