Distancia de Levenshtein

Métrica informática para la similitud de cadenas

En teoría de la información , lingüística y ciencias de la computación , la distancia de Levenshtein es una métrica de cadena para medir la diferencia entre dos secuencias. 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 otra. Recibe su nombre en honor al matemático soviético Vladimir Levenshtein , quien definió la métrica en 1965. ^[1]

La distancia de Levenshtein también puede denominarse 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 . ^{[2] : 32} Está estrechamente relacionada con las alineaciones de cadenas por pares .

Definición

La distancia de Levenshtein entre dos cuerdas (de longitud y respectivamente) está 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 }}\operatorname {head} (a)=\operatorname {head} (b),\\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{ otherwise}}\end{cases}}}$

donde el de alguna cadena es una cadena de todos los caracteres excepto el primero de (ie ), y es el primer carácter de (ie ). Se utiliza la notación o para hacer referencia al carácter n de la cadena , contando desde 0 , por lo tanto . ${\displaystyle \operatorname {tail} }$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \operatorname {tail} (x_{0}x_{1}\dots x_{n})=x_{1}x_{2}\dots x_{n}}$ ${\displaystyle \operatorname {head} (x)}$ ${\displaystyle x}$ ${\displaystyle \operatorname {head} (x_{0}x_{1}\dots x_{n})=x_{0}}$ ${\displaystyle x[n]}$ ${\displaystyle x_{n}}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle \operatorname {head} (x)=x_{0}=x[0]}$

El primer elemento del 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 una en la 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. sentado → sentado g (inserción de "g" al final).

Un ejemplo sencillo de eliminación se puede ver con "desinformado" y "uniformado" que tienen una distancia de 1:

1. uni n formado → uniformado (eliminación de "n").

Límites superior e inferior

La distancia de Levenshtein tiene varios límites superiores e inferiores simples, entre los que se incluyen:

• Es al menos el valor absoluto de la diferencia de los tamaños de las dos cadenas.
• Es como máximo la longitud de la cuerda más larga.
• Es cero si y sólo si las cadenas son iguales.
• Si las cadenas tienen el mismo tamaño, la distancia de Hamming es un límite superior de 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 a una tercera cuerda ( desigualdad triangular ).

Un ejemplo en el que la distancia de Levenshtein entre dos cuerdas de la misma longitud es estrictamente menor que la distancia de Hamming lo proporciona el par "flaw" y "lawn". En este caso, la distancia de Levenshtein es igual a 2 (elimine la "f" del principio; inserte la "n" al final). La distancia de Hamming es 4.

Aplicaciones

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

La distancia de Levenshtein también se puede calcular entre dos cadenas más largas, pero el costo de calcularla, que es aproximadamente proporcional al producto de las longitudes de las dos cadenas, hace que esto sea poco práctico. Por lo tanto, cuando se utiliza para ayudar en la búsqueda de cadenas difusas en aplicaciones como la vinculación 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 utiliza como una métrica para cuantificar la distancia lingüística , o cuán diferentes son dos idiomas entre sí. ^[3] Está relacionada con la inteligibilidad mutua : cuanto mayor sea la distancia lingüística, menor será la inteligibilidad mutua, y cuanto menor sea la distancia lingüística, mayor será 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) solo permite inserción y eliminación, no sustitución;
• La distancia de Hamming solo permite sustitución, por lo tanto, solo se aplica a cadenas de la misma longitud.
• La distancia de Jaro solo permite la transposición .

La distancia de edición suele definirse 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 alineamiento de secuencias de ADN como el algoritmo Smith-Waterman , que hacen que el costo de una operación dependa de dónde se aplica.

Cálculo

Recursivo

Esta es una implementación recursiva sencilla, pero ineficiente, de HaskelllDistance de una función que toma dos cadenas, s y t , junto con sus longitudes, y devuelve la distancia de Levenshtein entre ellas:

