distancia de Levenshtein

Métrica informática para la similitud de cadenas

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 otra. Lleva el nombre del matemático soviético Vladimir Levenshtein , quien consideró esta distancia 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 amplia de métricas de distancia conocidas colectivamente como distancia de edición . ^{[2] : 32} Está estrechamente relacionado con las alineaciones de cadenas por pares .

Definición

La distancia de Levenshtein entre dos cuerdas (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 }}\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 de alguna cadena es una cadena de todos menos el primer carácter de , y es el primer carácter de . Ya sea la notación o se utiliza para hacer referencia al carácter enésimo de la cadena , contando desde 0 , por lo tanto . ${\displaystyle \operatorname {tail} }$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \operatorname {head} (x)}$ ${\displaystyle x}$ ${\displaystyle x[n]}$ ${\displaystyle x_{n}}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle \operatorname {head} (x)=x_{0}=x[0]}$

Tenga en cuenta que 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 a otra, y no hay manera de hacerlo con menos de 3 ediciones:

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

Un ejemplo simple de eliminación se puede ver con "desinformados" y "uniformados" 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. Éstas incluyen:

• Es al menos el valor absoluto de 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 sólo si las cadenas son iguales.
• Si las cuerdas 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 desde 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 da 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 proceder de un diccionario, por ejemplo. Aquí, una de las cadenas suele ser corta, mientras que la otra es arbitrariamente larga. 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 memorias 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 las cuerdas, 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 vinculación de registros , las cadenas comparadas suelen ser cortas para ayudar a mejorar la velocidad de las comparaciones. ^{[ cita necesaria ]}

En lingüística, la distancia de Levenshtein se utiliza como métrica para cuantificar la distancia lingüística , o qué tan diferentes son dos idiomas entre sí. ^[3] 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 (LCS) más larga solo permite la inserción y eliminación, no la sustitución;
• la distancia de Hamming sólo permite sustitución, por lo tanto, sólo se aplica a cuerdas de la misma longitud.
• la distancia de Jaro sólo 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 de 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 de Haskell sencilla, pero ineficiente, de una lDistancefunción que toma dos cadenas, s y t , junto con sus longitudes, y devuelve la distancia de Levenshtein entre ellas:

lDistance :: Eq a => [ a ] ​​-> [ a ] ​​-> Int lDistance [] t = longitud t -- Si s está vacío, la distancia es el número de caracteres en t lDistance s [] = longitud s -- Si t está vacío, la distancia es el número de caracteres en s lDistance ( a : s' ) ( b : t' ) = si a == b entonces lDistance s' t' -- Si los primeros caracteres son iguales, se puede ignorar de lo contrario 1 + mínimo - De lo contrario, pruebe las tres acciones posibles y seleccione la mejor [ lDistance ( a : s' ) t' , -- Se inserta el carácter (b insertado) lDistance s' ( b : t' ), -- Se elimina el carácter (a eliminado) lDistance s' t' -- Se reemplaza el 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 creado 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 y todos los caracteres. 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. Si m es una matriz, es la i - ésima fila y la j -ésima columna de la matriz, donde la primera fila tiene el índice 0 y la primera columna tiene el índice 0.) ${\displaystyle m[i,j]}$

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 en forma de programación dinámica , y así 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 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:

función LevenshteinDistance ( char s [ 1 .. m ] , char t [ 1 .. n ]) : // para todo 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 declaran int d [ 0 .. m , 0 .. n ] establecen cada elemento en d en cero // los prefijos fuente se pueden transformar en una cadena vacía // eliminando todos los caracteres para i de 1 a m : d [ i , 0 ] := i // los prefijos de destino se pueden alcanzar desde el prefijo de origen vacío // insertando 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 : 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 ) // retorno de sustitución d [ m , n ]                     

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

La invariante que se mantiene en todo el algoritmo es que podemos transformar el segmento inicial utilizando 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 sólo 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: ^[5]

función LevenshteinDistance ( char s [ 0 .. m - 1 ] , char t [ 0 .. n - 1 ]) : // crea dos vectores de trabajo de distancias enteras declara int v0 [ n + 1 ] declara 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 un t; // esa distancia es el número de caracteres que se deben agregar a s para formar t. para i de 0 a n : v0 [ i ] = i            para i de 0 a m - 1 : // calcula v1 (distancias de fila actuales) desde la fila anterior v0         // el primer elemento de v1 es A[i + 1][0] // editar la distancia es eliminar (i + 1) caracteres de s para que coincidan con t vacío v1 [ 0 ] = i + 1       // usa la fórmula para completar el resto de la fila para j de 0 a n - 1 : // calculando los 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 ( coste de eliminación , costo de inserción , costo de sustitució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 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 Levenshtein determinan de manera eficiente si una cadena tiene una distancia de edición menor que una constante determinada de una cadena determinada. ^[7]

Aproximación

La distancia de Levenshtein entre dos cuerdas 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 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. ^[9]

Ver también

• agrep
• Distancia Damerau-Levenshtein
• diferencia
• Deformación dinámica del tiempo
• distancia euclidiana
• Homología de secuencias en genética.
• distancia de Hamming
• Algoritmo de Hunt-Szymanski
• índice jaccard
• Hashing sensible a la localidad
• Problema de subsecuencia común más largo
• 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 óptimo
• 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 y reversiones". Física soviética Doklady . 10 (8): 707–710. Código bibliográfico : 1966SPhD...10..707L.
2. Navarro, Gonzalo (2001). "Una visita guiada para aproximar la coincidencia de cadenas" (PDF) . Encuestas de Computación ACM . 33 (1): 31–88. CiteSeerX 10.1.1.452.6317 . doi :10.1145/375360.375365. S2CID  207551224. 
3. Enero D. diez 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 mediante un sinónimo)... relación léxica... relación gramatical.
4. Wagner, Robert A.; Fischer, Michael J. (1974), "El problema de corrección de cadena a cadena", 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 con memoria eficiente.
6. Hirschberg, DS (1975). "Un algoritmo de espacio 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. SEÑOR  0375829. S2CID  207694727. 
7. Schulz, Klaus U.; Mihov, Stoyan (2002). "Corrección rápida de cuerdas con Levenshtein-Automata". 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, Alejandro; Krauthgamer, Robert; Onak, Krzysztof (2010). "Aproximación polilogarítmica para la distancia de edición y la complejidad de la consulta asimétrica ". Síntoma IEEE. Fundamentos de la Informática (FOCS). arXiv : 1005.4033 . Código Bib : 2010arXiv1005.4033A. CiteSeerX 10.1.1.208.2079 . 
9. Backurs, Arturos; 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 ACM sobre teoría de la computación (STOC). arXiv : 1412.0348 . Código Bib : 2014arXiv1412.0348B.

enlaces externos

• Negro, Paul E., ed. (14 de agosto de 2008), "Distancia de Levenshtein", Diccionario de algoritmos y estructuras de datos [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 Rosetta de la distancia de Levenshtein