LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

 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. Informalmente, 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) requeridas para cambiar una palabra en 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 seminal, ^[5] Damerau declaró que más del 80% de todos los errores ortográficos humanos pueden expresarse por un solo error de uno de los cuatro tipos. El documento de Damerau consideró solo 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 los errores ortográficos humanos para mejorar aplicaciones como los correctores ortográficos , la distancia Damerau-Levenshtein también ha visto usos en biología para medir la variación entre las secuencias de proteínas.

Definición [ editar ]

Para expresar la distancia Damerau – Levenshtein entre dos cuerdas $${\ displaystyle a} y $${\ displaystyle b} Una función $${\ displaystyle d_ {a, b} (i, j)} está definido, cuyo valor es una distancia entre un $${\ displaystyle i}–Prefijo de símbolo (subcadena inicial) de cadena $${\ displaystyle a} y un $${\ displaystyle j}- prefijo de símbolo de $${\ displaystyle b}.

La función de distancia restringida se define de forma recursiva como :, ^{[7] : A: 11}

{\ displaystyle \ qquad d_ {a, b} (i, j) = \ min {\ begin {cases} 0 & {\ text {if}} i = j = 0 \\ d_ {a, b} (i-1 , j) +1 y {\ text {if}} i> 0 \\ d_ {a, b} (i, j-1) +1 & {\ text {if}} j> 0 \\ d_ {a, b} (i-1, j-1) +1 _ {(a_ {i} \ neq b_ {j})} & {\ text {if}} i, j> 0 \\ d_ {a, b} (i-2 , j-2) +1 & {\ text {if}} i, j> 1 {\ text {and}} a [i] = b [j-1] {\ text {and}} a [i-1] = b [j] \\\ end {casos}}}

dónde $${\ displaystyle 1 _ {(a_ {i} \ neq b_ {j})}}es la función del indicador igual a 0 cuando $${\ displaystyle a_ {i} = b_ {j}} e igual a 1 de lo contrario.

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 eliminació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 falta de coincidencia, dependiendo de si los símbolos respectivos son los mismos.
• $${\ 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:$${\ displaystyle d_ {a, b} (| a |, | b |)} dónde $${\ displaystyle i = | a |}denota la longitud de la cadena de una y$${\ displaystyle j = | b |}es la longitud de b .

Algoritmo [ editar ]

Aquí se presentan dos algoritmos: el primero, ^[8] más simple, calcula lo que se conoce como la distancia óptima de alineación de cuerdas 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 óptimo de alineación de cadenas calcula el número de operaciones de edición necesarias para igualar las cadenas bajo la condición de que no se edite ninguna subcadena más de una vez , mientras que el segundo no presenta dicha 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 de alineación de cadena ó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 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 del triángulo no se cumple: OSA ( CA , AC ) + OSA ( AC , ABC ) CA , ABC ), por lo que no es una métrica verdadera.

Distancia de alineación de cadena óptima [ editar ]

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

el algoritmo OSA-distance es 
    input : cadenas a [1..length (a)], b [1..length (b)]
     output : distance, integer
    
    sea d [0..length (a), 0..length (b)] una matriz de enteros en 2-d, dimensiones length (a) +1, length (b) +1
     // tenga en cuenta que d es cero- indexado, mientras que ayb están indexados en uno.
    
    para i: = 0 a la longitud (a) inclusive  do
        d [i, 0]: = i
    para j: = 0 a la longitud (b) inclusive  do
        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
            má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] + costo)   // 
    retorno de la transposición 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] + costo)   // transposición

Distancia con transposiciones adyacentes [ editar ]

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-distance es 
    input : cadenas a [1..length (a)], b [1..length (b)]
     output : distance, integer
    
    da: = nueva matriz de | Σ | enteros
    para i: = 1 a | Σ | inclusivo  hacer
        da [i]: = 0
    
    dejemos que d [−1..length (a), −1..length (b)] sea una matriz 2-d de enteros, dimensiones length (a) +2, length (b) +2
     // tenga en cuenta que d tiene índices que comienzan en −1, mientras que a, by da están indexados en uno.
    
    maxdist: = longitud (a) + longitud (b)
    d [−1, −1]: = maxdist
    para i: = 0 a la longitud (a) inclusive  do
        d [i, −1]: = maxdist
        d [i, 0]: = i
    para j: = 0 a la longitud (b) inclusive  do
        d [−1, j]: = maxdist
        d [0, j]: = j
    
    para i: = 1 a la longitud (a) inclusive  do
        db: = 0
        para j: = 1 a la longitud (b) inclusive  do
            k: = da [b [j]]
            ℓ: = db
            si a [i] = b [j] entonces
                costo: = 0
                db: = j
            má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
    retorno d [longitud (a), longitud (b)]

