LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

 distancia Jaro-Winkler es una métrica de cadena que mide una distancia de edición entre dos secuencias. Es una variante propuesta en 1990 por William E. Winkler de la métrica de distancia Jaro (1989, Matthew A. Jaro ).

La distancia Jaro-Winkler usa una escala de prefijo$${\ displaystyle p} que otorga calificaciones más favorables a las cadenas que coinciden desde el principio para una longitud de prefijo establecida $${\ displaystyle \ ell}.

Cuanto menor es la distancia Jaro-Winkler para dos cadenas, más similares son las cadenas. La puntuación se normaliza de modo que 1 equivale a ninguna similitud y 0 es una coincidencia exacta. La similitud de Jaro-Winkler es la inversión, (1 - distancia de Jaro-Winkler).

Aunque a menudo se la conoce como métrica de distancia , la distancia Jaro-Winkler no es una métrica en el sentido matemático de ese término porque no obedece a la desigualdad del triángulo .

Definición [ editar ]

Similitud de Jaro [ editar ]

La similitud de Jaro $${\ displaystyle sim_ {j}} de dos cadenas dadas $${\ displaystyle s_ {1}} y $${\ displaystyle s_ {2}} es

{\ displaystyle sim_ {j} = \ left \ {{\ begin {array} {ll} 0 & {\ text {if}} m = 0 \\ {\ frac {1} {3}} \ left ({\ frac {m} {| s_ {1} |}} + {\ frac {m} {| s_ {2} |}} + {\ frac {mt} {m}} \ right) & {\ text {si no}} \ end {array}} \ right.}

Dónde:

• $${\ displaystyle | s_ {i} |} es la longitud de la cuerda $${\ displaystyle s_ {i}};
• $${\ displaystyle m}es el número de caracteres coincidentes (ver más abajo);
• $${\ displaystyle t}es la mitad del número de transposiciones (ver más abajo).

Dos personajes de $${\ displaystyle s_ {1}} y $${\ displaystyle s_ {2}}respectivamente, se consideran coincidentes solo si son iguales y no más allá de$${\ displaystyle \ left \ lfloor {\ frac {\ max (| s_ {1} |, | s_ {2} |)} {2}} \ right \ rfloor -1}.

Cada personaje de $${\ displaystyle s_ {1}} se compara con todos sus caracteres coincidentes en $${\ displaystyle s_ {2}}. El número de caracteres coincidentes (pero con un orden de secuencia diferente) dividido por 2 define el número de transposiciones . Por ejemplo, al comparar CRATE con TRACE, solo 'R' 'A' 'E' son los caracteres coincidentes, es decir, m = 3. Aunque 'C', 'T' aparecen en ambas cadenas, están más allá de 1 (el resultado de$${\ displaystyle \ lfloor {\ tfrac {5} {2}} \ rfloor -1}) Por lo tanto, t = 0. En DwAyNE versus DuANE, las letras coincidentes ya están en el mismo orden DANE, por lo que no se necesitan transposiciones.

Similitud Jaro-Winkler [ editar ]

La similitud de Jaro-Winkler usa una escala de prefijo$${\ displaystyle p} que otorga calificaciones más favorables a las cadenas que coinciden desde el principio para una longitud de prefijo establecida $${\ displaystyle \ ell}. Dadas dos cuerdas$${\ displaystyle s_ {1}} y $${\ displaystyle s_ {2}}, su similitud Jaro-Winkler $${\ displaystyle sim_ {w}} es:

$${\ displaystyle sim_ {w} = sim_ {j} + \ ell p (1-sim_ {j}),}

dónde:

• $${\ displaystyle sim_ {j}} es la similitud de Jaro para cadenas $${\ displaystyle s_ {1}} y $${\ displaystyle s_ {2}}
• $${\ displaystyle \ ell} es la longitud del prefijo común al comienzo de la cadena hasta un máximo de cuatro caracteres
• $${\ displaystyle p}es un factor de escala constante de cuánto se ajusta la puntuación hacia arriba por tener prefijos comunes.$${\ displaystyle p} no debe exceder 0.25, de lo contrario la similitud podría ser mayor que 1. El valor estándar para esta constante en el trabajo de Winkler es $${\ displaystyle p = 0.1}

La distancia Jaro-Winkler $${\ displaystyle d_ {w}} Se define como $${\ displaystyle d_ {w} = 1-sim_ {w}}.

Aunque a menudo se la conoce como métrica de distancia , la distancia Jaro-Winkler no es una métrica en el sentido matemático de ese término porque no obedece a la desigualdad del triángulo . ^[1] La distancia Jaro-Winkler tampoco satisface el axioma de identidad$${\ displaystyle d (x, y) = 0 \ leftrightarrow x = y}.

Relación con otras métricas de distancia de edición [ editar ]

Artículo principal: Editar distancia

Existen otras medidas populares de distancia de edición , que se calculan utilizando un conjunto diferente de operaciones de edición permitidas. Por ejemplo,

• la distancia de Levenshtein permite la eliminación, inserción y sustitución;
• la distancia Damerau-Levenshtein permite la inserción, eliminación, sustitución y transposición de dos caracteres adyacentes;
• la distancia de subsecuencia común más larga (LCS) permite solo la inserción y eliminación, no la sustitución;
• la distancia de Hamming solo permite la sustitución, por lo tanto, solo se aplica a cuerdas de la misma longitud.

La distancia de edición generalmente se define 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 costo (posiblemente infinito). Esto se generaliza aún más por los algoritmos de alineación de secuencias de ADN , como el algoritmo Smith-Waterman , que hacen que el costo de una operación dependa de dónde se aplica.

distancia de Levenshtein es una métrica de cuerda para medir la diferencia entre dos secuencias. Informalmente, la distancia de Levenshtein entre dos palabras es el número mínimo de ediciones de un solo carácter (inserciones, eliminaciones o sustituciones) requeridas para cambiar una palabra en la otra. Lleva el nombre del matemático soviético Vladimir Levenshtein , quien consideró esta distancia en 1965. ^[1]

La distancia de Levenshtein también se puede denominar distancia de edición , aunque ese término también puede denotar una familia más grande de métricas de distancia . ^[2] : 32 Está estrechamente relacionado con las alineaciones de cadenas por pares .

Definición [ editar ]

La distancia de Levenshtein entre dos cuerdas $${\ displaystyle a, b} (de longitud $${\ displaystyle | a |} y $${\ displaystyle | b |} respectivamente) está dado por $${\ displaystyle \ operatorname {lev} _ {a, b} (| a |, | b |)} dónde

{\ displaystyle \ qquad \ operatorname {lev} _ {a, b} (i, j) = {\ begin {cases} \ max (i, j) & {\ text {if}} \ min (i, j) = 0, \\\ min {\ begin {cases} \ operatorname {lev} _ {a, b} (i-1, j) +1 \\\ operatorname {lev} _ {a, b} (i, j -1) +1 \\\ operatorname {lev} _ {a, b} (i-1, j-1) +1 _ {(a_ {i} \ neq b_ {j})} \ end {cases}} & {\ text {de lo contrario.}} \ end {cases}}}

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, y $${\ displaystyle \ operatorname {lev} _ {a, b} (i, j)} es la distancia entre el primero $${\ displaystyle i} personajes de $${\ displaystyle a} y el primero $${\ displaystyle j} personajes de $${\ displaystyle b}.

Tenga en cuenta que el primer elemento en el mínimo corresponde a la eliminación (de $${\ displaystyle a} a $${\ displaystyle b}), el segundo para la inserción y el tercero para que coincida o no coincida, dependiendo de si los símbolos respectivos son los mismos.

Ejemplo [ editar ]

Por ejemplo, la distancia de Levenshtein entre "gatito" y "sentado" es 3, ya que las siguientes tres ediciones cambian de una a otra, y no hay forma de hacerlo con menos de tres ediciones:

1. k itten → s itten (sustitución de "s" por "k")
2. sitt e n → sitt i n (sustitución de "i" por "e")
3. sittin → sittin g (inserción de "g" al final).

Límites superior e inferior [ editar ]

La distancia de Levenshtein tiene varios límites superiores e inferiores simples. Éstos incluyen:

• Es al menos la diferencia de los tamaños de las dos cadenas.
• Es como máximo la longitud de la cadena más larga.
• Es cero si y solo si las cadenas son iguales.
• Si las cadenas son del mismo tamaño, la distancia de Hamming es un límite superior en la distancia de Levenshtein.
• La distancia de Levenshtein entre dos cadenas no es mayor que la suma de sus distancias de Levenshtein desde una tercera cadena ( desigualdad triangular ).

Un ejemplo donde la distancia de Levenshtein entre dos cuerdas de la misma longitud es estrictamente menor que la distancia de Hamming es dada por el par "falla" y "césped". Aquí la distancia de Levenshtein es igual a 2 (elimine "f" del frente; inserte "n" al final). La distancia de Hamming es 4.

Aplicaciones [ editar ]

En la coincidencia aproximada de cadenas , el objetivo es encontrar coincidencias para cadenas cortas en muchos textos más largos, en situaciones en las que se espera un pequeño número de diferencias. Las cadenas cortas podrían provenir de un diccionario, por ejemplo. Aquí, una de las cadenas es típicamente corta, mientras que la otra es arbitrariamente larga. Esto tiene una amplia gama de aplicaciones, por ejemplo, correctores ortográficos , sistemas de corrección para el reconocimiento óptico de caracteres y software para ayudar a la traducción del lenguaje natural basado en la memoria de traducción .

La distancia de Levenshtein también se puede calcular entre dos cadenas más largas, pero el costo para calcularla, que es aproximadamente proporcional al producto de las dos longitudes de cadena, hace que esto sea poco práctico. Por lo tanto, cuando se usa para ayudar en la búsqueda de cadenas difusas en aplicaciones como el enlace de registros , las cadenas comparadas suelen ser cortas para ayudar a mejorar la velocidad de las comparaciones. ^{[ cita requerida ]}

En lingüística, la distancia de Levenshtein se usa como una métrica para cuantificar la distancia lingüística , o cuán diferentes son dos idiomas entre sí. ^[3] Se relaciona con la inteligibilidad mutua , cuanto mayor es la distancia lingüística, menor es la inteligibilidad mutua y cuanto menor es la distancia lingüística, mayor es la inteligibilidad mutua.

Relación con otras métricas de distancia de edición [ editar ]

Artículo principal: Editar distancia

Existen otras medidas populares de distancia de edición , que se calculan utilizando un conjunto diferente de operaciones de edición permitidas. Por ejemplo,

• la distancia Damerau-Levenshtein permite la transposición de dos caracteres adyacentes junto con la inserción, eliminación, sustitución;
• la distancia de subsecuencia común más larga (LCS) permite solo la inserción y eliminación, no la sustitución;
• la distancia de Hamming solo permite la sustitución, por lo tanto, solo se aplica a cuerdas de la misma longitud.
• la distancia de Jaro solo permite la transposición .

La distancia de edición generalmente se define 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 costo (posiblemente infinito). Esto se generaliza aún más por los algoritmos de alineación de secuencias de ADN , como el algoritmo Smith-Waterman , que hacen que el costo de una operación dependa de dónde se aplica.

Calculando la distancia de Levenshtein [ editar ]

Recursivo [ editar ]

Este es un sencillo, pero ineficaz, recursivo C implementación de una LevenshteinDistancefunción que toma dos cadenas, s y t , junto con sus longitudes, y devuelve la distancia Levenshtein entre ellos:

// len_s y len_t son el número de caracteres en la cadena syt respectivamente 
int  LevenshteinDistance ( const  char  * s ,  int  len_s ,  const  char  * t ,  int  len_t ) 
{  
  int  cost ;

  / * caso base: cadenas vacías * / 
  if  ( len_s  ==  0 )  return  len_t ; 
  if  ( len_t  ==  0 )  devuelve  len_s ;

  / * prueba si los últimos caracteres de las cadenas coinciden * / 
  if  ( s [ len_s - 1 ]  ==  t [ len_t - 1 ]) 
      cost  =  0 ; 
  más 
      costo  =  1 ;

  / * devolver mínimo de eliminar char de s, eliminar char de t, y eliminar char de ambos * / 
  return  mínimo ( LevenshteinDistance ( s ,  len_s  -  1 ,  t ,  len_t     )  +  1 , 
                 LevenshteinDistance ( s ,  len_s     ,  t ,  len_t  -  1 )  +  1 , 
                 LevenshteinDistance ( s ,  len_s  -  1 ,  t ,  len_t  -  1 ) +  costo ); 
}

Esta implementación es muy ineficiente porque vuelve a calcular la distancia de Levenshtein de las mismas subcadenas muchas veces.

Un método más eficiente nunca repetiría el mismo cálculo de distancia. Por ejemplo, la distancia de Levenshtein de todos los prefijos posibles podría almacenarse en una matriz donde está la distancia entre los primeros caracteres de la cadena y los primeros caracteres de la cadena . La tabla es fácil de construir una fila a la vez comenzando con la fila 0. Cuando se ha construido toda la tabla, la distancia deseada es . d[][]d[i][j]isjtd[len_s][len_t]

Iterativo con matriz completa [ editar ]

Artículo principal: algoritmo Wagner-Fischer

Nota: Esta sección utiliza cadenas basadas en 1 en lugar de cadenas basadas en 0

Calcular la distancia de Levenshtein se basa en la observación de que si reservamos una matriz para mantener las distancias de Levenshtein entre todos los prefijos de la primera cadena y todos los prefijos de la segunda, entonces podemos calcular los valores en la matriz en una forma de programación dinámica , y así encuentre la distancia entre las dos cadenas completas como el último valor calculado.

Este algoritmo, un ejemplo de programación dinámica de abajo hacia arriba , se discute, con variantes, en el artículo de 1974 El problema de corrección de cadena a cadena de Robert A. Wagner y Michael J. Fischer. ^[4]

Esta es una implementación pseudocódigo sencillo para una función LevenshteinDistanceque toma dos cadenas, s de longitud m , y t de longitud n , y devuelve la distancia Levenshtein entre ellos:

función  LevenshteinDistance ( char  s [ 1 .. m ],  char  t [ 1 .. n ]) : 
  // para todos i y j, d [i, j] mantendrá la distancia de Levenshtein entre 
  // los primeros i caracteres de s y los primeros j caracteres de t 
  // tenga en cuenta que d tiene (m + 1) * (n + 1) los valores 
  declaran  int  d [ 0 .. m ,  0 .. n ]
 
  establecer  cada  elemento  en  d  a  cero
 
  // los prefijos de origen se pueden transformar en una cadena vacía 
  // soltando todos los caracteres 
  para  i  de  1  a  m : 
      d [ i ,  0 ]  : =  i
 
  // se pueden alcanzar los prefijos de destino desde el prefijo de origen vacío 
  // insertando todos los caracteres 
  para  j  de  1  a  n : 
      d [ 0 ,  j ]  : =  j
 
  para  j  de  1  a  n : 
      para  i  de  1  a  m : 
          si  s [ i ]  =  t [ j ] : 
            costo de sustitución  : =  0 
          más : 
            costo de sustitución  : =  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 de sustitución )   // sustitución
 
  retorno  d [ m ,  n ]