lDistancia :: Eq a => [ a ] ​​-> [ a ] ​​-> Int lDistancia [] t = length t -- Si s está vacío, la distancia es el número de caracteres en t lDistancia s [] = length s -- Si t está vacío, la distancia es el número de caracteres en s lDistancia ( a : s' ) ( b : t' ) = if a == b then lDistancia s' t' -- Si los primeros caracteres son iguales, se pueden ignorar de lo contrario 1 + mínimo -- De lo contrario, pruebe las tres acciones posibles y seleccione la mejor [ lDistancia ( a : s' ) t' , -- Se inserta un carácter (b se inserta) lDistancia s' ( b : t' ), -- Se elimina un carácter (a se elimina) lDistancia s' t' -- Se reemplaza un carácter (a se reemplaza con b) ]                                                            

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 sufijos posibles 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, lo que representa la distancia entre todos los caracteres de y todos los caracteres de . ${\displaystyle M}$ ${\displaystyle M[i][j]}$ ${\displaystyle i}$s ${\displaystyle j}$tst

Iterativo con matriz completa

En esta sección se utilizan cadenas basadas en 1 en lugar de cadenas basadas en 0. Si m es una matriz, es la fila i y la columna j de la matriz, siendo la primera fila la que tiene índice 0 y la primera columna la que tiene índice 0. ${\displaystyle m[i,j]}$

El cálculo de 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 así encontrar 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 analiza, con variantes, en el artículo de 1974 The String-to-string correction problem de Robert A. Wagner y Michael J. Fischer. ^[4]

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

function LevenshteinDistance ( char s [ 1..m ] , char t [ 1..n ] ) : // para todos los i y j, d [ i,j] contendrá la distancia de Levenshtein entre los primeros i caracteres de s y los primeros j caracteres de t declare int d [ 0..m , 0..n ] establece cada elemento en d en cero // los prefijos de origen se pueden transformar en una cadena vacía al eliminar todos los caracteres para i de 1 a m : d [ i , 0 ] : = i // los prefijos de destino se pueden alcanzar desde un prefijo de origen vacío al insertar cada carácter para j de 1 a n : d [ 0 , j ] := j para j de 1 a n : para i de 1 a m : if s [ i ] = t [ j ] : substitutionCost := 0 else : substitutionCost := 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 ] + costoDeSustitución ) // sustitución 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 número con 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 uno no desea reconstruir las cadenas de entrada editadas.

La distancia de Levenshtein se puede calcular iterativamente utilizando 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 declare int v0 [ n + 1 ] declare int v1 [ n + 1 ]                // inicializa v0 (la fila anterior de distancias) // esta fila es A[0][i]: edita la distancia desde un s vacío hasta t; // esa distancia es la cantidad de caracteres que se deben agregar a s para formar t. para i desde 0 hasta n : v0 [ i ] = i            para i de 0 a m - 1 : // calcula v1 (distancias de fila actual) a partir 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 coincida con t vacío v1 [ 0 ] = i + 1       // usa la fórmula para completar el resto de la fila para j desde 0 hasta n - 1 : // calculando costos para 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 ] := mínimo ( costedeeliminación , costedeinserción , costedesustitución )       // copiar v1 (fila actual) a v0 (fila anterior) para la siguiente iteración // dado que los datos en v1 siempre se invalidan, un intercambio sin copia podría ser más eficiente intercambiar v0 con v1 // después del último intercambio, los resultados de v1 ahora están en v0 return v0 [ n ]        

El algoritmo de Hirschberg combina este método con el de 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 asintóticos de tiempo y espacio. ^[6]

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 desde una cadena dada. ^[7]

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 ajustar, en el tiempo O ( n ^{1 + ε} ) . ^[8]

Complejidad computacional

Se ha demostrado que la distancia de Levenshtein de dos cuerdas 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. ^[9]

Véase también

