Distancia de Levenshtein

La distancia de Levenshtein es una métrica que cuantifica la diferencia entre dos cadenas de caracteres o, de forma más general, entre dos secuencias finitas de símbolos. En su definición clásica, corresponde al número mínimo de operaciones de inserción, eliminación y sustitución de un único símbolo necesarias para transformar una secuencia en la otra, asignando coste 1 a cada operación.^[1]

Recibe su nombre del matemático soviético Vladimir Levenshtein, que introdujo esta distancia en 1965 en el contexto de los códigos capaces de corregir errores de inserción y eliminación.^[1] La distancia de Levenshtein es una forma clásica de distancia de edición. Este último término también se emplea en sentido más amplio para modelos en los que cambia el conjunto de operaciones permitidas o el coste asignado a cada una de ellas.^[2]

Se utiliza, entre otros ámbitos, en la corrección ortográfica, la búsqueda aproximada, el análisis lingüístico, el reconocimiento del habla, el cotejo de registros y la comparación de secuencias biológicas.^[2]

Definición

Sean

a=a_{1}a_{2}\dots a_{m}

y

b=b_{1}b_{2}\dots b_{n}

dos secuencias. Se define $D(i,j)$ como la distancia de Levenshtein entre el prefijo $a_{1}\dots a_{i}$ y el prefijo $b_{1}\dots b_{j}$ .

Las condiciones de contorno son

D(i,0)=i,\qquad D(0,j)=j.

Para $i>0$ y $j>0$ ,

D(i,j)=\min {\begin{cases}D(i-1,j)+1,\\D(i,j-1)+1,\\D(i-1,j-1)+\delta (a_{i},b_{j}),\end{cases}}

donde

\delta (a_{i},b_{j})={\begin{cases}0,&a_{i}=b_{j},\\1,&a_{i}\neq b_{j}.\end{cases}}

Los tres términos representan, respectivamente, la eliminación de un símbolo de la secuencia de origen, la inserción de un símbolo de la secuencia de destino y la coincidencia o sustitución del último símbolo de ambos prefijos.^[3]

La distancia entre las secuencias completas es $D(m,n)$ .

Ejemplos

Entre las palabras «casa» y «calle» la distancia de Levenshtein es 3. Una secuencia mínima de operaciones es:

casa → cala — sustitución de s por l;
cala → calla — inserción de l;
calla → calle — sustitución de a por e.

Otro ejemplo clásico es kitten → sitting, cuya distancia es 3 mediante dos sustituciones y una inserción.

Propiedades y cotas

Con costes unitarios de inserción, eliminación y sustitución, la distancia de Levenshtein es una métrica: es no negativa, vale cero si y solo si las dos secuencias son iguales, es simétrica y satisface la desigualdad triangular.^[2]

Para dos secuencias de longitudes $m$ y $n$ ,

|m-n|\leq d_{L}(a,b)\leq \max(m,n).

La cota inferior se debe a que una sola inserción o eliminación cambia la longitud en una unidad. La cota superior puede alcanzarse sustituyendo los símbolos de la parte de longitud común y, después, insertando o eliminando los símbolos restantes.

Si ambas secuencias tienen la misma longitud, la distancia de Hamming es una cota superior de la distancia de Levenshtein:

d_{L}(a,b)\leq d_{H}(a,b).

La distancia de Hamming solo contabiliza sustituciones y se aplica directamente a secuencias de igual longitud.

Si se prohíben las sustituciones y solo se permiten inserciones y eliminaciones, la distancia de edición resultante para dos secuencias de longitudes $m$ y $n$ es

m+n-2L,

donde $L$ es la longitud de una subsecuencia común más larga. Esta igualdad no se aplica sin cambios a la distancia de Levenshtein clásica, pues en ella una sustitución cuesta 1, mientras que una eliminación seguida de una inserción cuesta 2.^[3]

Cálculo

Programación dinámica

El algoritmo clásico usa programación dinámica. Una matriz de tamaño $(m+1)\times (n+1)$ almacena las distancias entre todos los pares de prefijos.^[3]

función DistanciaLevenshtein(s[1..m], t[1..n]):
    crear d[0..m, 0..n]

    para i de 0 a m:
        d[i,0] = i

    para j de 0 a n:
        d[0,j] = j

    para i de 1 a m:
        para j de 1 a n:
            si s[i] = t[j]:
                coste = 0
            en otro caso:
                coste = 1

            d[i,j] = mínimo(
                d[i-1,j]   + 1,      // eliminación de s[i]
                d[i,j-1]   + 1,      // inserción de t[j]
                d[i-1,j-1] + coste   // coincidencia o sustitución
            )

    devolver d[m,n]