Dos ejemplos de la matriz resultante (al pasar el cursor sobre un número etiquetado se revela la operación realizada para obtener ese número):

k yo t t mi norte 0 0 1 2 3 4 4 5 5 6 6 s 1 1 2 3 4 4 5 5 6 6 yo 2 2 1 2 3 4 4 5 5 t 3 3 2 1 2 3 4 4 t 4 4 4 4 3 2 1 2 3 yo 5 5 5 5 4 4 3 2 2 3 norte 6 6 6 6 5 5 4 4 3 3 2 sol 7 7 7 7 6 6 5 5 4 4 4 4 3

S una t tu r re una y 0 0 1 2 3 4 4 5 5 6 6 7 7 8 S 1 0 0 1 2 3 4 4 5 5 6 6 7 7 tu 2 1 1 2 2 3 4 4 5 5 6 6 norte 3 2 2 2 3 3 4 4 5 5 6 6 re 4 4 3 3 3 3 4 4 3 4 4 5 5 una 5 5 4 4 3 4 4 4 4 4 4 4 4 3 4 4 y 6 6 5 5 4 4 4 4 5 5 5 5 5 5 4 4 3

La invariante mantenida en todo el algoritmo es que podemos transformar el segmento inicial en un mínimo de operaciones. Al final, el elemento inferior derecho de la matriz contiene la respuesta. s[1..i]t[1..j]d[i,j]