Para idear un algoritmo adecuado para calcular la distancia de Damerau-Levenshtein sin restricciones, tenga en cuenta que siempre existe una secuencia óptima de operaciones de edición, donde las letras transpuestas una vez nunca se modifican después. (Esto es válido siempre que el costo de una transposición,$${\ displaystyle W_ {T}}, es al menos el promedio del costo de una inserción y eliminación, es decir, $${\ displaystyle 2W_ {T} \ geq W_ {I} + W_ {D}}. ^[9] ) Por lo tanto, debemos 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 convertirse en adyacente después de la eliminación. La implementación directa de esta idea proporciona un algoritmo de complejidad cúbica:$${\ displaystyle O \ left (M \ cdot N \ cdot \ max (M, N) \ right)}, donde M y N son longitudes de cadena. Usando las ideas de Lowrance y Wagner, ^[9] este ingenuo algoritmo puede mejorarse para ser$${\ displaystyle O \ left (M \ cdot N \ right)} En el peor de los casos.

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

Aplicaciones [ editar ]

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 difiere muy raramente. Oommen y Loke ^[8] incluso mitigaron la limitación de la distancia de edición restringida mediante la introducción de transposiciones generalizadas . Sin embargo, uno debe recordar que la distancia de edición restringida generalmente no satisface la desigualdad del triángulo y, por lo tanto, no puede usarse con árboles métricos .

ADN [ editar ]

Dado que el ADN se somete con frecuencia a 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 medida adecuada 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 fraude [ editar ]

El algoritmo se puede usar con cualquier conjunto de palabras, como nombres de proveedores. Dado que la entrada es manual por naturaleza, existe el riesgo de ingresar a un proveedor falso. Un empleado fraudulento puede ingresar a un proveedor real como "Rich Heir Estate Services" frente a un proveedor falso "Rich Hier State Services". El estafador luego crearía una cuenta bancaria falsa y la compañía enrutaría los cheques al vendedor real y al vendedor falso. El algoritmo Damerau-Levenshtein detectará la letra transpuesta y descartada y llamará la atención de los elementos a un examinador de fraudes.

Control de exportación [ editar ]

El gobierno de los EE. UU. Utiliza la distancia Damerau – Levenshtein con su API Consolidated Screening List.

El coeficiente Sørensen-Dice (ver abajo para otros nombres) es una estadística utilizada para medir la similitud de dos muestras . Fue desarrollado independientemente por los botánicos Thorvald Sørensen ^[1] y Lee Raymond Dice , ^[2] que publicaron en 1948 y 1945 respectivamente.

Nombre [ editar ]

El índice es conocido por varios otros nombres, especialmente el índice Sørensen-Dice , el índice Sørensen y el coeficiente de Dice . Otras variaciones incluyen el "coeficiente de similitud" o "índice", como el coeficiente de similitud de dados (DSC) . Deletreos alternativos comunes para Sørensen son Sorenson, Soerenson y Sörenson, y los tres también se pueden ver con el final –sen.

Otros nombres incluyen:

• Puntaje F1
• Índice binario (no cuantitativo) de Czekanowski ^[3]
• Índice de similitud de Zijdenbos, ^[4] [5] refiriéndose a un artículo de 1994 de Zijdenbos et al. ^[6]

Fórmula [ editar ]

La fórmula original de Sørensen estaba destinada a aplicarse a datos discretos. Dados dos conjuntos, X e Y, se define como

$${\ displaystyle DSC = {\ frac {2 | X \ cap Y |} {| X | + | Y |}}}

donde | X | y | Y | son las cardinalidades de los dos conjuntos (es decir, el número de elementos en cada conjunto). El índice de Sørensen equivale al doble del número de elementos comunes a ambos conjuntos dividido por la suma del número de elementos en cada conjunto.

Cuando se aplica a datos booleanos, utilizando la definición de verdadero positivo (TP), falso positivo (FP) y falso negativo (FN), se puede escribir como

$${\ displaystyle DSC = {\ frac {2TP} {2TP + FP + FN}}}.

Es diferente del índice Jaccard que solo cuenta los verdaderos positivos una vez tanto en el numerador como en el denominador. DSC es el cociente de similitud y varía entre 0 y 1. ^[7] Se puede ver como una medida de similitud sobre conjuntos.

De manera similar al índice de Jaccard , el conjunto de operaciones se pueden expresar en términos de las operaciones vectoriales sobre vectores binarios una y b :