El invariante es que d[i,j] representa el número mínimo de ediciones necesarias para transformar los primeros i símbolos de s en los primeros j símbolos de t.

La matriz completa requiere tiempo $\Theta (mn)$ y espacio $\Theta (mn)$ .^[3]

Reducción de memoria

Si solo se necesita el valor de la distancia, cada fila depende únicamente de la fila anterior y de la fila corriente. Usando la secuencia más corta como dimensión almacenada, la memoria de trabajo puede reducirse a $O(\min(m,n))$ .^[4]

Reconstrucción de las operaciones

Si se conserva la matriz completa, puede reconstruirse una secuencia óptima de ediciones recorriéndola en sentido inverso desde $D(m,n)$ . Puede haber varios predecesores que produzcan el mismo valor mínimo; por tanto, una misma distancia puede corresponder a más de una secuencia óptima de operaciones.

Algoritmos dependientes de la distancia

Cuando la distancia real $s$ es pequeña respecto de las longitudes de las secuencias, no siempre es necesario calcular toda la matriz. Ukkonen desarrolló algoritmos exactos que restringen el cálculo a una banda relevante de la matriz y cuyo coste depende de $s$ .^[4]

En este contexto, «búsqueda aproximada» significa que se permiten discrepancias entre las cadenas; no implica necesariamente aproximar el valor numérico de la distancia.

Métodos bit-paralelos

Myers propuso en 1999 un algoritmo basado en vectores de bits para búsqueda aproximada, en el que numerosos estados de la programación dinámica se empaquetan en los bits de una palabra de máquina y se actualizan mediante operaciones bit a bit.^[5]

Variantes y medidas relacionadas

Distancia de edición ponderada

En una distancia de edición ponderada, las inserciones, eliminaciones y sustituciones pueden recibir costes diferentes, incluso dependientes de los símbolos concretos. Una elección arbitraria de costes no preserva automáticamente todas las propiedades métricas; por ejemplo, unos costes asimétricos pueden romper la simetría.^[2]

La distancia de Damerau-Levenshtein añade como operación elemental la transposición de dos símbolos adyacentes.

Normalización

La distancia sin normalizar tiende a crecer con la longitud de las secuencias. Por ello se utilizan variantes normalizadas. No existe una única definición universal de «distancia de Levenshtein normalizada».

Una forma frecuente es

d_{N}(a,b)={\frac {d_{L}(a,b)}{\max(|a|,|b|)}},

que toma valores entre 0 y 1. El complemento

s(a,b)=1-d_{N}(a,b)

puede interpretarse como una medida de similitud.

En lingüística cuantitativa se emplean asimismo medidas construidas a partir de esta normalización. El proyecto ASJP, por ejemplo, calcula distancias entre listas léxicas mediante LDND (Levenshtein Distance Normalized Divided), que normaliza primero por la longitud de las palabras y después corrige parte de la semejanza accidental entre inventarios fonológicos.^[6]^[7]

Aplicaciones

Corrección ortográfica y búsqueda aproximada

La distancia de Levenshtein es una medida básica en la búsqueda aproximada de cadenas. Permite localizar candidatos que difieren de una consulta por pequeñas inserciones, eliminaciones o sustituciones, como ocurre en muchos sistemas de corrección ortográfica.^[2]

En colecciones grandes, el cálculo de la distancia suele combinarse con filtros, índices, q-gramas u otras técnicas para reducir el número de comparaciones completas.^[2]

Reconocimiento del habla en español

En reconocimiento automático del habla, la distancia de edición puede calcularse sobre secuencias de palabras o fonemas. Investigadores en México han empleado la distancia de Levenshtein sobre representaciones fonéticas para corregir errores de reconocimiento en español dentro de dominios específicos.^[8]

En este tipo de evaluación también se usa la tasa de error de palabras (WER), calculada a partir del número de sustituciones $S$ , eliminaciones $D$ e inserciones $I$ en el alineamiento entre la hipótesis y la transcripción de referencia:

\mathrm {WER} ={\frac {S+D+I}{N}},

donde $N$ es el número de palabras de la referencia.^[8]

