Distancia de Levenshtein - Levenshtein distance

En teoría de la información , lingüística e informática , la distancia de Levenshtein es una métrica de cadena para medir la diferencia entre dos secuencias. De manera informal, la distancia de Levenshtein entre dos palabras es el número mínimo de ediciones de un solo carácter (inserciones, eliminaciones o sustituciones) necesarias para cambiar una palabra por la otra. Lleva el nombre del matemático soviético Vladimir Levenshtein , quien consideró esta distancia en 1965.

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 conocidas colectivamente como distancia de edición . Está estrechamente relacionado con las alineaciones de cadenas por pares .

Definición

La distancia de Levenshtein entre dos cadenas (de longitud y respectivamente) viene dada por donde ${\ Displaystyle a, b}$${\ Displaystyle | a |}$${\ Displaystyle | b |}$${\ Displaystyle \ operatorname {lev} (a, b)}$

${\ Displaystyle \ operatorname {lev} (a, b) = {\ begin {cases} | a | & {\ text {if}} | b | = 0, \\ | b | & {\ text {if}} | a | = 0, \\\ operatorname {lev} {\ big (} \ operatorname {tail} (a), \ operatorname {tail} (b) {\ big)} & {\ text {if}} a [ 0] = b [0] \\ 1+ \ min {\ begin {cases} \ operatorname {lev} {\ big (} \ operatorname {tail} (a), b {\ big)} \\\ operatorname {lev } {\ big (} a, \ operatorname {tail} (b) {\ big)} \\\ operatorname {lev} {\ big (} \ operatorname {tail} (a), \ operatorname {tail} (b) {\ big)} \\\ end {cases}} & {\ text {de lo contrario,}} \ end {cases}}}$

donde el de alguna cadena es una cadena de todos menos el primer carácter de , y es el ésimo carácter de la cadena , contando desde 0 . ${\ Displaystyle \ operatorname {tail}}$${\ Displaystyle x}$${\ Displaystyle x}$${\ Displaystyle x [n]}$${\ Displaystyle n}$${\ Displaystyle x}$

Tenga en cuenta que el primer elemento en el mínimo corresponde a la eliminación (de a ), el segundo a la inserción y el tercero a la sustitución. ${\ Displaystyle a}$${\ Displaystyle b}$

Esta definición corresponde directamente a la implementación recursiva ingenua .

Ejemplo

Edite la matriz de distancia para dos palabras usando el costo de sustitución como 1 y el costo de eliminación o inserción como 0.5

Por ejemplo, la distancia de Levenshtein entre "gatito" y "sentado" es 3, ya que las siguientes 3 ediciones cambian de una a otra, y no hay forma de hacerlo con menos de 3 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

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

• Es al menos la diferencia de tamaños de las dos cuerdas.
• Es como máximo la longitud de la cuerda más larga.
• Es cero si y solo si las cadenas son iguales.
• Si las cuerdas tienen el mismo tamaño, la distancia de Hamming es un límite superior en la distancia de Levenshtein. La distancia de Hamming es el número de posiciones en las que los símbolos correspondientes en las dos cadenas son diferentes.
• La distancia de Levenshtein entre dos cuerdas no es mayor que la suma de sus distancias de Levenshtein desde una tercera cuerda ( desigualdad de triángulo ).

Un ejemplo en el que la distancia de Levenshtein entre dos cuerdas de la misma longitud es estrictamente menor que la distancia de Hamming viene dada por el par "defecto" 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

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 una pequeña cantidad de diferencias. Las cadenas cortas podrían provenir de un diccionario, por ejemplo. Aquí, una de las cadenas suele ser 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 basada en la memoria de traducción .

La distancia de Levenshtein también se puede calcular entre dos cuerdas más largas, pero el costo de calcularla, que es aproximadamente proporcional al producto de las dos longitudes de cuerda, hace que esto no sea práctico. Por lo tanto, cuando se utilizan 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.

En lingüística, la distancia de Levenshtein se utiliza como métrica para cuantificar la distancia lingüística o cuán diferentes son dos idiomas entre sí. Está relacionado 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

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 y sustitución;
• la distancia de subsecuencia común más larga (LCS) permite solo la inserción y la 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 mediante 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 aplique.

Calcular la distancia de Levenshtein

Recursivo

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

lDistance :: ( Eq a ) => [a] -> [a] -> Int
lDistance [] t = length t   -- If s is empty, the distance is the number of characters in t
lDistance s [] = length s   -- If t is empty, the distance is the number of characters in s
lDistance (a:s') (b:t') =
  if
    a == b
  then
    lDistance s' t'         -- If the first characters are the same, they can be ignored
  else
    1 + minimum             -- Otherwise try all three possible actions and select the best one
      [ lDistance (a:s') t' -- Character is inserted (b inserted)
      , lDistance s' (b:t') -- Character is deleted  (a deleted)
      , lDistance s' t'     -- Character is replaced (a replaced with b)
      ]