• de acuerdo
• Distancia Damerau-Levenshtein
• diferencia
• Deformación temporal dinámica
• Distancia euclidiana
• Homología de secuencias en genética
• Distancia de Hamming
• Algoritmo de Hunt-Szymanski
• Índice de Jaccard
• Distancia Jaro-Winkler
• Hashing sensible a la localidad
• Problema de la subsecuencia común más larga
• Lucene (un motor de búsqueda de código abierto que implementa la distancia de edición)
• Distancia de Manhattan
• Espacio métrico
• MinHash
• Algoritmo de coincidencia óptima
• Taxonomía numérica
• Índice de similitud de Sørensen

Referencias

1. B. И. Levènstein (1965). Двоичные коды с исправлением выпадений, вставок и замещений символов [Códigos binarios capaces de corregir eliminaciones, inserciones y reversiones]. Доклады Академии Наук СССР (en ruso). 163 (4): 845–848.Apareció en inglés como: Levenshtein, Vladimir I. (febrero de 1966). "Códigos binarios capaces de corregir eliminaciones, inserciones e inversiones". Soviet Physics Doklady . 10 (8): 707–710. Bibcode :1966SPhD...10..707L.
2. Navarro, Gonzalo (2001). "Una visita guiada a la aproximación de la correspondencia de cadenas" (PDF) . ACM Computing Surveys . 33 (1): 31–88. CiteSeerX 10.1.1.452.6317 . doi :10.1145/375360.375365. S2CID  207551224. 
3. Jan D. ten Thije; Ludger Zeevaert (1 de enero de 2007), Multilingüismo receptivo: análisis lingüísticos, políticas lingüísticas y conceptos didácticos, John Benjamins Publishing Company, ISBN 978-90-272-1926-8, Suponiendo que la inteligibilidad está inversamente relacionada con la distancia lingüística... las palabras de contenido el porcentaje de cognados (relacionados directamente o a través de un sinónimo)... relación léxica... relación gramatical.
4. Wagner, Robert A.; Fischer, Michael J. (1974), "El problema de corrección de cuerda a cuerda", Journal of the ACM , 21 (1): 168–173, doi : 10.1145/321796.321811 , S2CID  13381535
5. Hjelmqvist, Sten (26 de marzo de 2012), Algoritmo de Levenshtein rápido y eficiente en el uso de la memoria.
6. Hirschberg, DS (1975). "Un algoritmo espacial lineal para calcular subsecuencias comunes máximas" (PDF) . Comunicaciones de la ACM (manuscrito enviado). 18 (6): 341–343. CiteSeerX 10.1.1.348.4774 . doi :10.1145/360825.360861. MR  0375829. S2CID  207694727. 
7. Schulz, Klaus U.; Mihov, Stoyan (2002). "Corrección rápida de cadenas con autómatas de Levenshtein". Revista internacional de análisis y reconocimiento de documentos . 5 (1): 67–85. CiteSeerX 10.1.1.16.652 . doi :10.1007/s10032-002-0082-8. S2CID  207046453. 
8. Andoni, Alexandr; Krauthgamer, Robert; Onak, Krzysztof (2010). Aproximación polilogarítmica para la distancia de edición y la complejidad asimétrica de la consulta . IEEE Symp. Foundations of Computer Science (FOCS). arXiv : 1005.4033 . Bibcode :2010arXiv1005.4033A. CiteSeerX 10.1.1.208.2079 . 
9. Backurs, Arturs; Indyk, Piotr (2015). Editar La distancia no se puede calcular en tiempo fuertemente subcuadrático (a menos que SETH sea falso) . Cuadragésimo séptimo simposio anual de la ACM sobre teoría de la computación (STOC). arXiv : 1412.0348 . Código Bibliográfico :2014arXiv1412.0348B.

Enlaces externos

• Black, Paul E., ed. (14 de agosto de 2008), "Distancia de Levenshtein", Dictionary of Algorithms and Data Structures [en línea], US National Institute of Standards and Technology , consultado el 2 de noviembre de 2016
• Implementaciones de la distancia de Levenshtein en el código Rosetta