Dialectometría y variedades del español

La distancia de Levenshtein también se ha utilizado en dialectometría. Fernández Planas y colaboradores analizaron datos prosódicos de seis variedades del español peninsular y siete variedades insulares mediante métodos dialectométricos, incluyendo el índice de distancia lingüística de Levenshtein sobre cadenas de etiquetas prosódicas.^[9]

En estos usos, la distancia se aplica a representaciones fonéticas, fonológicas o prosódicas concretas; no constituye por sí sola una medida universal de la «distancia entre lenguas».

Estudios léxicos

La definición de Levenshtein se aplica a secuencias de símbolos, por lo que los símbolos no tienen que ser necesariamente caracteres individuales. En Chile, Rojas, Zambrano y Salcedo propusieron una medida de disimilitud entre lexicones de estudiantes basada en Levenshtein, considerando cada palabra del lexicón como un símbolo y comparando secuencias ordenadas de vocablos.^[10]

Este ejemplo ilustra que la misma construcción matemática puede operar sobre caracteres, palabras, fonemas, tokens u otros símbolos, siempre que la unidad de comparación esté definida.

Lingüística histórica y clasificación automática

En bases comparativas como ASJP, las formas léxicas de conceptos equivalentes se transcriben en un sistema común y se comparan mediante variantes normalizadas de Levenshtein. El proyecto utiliza LDND para producir matrices de distancia entre listas de palabras.^[6]

Estas medidas pueden contribuir a la clasificación automática y a estudios cuantitativos, pero no sustituyen por sí solas al método comparativo histórico. La normalización y la corrección por semejanzas accidentales son precisamente intentos de reducir algunos sesgos de la distancia bruta.^[11]

Bioinformática

En bioinformática, la distancia de edición está estrechamente relacionada con la comparación y el alineamiento de secuencias. Inserciones, eliminaciones y sustituciones ofrecen un modelo simple de diferencias entre secuencias de ADN o proteínas. Sin embargo, los algoritmos de alineamiento empleados en la práctica suelen utilizar matrices de sustitución y penalizaciones de gap más ricas que la distancia de Levenshtein con coste unitario.^[12]

Unicode y unidad de comparación

La definición matemática se formula sobre secuencias de símbolos y no determina qué debe considerarse un «carácter» en una implementación. En texto Unicode puede compararse, por ejemplo, la secuencia de bytes codificados, unidades de código, puntos de código o clústeres de grafemas. Estas elecciones pueden producir distancias diferentes.

Este detalle es relevante en español por la presencia de letras acentuadas, diéresis y la letra ñ. Por ejemplo, «ñ» puede representarse mediante un único punto de código precompuesto o mediante una n seguida de un signo de tilde combinante. Las dos representaciones pueden ser canónicamente equivalentes sin ser secuencias idénticas de puntos de código.

El Unicode Standard Annex #15 define formas de normalización como NFC y NFD para tratar la equivalencia canónica.^[13] El Unicode Standard Annex #29 define los extended grapheme clusters, una aproximación algorítmica de los caracteres percibidos por el usuario.^[14]

La normalización Unicode no equivale a eliminar tildes o diacríticos: «papa» y «papá» siguen siendo cadenas distintas. Una implementación debe especificar la unidad comparada y cualquier normalización previa al cálculo.

Limitaciones

La distancia de Levenshtein mide el coste mínimo de edición, no la semejanza semántica. Dos palabras de significado muy distinto pueden diferir en un solo carácter, mientras que dos expresiones semánticamente equivalentes pueden tener una distancia elevada.

También es sensible a la longitud de las secuencias, razón por la que algunas aplicaciones utilizan medidas normalizadas. Además, la distancia clásica trata todas las sustituciones como igualmente costosas: no incorpora de forma automática semejanza fonética, relaciones morfológicas, orden flexible de palabras, abreviaturas ni contexto.

En lingüística, una distancia pequeña entre formas no demuestra por sí sola parentesco histórico; las semejanzas pueden deberse a coincidencias, préstamos o restricciones fonotácticas. Por ello, los métodos cuantitativos suelen combinarse con información lingüística adicional y normalizaciones específicas.^[6]

Historia

Levenshtein presentó en 1965 una distancia entre secuencias en el marco de la teoría de códigos capaces de corregir inserciones y eliminaciones.^[1] El artículo original no contenía la forma matricial que hoy suele enseñarse como algoritmo estándar.

