Distancia Damerau-Levenshtein - Damerau–Levenshtein distance

${\ Displaystyle 1 _ {(a_ {i} \ neq b_ {j})}}$

${\ Displaystyle a_ {i} = b_ {j}}$

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

• ${\ Displaystyle d_ {a, b} (i-1, j) +1}$corresponde a una supresión (de a a b ),
• ${\ Displaystyle d_ {a, b} (i, j-1) +1}$corresponde a una inserción (de a a b ),
• ${\ Displaystyle d_ {a, b} (i-1, j-1) +1 _ {(a_ {i} \ neq b_ {j})}}$ corresponde a una coincidencia o discordancia, dependiendo de si los símbolos respectivos son iguales,
• ${\ Displaystyle d_ {a, b} (i-2, j-2) +1}$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: , donde denota la longitud de cadena de

${\ Displaystyle d_ {a, b} {\ big (} | a |, | b | {\ big)}}$

${\ Displaystyle i = | a |}$

${\ Displaystyle j = | b |}$

Algoritmo

Aquí se presentan dos algoritmos: el primero, más simple, calcula lo que se conoce como la distancia de alineación de cuerda óptima o distancia de edición restringida , mientras que el segundo 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

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 de alineación de la cuerda óptima 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

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

algorithm OSA-distance is
    input: strings a[1..length(a)], b[1..length(b)]
    output: distance, integer
    
    let d[0..length(a), 0..length(b)] be a 2-d array of integers, dimensions length(a)+1, length(b)+1
    // note that d is zero-indexed, while a and b are one-indexed.
    
    for i := 0 to length(a) inclusive do
        d[i, 0] := i
    for j := 0 to length(b) inclusive do
        d[0, j] := j
    
    for i := 1 to length(a) inclusive do
        for j := 1 to length(b) inclusive do
            if a[i] = b[j] then
                cost := 0
            else
                cost := 1
            d[i, j] := minimum(d[i-1, j] + 1,     // deletion
                               d[i, j-1] + 1,     // insertion
                               d[i-1, j-1] + cost)  // substitution
            if i > 1 and j > 1 and a[i] = b[j-1] and a[i-1] = b[j] then
                d[i, j] := minimum(d[i, j],
                                   d[i-2, j-2] + 1)  // transposition
    return d[length(a), length(b)]

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

if i > 1 and j > 1 and a[i] = b[j-1] and a[i-1] = b[j] then
    d[i, j] := minimum(d[i, j],
                       d[i-2, j-2] + 1)  // transposition

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 los arreglos estén en [0, | Σ |) :

algorithm DL-distance is
    input: strings a[1..length(a)], b[1..length(b)]
    output: distance, integer
    
    da := new array of |Σ| integers
    for i := 1 to |Σ| inclusive do
        da[i] := 0
    
    let d[−1..length(a), −1..length(b)] be a 2-d array of integers, dimensions length(a)+2, length(b)+2
    // note that d has indices starting at −1, while a, b and da are one-indexed.
    
    maxdist := length(a) + length(b)
    d[−1, −1] := maxdist
    for i := 0 to length(a) inclusive do
        d[i, −1] := maxdist
        d[i, 0] := i
    for j := 0 to length(b) inclusive do
        d[−1, j] := maxdist
        d[0, j] := j
    
    for i := 1 to length(a) inclusive do
        db := 0
        for j := 1 to length(b) inclusive do
            k := da[b[j]]
            ℓ := db
            if a[i] = b[j] then
                cost := 0
                db := j
            else
                cost := 1
            d[i, j] := minimum(d[i−1, j−1] + cost,  //substitution
                               d[i,   j−1] + 1,     //insertion
                               d[i−1, j  ] + 1,     //deletion
                               d[k−1, ℓ−1] + (i−k−1) + 1 + (j-ℓ−1)) //transposition
        da[a[i]] := i
    return d[length(a), length(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 posteriormente. (Esto es válido siempre que el costo de una transposición,, sea ​​al menos el promedio del costo de una inserción y eliminación, es decir, ). Por lo tanto, necesitamos considerar solo dos formas simétricas de modificar una subcadena más de una vez: ( 1) transponer letras e insertar una cantidad arbitraria 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 sencilla de esta idea proporciona un algoritmo de complejidad cúbica:, donde

${\ Displaystyle W_ {T}}$

${\ Displaystyle 2W_ {T} \ geq W_ {I} + W_ {D}}$

${\ Displaystyle O {\ big (} M \ cdot N \ cdot \ max (M, N) {\ big)}}$

${\ Displaystyle O (M \ cdot N)}$

Es interesante que el algoritmo bitap pueda modificarse para procesar la transposición. Consulte la sección de recuperación de información de para ver un ejemplo de dicha 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 incluso mitigaron la limitación de la distancia de edición restringida al introducir transposiciones generalizadas . Sin embargo, uno debe recordar que la distancia de edición restringida generalmente no satisface la desigualdad del

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