Esta implementación es muy ineficaz 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 posibles prefijos podría almacenarse en una matriz , donde es la distancia entre los últimos caracteres de la cadena y los últimos 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 está en la tabla en la última fila y columna, que representa la distancia entre todos los caracteres en y todos los personajes en . ${\ Displaystyle M}$${\ Displaystyle M [i] [j]}$${\ Displaystyle i}$s${\ Displaystyle j}$tst

Iterativo con matriz completa

(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 contener 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 de una manera de programación dinámica , y por lo tanto, encuentre la distancia entre las dos cadenas completas como último valor calculado.

Este algoritmo, un ejemplo de programación dinámica ascendente , se analiza, con variantes, en el artículo de 1974 El problema de corrección de cuerda a cuerda de Robert A. Wagner y Michael J. Fischer.

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

function LevenshteinDistance(char s[1..m], char t[1..n]):
  // for all i and j, d[i,j] will hold the Levenshtein distance between
  // the first i characters of s and the first j characters of t
  declare int d[0..m, 0..n]
 
  set each element in d to zero
 
  // source prefixes can be transformed into empty string by
  // dropping all characters
  for i from 1 to m:
    d[i, 0] := i
 
  // target prefixes can be reached from empty source prefix
  // by inserting every character
  for j from 1 to n:
    d[0, j] := j
 
  for j from 1 to n:
    for i from 1 to m:
      if s[i] = t[j]:
        substitutionCost := 0
      else:
        substitutionCost := 1

      d[i, j] := minimum(d[i-1, j] + 1,                   // deletion
                         d[i, j-1] + 1,                   // insertion
                         d[i-1, j-1] + substitutionCost)  // substitution
 
  return 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):

La invariante que se mantiene a lo largo del 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

Resulta que solo se necesitan dos filas de la tabla, la fila anterior y la fila actual que se está calculando, para la construcción, si no se desea reconstruir las cadenas de entrada editadas.

La distancia de Levenshtein se puede calcular de forma iterativa utilizando el siguiente algoritmo:

function LevenshteinDistance(char s[0..m-1], char t[0..n-1]):
    // create two work vectors of integer distances
    declare int v0[n + 1]
    declare int v1[n + 1]

    // initialize v0 (the previous row of distances)
    // this row is A[0][i]: edit distance for an empty s
    // the distance is just the number of characters to delete from t
    for i from 0 to n:
        v0[i] = i

    for i from 0 to m - 1:
        // calculate v1 (current row distances) from the previous row v0

        // first element of v1 is A[i + 1][0]
        //   edit distance is delete (i + 1) chars from s to match empty t
        v1[0] = i + 1

        // use formula to fill in the rest of the row
        for j from 0 to n - 1:
            // calculating costs for A[i + 1][j + 1]
            deletionCost := v0[j + 1] + 1
            insertionCost := v1[j] + 1
            if s[i] = t[j]:
                substitutionCost := v0[j]
            else:
                substitutionCost := v0[j] + 1

            v1[j + 1] := minimum(deletionCost, insertionCost, substitutionCost)

        // copy v1 (current row) to v0 (previous row) for next iteration
        // since data in v1 is always invalidated, a swap without copy could be more efficient
        swap v0 with v1
    // after the last swap, the results of v1 are now in v0
    return v0[n]

Esta variante de dos filas es subóptima: la cantidad de memoria requerida puede reducirse a una fila y una palabra (índice) de sobrecarga, para una mejor ubicación de la caché.

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.

Variante adaptativa

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, a no más que cuadrática en la longitud de la cadena más corta. . La idea es que uno puede usar funciones de biblioteca eficientes ( std::mismatch) para verificar prefijos y sufijos comunes y solo sumergirse en la parte de DP sobre la falta de coincidencia.

Autómatas

Los autómatas de Levenshtein determinan de manera eficiente si una cadena tiene una distancia de edición menor que una constante dada de una cadena dada.

Aproximación

La distancia de Levenshtein entre dos cadenas de longitud n se puede aproximar dentro de un factor

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

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

Complejidad computacional

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.

Ver también

Referencias

enlaces externos

• Black, Paul E., ed. (14 de agosto de 2008), "Levenshtein distance", Dictionary of Algorithms and Data Structures [en línea] , Instituto Nacional de Estándares y Tecnología de EE. UU. , Consultado el 2 de noviembre de 2016
• Implementaciones del Código Rosseta de la distancia de Levenshtein