En 1974, Wagner y Fischer publicaron una formulación general mediante programación dinámica del problema de corrección de una cadena en otra.^[3] Trabajos posteriores desarrollaron algoritmos sensibles a la distancia real, técnicas bit-paralelas, autómatas, índices para búsqueda aproximada y otros métodos especializados.^[4]^[5]^[2]

Véase también

Referencias

1 2 3 V. I. Levenshtein, «Binary codes capable of correcting deletions, insertions, and reversals», Doklady Akademii Nauk SSSR, vol. 163, n.º 4, 1965, pp. 845–848. Traducción inglesa en Soviet Physics Doklady, vol. 10, n.º 8, 1966, pp. 707–710. Math-Net.
1 2 3 4 5 6 7 Gonzalo Navarro, «A guided tour to approximate string matching», ACM Computing Surveys, vol. 33, n.º 1, 2001, pp. 31–88. doi:10.1145/375360.375365.
1 2 3 4 5 Robert A. Wagner y Michael J. Fischer, «The String-to-String Correction Problem», Journal of the ACM, vol. 21, n.º 1, 1974, pp. 168–173. doi:10.1145/321796.321811.
1 2 3 Esko Ukkonen, «Algorithms for approximate string matching», Information and Control, vol. 64, n.os 1–3, 1985, pp. 100–118. doi:10.1016/S0019-9958(85)80046-2.
1 2 Gene Myers, «A fast bit-vector algorithm for approximate string matching based on dynamic programming», Journal of the ACM, vol. 46, n.º 3, 1999, pp. 395–415. doi:10.1145/316542.316550.
1 2 3 The ASJP Database, «How to get a matrix of ASJP distances». ASJP.
↑ Søren Wichmann, «How to Distinguish Languages and Dialects», Computational Linguistics, vol. 45, n.º 4, 2019, pp. 823–867. doi:10.1162/coli_a_00366.
1 2 Diego Campos Sobrino, Mario Campos Soberanis, Iván Martínez Chin y Víctor Uc Cetina, «Corrección de errores del reconocedor de voz de Google usando métricas de distancia fonética», Research in Computing Science, vol. 148, n.º 1, 2019, pp. 57–70. texto completo.
↑ Ana María Fernández Planas, Josefa Dorta, Paolo Roseano, Chaxiraxi Díaz, Wendy Elvira-García, José Antonio Martín Gómez y Eugenio Martínez Celdrán, «Distancia y proximidad prosódica entre algunas variedades del español: un estudio dialectométrico a partir de datos acústicos», RLA. Revista de Lingüística Teórica y Aplicada, vol. 53, n.º 2, 2015, pp. 13–45. doi:10.4067/S0718-48832015000200002.
↑ Darío F. Rojas, Carolina del C. Zambrano y Pedro A. Salcedo, «Metodología de análisis de disponibilidad léxica en alumnos de pedagogía a través de la comparación jerárquica de lexicones», Formación Universitaria, vol. 10, n.º 4, 2017, pp. 3–14. doi:10.4067/S0718-50062017000400002.
↑ Søren Wichmann et al., «Evaluating linguistic distance measures», Physica A: Statistical Mechanics and its Applications, vol. 389, n.º 17, 2010, pp. 3632–3639. doi:10.1016/j.physa.2010.05.011.
↑ Bonnie Berger, Michael S. Waterman y Yun William Yu, «Levenshtein Distance, Sequence Comparison and Biological Database Search», IEEE Transactions on Information Theory, vol. 67, n.º 6, 2021, pp. 3287–3294. doi:10.1109/TIT.2020.2996543.
↑ Unicode Consortium, «Unicode Standard Annex #15: Unicode Normalization Forms». Unicode Consortium.
↑ Unicode Consortium, «Unicode Standard Annex #29: Unicode Text Segmentation». Unicode Consortium.

Bibliografía

Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997. ISBN 0-521-58519-8.
Gonzalo Navarro, «A guided tour to approximate string matching», ACM Computing Surveys, vol. 33, n.º 1, 2001, pp. 31–88.
Ana María Fernández Planas et al., «Distancia y proximidad prosódica entre algunas variedades del español: un estudio dialectométrico a partir de datos acústicos», RLA. Revista de Lingüística Teórica y Aplicada, vol. 53, n.º 2, 2015.
Darío F. Rojas, Carolina del C. Zambrano y Pedro A. Salcedo, «Metodología de análisis de disponibilidad léxica en alumnos de pedagogía a través de la comparación jerárquica de lexicones», Formación Universitaria, vol. 10, n.º 4, 2017.