Iterativo con dos filas de matriz [ editar ]

Resulta que solo se necesitan dos filas de la tabla para la construcción si no se desea reconstruir las cadenas de entrada editadas (se calcula la fila anterior y la fila actual).

La distancia de Levenshtein se puede calcular iterativamente usando el siguiente algoritmo: ^[5]

función  LevenshteinDistance ( char  s [ 0 .. m - 1 ],  char  t [ 0 .. n - 1 ]) : 
    // crea dos vectores de trabajo de distancias enteras 
    declarar  int  v0 [ n  +  1 ] 
    declarar  int  v1 [ n  +  1 ]

    // inicializa v0 (la fila de distancias anterior) 
    // esta fila es A [0] [i]: edita la distancia para una s vacía 
    // la distancia es solo el número de caracteres que se eliminarán de t 
    para  i  de  0  a  n : 
        v0 [ i ]  =  i

    para  i  de  0  a  m - 1 : 
        // calcular v1 (distancias de fila actuales) de la fila anterior v0

        // el primer elemento de v1 es A [i + 1] [0] 
        // la distancia de edición es eliminar (i + 1) caracteres de s para que coincidan con t 
        v1 [ 0 ]  =  i  +  1

        // usa la fórmula para completar el resto de la fila 
        para  j  de  0  a  n - 1 : 
            // calculando costos para A [i + 1] [j + 1] 
            deletionCost  : =  v0 [ j  +  1 ]  +  1 
            insertionCost  : =  v1 [ j ]  +  1 
            si  s [ i ]  =  t [ j ] : 
                costo de sustitución  : =  v0 [ j ] 
            más :
                 costo de sustitución : =  v0 [ j ]  +  1 ;

            v1 [ j  +  1 ]  : =  mínimo ( deletionCost ,  insertionCost ,  substitutionCost )

        // copia v1 (fila actual) a v0 (fila anterior) para el siguiente 
        intercambio de  iteración v0  con  v1 
    // después del último intercambio, los resultados de v1 ahora están en v0 
    devuelven  v0 [ n ]