$${\ displaystyle s_ {v} = {\ frac {2 | {\ bf {{a} \ cdot {\ bf {{b} |}}}}} {| {\ bf {{a} | ^ {2} + | {\ bf {{b} | ^ {2}}}}}}}}

que da el mismo resultado sobre los vectores binarios y también da una métrica de similitud más general sobre los vectores en términos generales.

Para los conjuntos X e Y de palabras clave utilizadas en la recuperación de información , el coeficiente se puede definir como el doble de la información compartida (intersección) sobre la suma de cardinalidades: ^[8]

Cuando se toma como una medida de similitud de cadena , el coeficiente se puede calcular para dos cadenas, x e y usando bigrams de la siguiente manera: ^[9]

$${\ displaystyle s = {\ frac {2n_ {t}} {n_ {x} + n_ {y}}}}

donde n _t es el número de caracteres que se encuentra en Bigramas ambas cadenas, n _x es el número de Bigramas en cadena de x y n _y es el número de Bigramas en cadena y . Por ejemplo, para calcular la similitud entre:

night

nacht

Encontraríamos el conjunto de bigrams en cada palabra:

{ ni, ig, gh, ht}

{ na, ac, ch, ht}

Cada conjunto tiene cuatro elementos, y la intersección de estos dos conjuntos tiene sólo un elemento: ht.

Al insertar estos números en la fórmula, calculamos, s  = (2 · 1) / (4 + 4) = 0.25.

Diferencia de Jaccard [ editar ]

Este coeficiente no es muy diferente en forma del índice de Jaccard . De hecho, ambos son equivalentes en el sentido de que dado un valor para el coeficiente Sørensen-Dice$${\ displaystyle S}, se puede calcular el valor del índice Jaccard respectivo $${\ displaystyle J} y viceversa, usando las ecuaciones $${\ displaystyle J = S / (2-S)} y $${\ displaystyle S = 2J / (1 + J)}.

Dado que el coeficiente Sørensen-Dice no satisface la desigualdad del triángulo, puede considerarse una versión semimétrica del índice Jaccard. ^[3]

La función oscila entre cero y uno, como Jaccard. A diferencia de Jaccard, la función de diferencia correspondiente

$${\ displaystyle d = 1 - {\ frac {2 | X \ cap Y |} {| X | + | Y |}}}

no es una medida de distancia adecuada, ya que no posee la propiedad de la desigualdad triangular . ^[3] El contraejemplo más simple de esto está dado por los tres conjuntos {a}, {b} y {a, b}, siendo la distancia entre los dos primeros 1 y la diferencia entre el tercero y cada uno de los otros un tercio. Para satisfacer la desigualdad triangular, la suma de cualquier dos de estos tres lados debe ser mayor que o igual al lado restante. Sin embargo, la distancia entre {a} y {a, b} más la distancia entre {b} y {a, b} es igual a 2/3 y, por lo tanto, es menor que la distancia entre {a} y {b} que es 1.

Aplicaciones [ editar ]

El coeficiente Sørensen-Dice es útil para los datos de la comunidad ecológica (por ejemplo, Looman y Campbell, 1960 ^[10] ). La justificación para su uso es principalmente empírica más que teórica (aunque puede justificarse teóricamente como la intersección de dos conjuntos difusos ^[11] ). En comparación con la distancia euclidiana , la distancia de Sørensen conserva la sensibilidad en conjuntos de datos más heterogéneos y da menos peso a los valores atípicos. ^[12] Recientemente, el puntaje Dice (y sus variaciones, por ejemplo, logDice tomando un logaritmo del mismo) se ha vuelto popular en la lexicografía por computadora para medir el puntaje de asociación léxica de dos palabras dadas. ^[13] También se usa comúnmente en la segmentación de imágenes, en particular para comparar la salida del algoritmo con máscaras de referencia en aplicaciones médicas. ^[6]

Versión de abundancia [ editar ]

La expresión se extiende fácilmente a la abundancia en lugar de la presencia / ausencia de especies. Esta versión cuantitativa es conocida por varios nombres:

• Índice cuantitativo de Sørensen-Dice ^[3]
• Índice cuantitativo de Sørensen ^[3]
• Índice de dados cuantitativos ^[3]
• Similitud de Bray-Curtis (1 menos la disimilitud de Bray-Curtis ) ^[3]
• Índice cuantitativo de Czekanowski ^[3]
• Índice Steinhaus ^[3]
• El porcentaje de similitud de Pielou ^[3]
• 1 menos la distancia de Hellinger