Enlaces externos

Proyecto: Distancia de Levenshtein — material docente de la Universidad de Costa Rica con ejercicios de implementación y tratamiento de Unicode.
Levenshtein distance — Dictionary of Algorithms and Data Structures, NIST (en inglés)
Levenshtein Distance — recurso en inglés sobre definición, algoritmos, historia, publicaciones y aplicaciones de la distancia de Levenshtein.

[Levenshtein1965-1] 1 2 3 V. I. Levenshtein, «Binary codes capable of correcting deletions, insertions, and reversals», Doklady Akademii Nauk SSSR, vol. 163, n.º 4, 1965, pp. 845–848. Traducción inglesa en Soviet Physics Doklady, vol. 10, n.º 8, 1966, pp. 707–710. Math-Net.

[Navarro2001-2] 1 2 3 4 5 6 7 Gonzalo Navarro, «A guided tour to approximate string matching», ACM Computing Surveys, vol. 33, n.º 1, 2001, pp. 31–88. doi:10.1145/375360.375365.

[WagnerFischer1974-3] 1 2 3 4 5 Robert A. Wagner y Michael J. Fischer, «The String-to-String Correction Problem», Journal of the ACM, vol. 21, n.º 1, 1974, pp. 168–173. doi:10.1145/321796.321811.

[Ukkonen1985-4] 1 2 3 Esko Ukkonen, «Algorithms for approximate string matching», Information and Control, vol. 64, n.os 1–3, 1985, pp. 100–118. doi:10.1016/S0019-9958(85)80046-2.

[Myers1999-5] 1 2 Gene Myers, «A fast bit-vector algorithm for approximate string matching based on dynamic programming», Journal of the ACM, vol. 46, n.º 3, 1999, pp. 395–415. doi:10.1145/316542.316550.

[ASJP-6] 1 2 3 The ASJP Database, «How to get a matrix of ASJP distances». ASJP.

[7] Søren Wichmann, «How to Distinguish Languages and Dialects», Computational Linguistics, vol. 45, n.º 4, 2019, pp. 823–867. doi:10.1162/coli_a_00366.

[Campos2019-8] 1 2 Diego Campos Sobrino, Mario Campos Soberanis, Iván Martínez Chin y Víctor Uc Cetina, «Corrección de errores del reconocedor de voz de Google usando métricas de distancia fonética», Research in Computing Science, vol. 148, n.º 1, 2019, pp. 57–70. texto completo.

[Fernandez2015-9] Ana María Fernández Planas, Josefa Dorta, Paolo Roseano, Chaxiraxi Díaz, Wendy Elvira-García, José Antonio Martín Gómez y Eugenio Martínez Celdrán, «Distancia y proximidad prosódica entre algunas variedades del español: un estudio dialectométrico a partir de datos acústicos», RLA. Revista de Lingüística Teórica y Aplicada, vol. 53, n.º 2, 2015, pp. 13–45. doi:10.4067/S0718-48832015000200002.

[Rojas2017-10] Darío F. Rojas, Carolina del C. Zambrano y Pedro A. Salcedo, «Metodología de análisis de disponibilidad léxica en alumnos de pedagogía a través de la comparación jerárquica de lexicones», Formación Universitaria, vol. 10, n.º 4, 2017, pp. 3–14. doi:10.4067/S0718-50062017000400002.

[11] Søren Wichmann et al., «Evaluating linguistic distance measures», Physica A: Statistical Mechanics and its Applications, vol. 389, n.º 17, 2010, pp. 3632–3639. doi:10.1016/j.physa.2010.05.011.

[Berger2021-12] Bonnie Berger, Michael S. Waterman y Yun William Yu, «Levenshtein Distance, Sequence Comparison and Biological Database Search», IEEE Transactions on Information Theory, vol. 67, n.º 6, 2021, pp. 3287–3294. doi:10.1109/TIT.2020.2996543.

[UAX15-13] Unicode Consortium, «Unicode Standard Annex #15: Unicode Normalization Forms». Unicode Consortium.

[UAX29-14] Unicode Consortium, «Unicode Standard Annex #29: Unicode Text Segmentation». Unicode Consortium.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]