Esta variante de dos filas es subóptima: la cantidad de memoria requerida puede reducirse a una fila y una palabra de sobrecarga. ^[6]

El algoritmo de Hirschberg combina este método con divide y vencerás . Puede calcular la secuencia de edición óptima, y ​​no solo la distancia de edición, en los mismos límites de tiempo y espacio asintóticos. ^[7]

Variante adaptativa [ editar ]

La variante dinámica no es la implementación ideal. Un enfoque adaptativo puede reducir la cantidad de memoria requerida y, en el mejor de los casos, puede reducir la complejidad del tiempo a lineal en la longitud de la cadena más corta y, en el peor de los casos, no más que cuadrática en la longitud de la cadena más corta . ^[8]

Aproximación [ editar ]

La distancia de Levenshtein entre dos cadenas de longitud n puede aproximarse a un factor

$${\ displaystyle (\ log n) ^ {O (1 / \ varepsilon)}}

donde ε > 0 es un parámetro libre para sintonizar, en el tiempo O (n ^{1 + ε} ) . ^[9]

Complejidad computacional [ editar ]

Se ha demostrado que la distancia de Levenshtein de dos cadenas de longitud n no se puede calcular en el tiempo O (n ^{2 - ε} ) para cualquier ε mayor que cero a menos que la hipótesis del tiempo exponencial fuerte sea ​​falsa.