Distancia de Levenshtein

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.

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. Está estrechamente relacionado con las alineaciones de cuerdas por pares.

Definición

La distancia de Levenshtein entre dos cuerdas a,b{displaystyle a,b} (de longitud) SilencioaSilencio{displaystyle Silencioso y SilenciobSilencio{displaystyle Silencioso respectivamente) Lev⁡ ⁡ ()a,b){displaystyle operatorname {lev} (a,b)} Donde

Lev⁡ ⁡ ()a,b)={}SilencioaSilenciosiSilenciobSilencio=0,SilenciobSilenciosiSilencioaSilencio=0,Lev⁡ ⁡ ()cola⁡ ⁡ ()a),cola⁡ ⁡ ()b))sia[0]=b[0],1+min{}Lev⁡ ⁡ ()cola⁡ ⁡ ()a),b)Lev⁡ ⁡ ()a,cola⁡ ⁡ ()b))Lev⁡ ⁡ ()cola⁡ ⁡ ()a),cola⁡ ⁡ ()b))de otra manera{fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Ser] {big} {big}fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {big} {big} {big} {big} {big} {big}\fnMicrosoft Sans Serif} {big} {fnMicrosoft Sans Serif} {fnMicrosoft} {fnMicrosoft}} {fnMicrosoft}}}}}}}}}fnMicrosoft Sanstop} {fnMicrox} {f}fnMinMicronombre}fnMicrosoft Sans}fnMicrosoft Sans}fnMicrosoft} {fnMinMicronombre}fnMicronombre}f}fnMicrosoft}f}f}fnun}fnMicrosoft}fnMicrosoft}fnMicrosoft}fnMicrosoft}f}fn

Donde cola{displaystyle operatorname {tail} de alguna cuerda x{displaystyle x} es una cuerda de todos pero el primer carácter x{displaystyle x}, y x[n]{displaystyle x[n]} es n{displaystyle n}t carácter de la cuerda x{displaystyle x}Contando desde cero.

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

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

Ejemplo

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. kitten → sitten (sustitución de "s" para "k"),
2. Siéntateen → sentarsein (sustitución de "i" para "e"),
3. sittin → sitting (inserción de "g" al final).

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 los tamaños de las dos cuerdas.
• Es a la mayor parte de la longitud de la cadena más larga.
• Es cero si y sólo si las cuerdas son iguales.
• Si las cuerdas tienen el mismo tamaño, la distancia Hamming es un límite superior en la distancia Levenshtein. La distancia Hamming es el número de posiciones en las que los símbolos correspondientes en las dos cuerdas son diferentes.
• La distancia de Levenshtein entre dos cuerdas no es mayor que la suma de sus distancias de Levenshtein de una tercera cadena (la 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 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. 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 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 la vinculación 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 a la inserción, eliminación, sustitución;
• la distancia de subsecuencia común más larga (LCS) permite sólo la inserción y eliminación, no sustitución;
• la distancia Hamming permite sólo sustitución, por lo tanto, sólo se aplica a las cadenas de la misma longitud.
• la distancia Jaro permite sólo 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 coste de una operación dependa de dónde se aplica.

Cálculo

Recursiva

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

IDistance :: Eq a = [a] - [a] - IntIDistance [] t = longitud t -- Si s está vacío, la distancia es el número de caracteres en tIDistance s [] = longitud s -- Si t está vacío, la distancia es el número de caracteres en sIDistance ()a : s ') ()b : t ') = si a == b entonces IDistance s ' t ' -- Si los primeros caracteres son los mismos, pueden ser ignorados más 1 + mínimo -- De lo contrario probar las tres acciones posibles y seleccionar el mejor [ IDistance ()a : s ') t ', -- Se inserta el carácter (b insertado) IDistance s ' ()b : t '), -- El carácter se elimina (se elimina) IDistance s ' t ' -- El carácter es reemplazado (sustituido por 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 puede ser almacenada en un array M{displaystyle M}, donde M[i][j]{displaystyle M[i][j] es la distancia entre la última i{displaystyle i} caracteres de cuerda s y el último j{displaystyle j} caracteres de cuerda t. La mesa 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, representando la distancia entre todos los caracteres en s y todos los personajes t.

Iterativo con matriz completa

(Nota: esta sección utiliza cadenas basadas en 1 en lugar de cadenas basadas en 0).

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 en una programación dinámica. moda, y así encontrar 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 cadena a cadena de Robert A. Wagner y Michael J. Fischer..

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

función Levenshtein Distancia()char s[1..m], char t[1..n]): // para todos i y j, d[i,j] mantendrá la distancia Levenshtein entre // los primeros personajes de s y los primeros j caracteres de t Declara int d[0..m, 0..n]  set cada uno elemento dentro d a cero  // prefijos de fuente se pueden transformar en cadena vacía por // dejar caer todos los caracteres para i desde 1 a m: d[i, 0] := i  // prefijos de destino se pueden alcanzar desde prefijo de fuente vacía // insertando cada personaje para j desde 1 a n: d[0, j] := j  para j desde 1 a n: para i desde 1 a m: si s[i] = t[j]: sustitución Costo := 0 más: sustitución 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] + sustitución Costo) // sustitución  retorno 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 s[1..i] en t[1..j] usando un mínimo de d[i, j] operaciones. Al final, el elemento inferior derecho de la matriz contiene la respuesta.

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:

función Levenshtein Distancia()char s[0..m-1], char t[0..n-1]): // crear dos vectores de trabajo de distancias enteros Declara int v0[n + 1] Declara int v1[n + 1] // inicializar v0 (la fila anterior de distancias) // esta fila es A[0][i]: editar distancia de una s vacía a t; // esa distancia es el número de caracteres para anexar a s para hacer t. para i desde 0 a n: v0[i] = i para i desde 0 a m - 1: // calcular v1 (distancias de filas corrientes) de la fila anterior v0 // primer elemento de v1 es A[i + 1][0] // editar distancia es eliminar (i + 1) chars de s a juego vacío t v1[0] = i + 1 // utilizar fórmula para llenar el resto de la fila para j desde 0 a n - 1: // calculando costos para A[i + 1][j + 1] eliminación Costo := v0[j + 1] + 1 inserción Costo := v1[j] + 1 si s[i] = t[j]: sustitución Costo := v0[j] más: sustitución Costo := v0[j] + 1 v1[j + 1] := mínimo()eliminación Costo, inserción Costo, sustitución Costo) // copiar v1 (rema actual) a v0 (rema anterior) para la próxima iteración // ya que los datos en v1 siempre están invalidados, un intercambio sin copia podría ser más eficiente Swap v0 con v1 // después del último swap, los resultados de v1 ahora están en v0 retorno v0[n]

Hirschberg 's algorithm combines this method with divide and conquer. It can compute the optimal edit sequence, and not just the edit distance, in the same asymptotic time and space bounds.

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.

Aproximación

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

()log⁡ ⁡ n)O()1/ε ε ),{displaystyle (log n)^{O(1/varepsilon)}

where ε > 0 is a free parameter to be tuned, in time 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 es falsa.