Calculadora de distancia de Levenshtein
Datos de entrada
| Primera cadena | kitten |
|---|---|
| Segunda cadena | sitting |
Calculadora de distancia de Levenshtein
Calcula la distancia de Levenshtein (distancia de edición) entre dos cadenas: el número mínimo de inserciones, eliminaciones y sustituciones de un solo carácter necesarias para transformar una en la otra, junto con un porcentaje de similitud.
Datos de entrada
Cadenas
Resultados
Introduce un valor para ver los resultados.
Resultados
Distancia de Levenshtein
La distancia de Levenshtein, también llamada distancia de edición, mide cuán diferentes son dos cadenas contando el menor número de ediciones de un solo carácter necesarias para convertir una en la otra. Las ediciones permitidas son la inserción, la eliminación y la sustitución, cada una con coste uno. La calculadora recibe dos cadenas y devuelve esa distancia junto con un porcentaje de similitud, lo que resulta útil para la corrección ortográfica, la coincidencia aproximada y la comparación de secuencias como el ADN.
Las tres operaciones de edición
Toda transformación entre dos cadenas puede expresarse como una secuencia de tres movimientos básicos. Una inserción añade un carácter, una eliminación quita uno y una sustitución reemplaza un carácter por otro. La distancia de Levenshtein busca la secuencia más económica de estos movimientos, donde cada uno cuesta uno. Como la sustitución es un solo paso y no una eliminación seguida de una inserción, cambiar una letra siempre se cuenta como una edición, no como dos.
Lleva el nombre de Vladímir Levenshtein, que la definió en 1965, y generaliza la más antigua Calculadora de distancia de Hamming: la distancia de Hamming solo permite sustituciones y únicamente para cadenas de igual longitud, mientras que la de Levenshtein admite además inserciones y eliminaciones, por lo que maneja cadenas de longitudes distintas.
La tabla de programación dinámica
La distancia se calcula rellenando una tabla con una fila por cada carácter de la primera cadena (más una fila vacía inicial) y una columna por cada carácter de la segunda (más una columna vacía inicial). La celda contiene la distancia de edición entre los primeros caracteres de A y los primeros caracteres de B.
La primera fila y la primera columna cuentan las ediciones frente a la cadena vacía, de modo que y . Cualquier otra celda es el mínimo de tres candidatos:
D[i][j]=min⎩⎨⎧D[i−1][j]+1D[i][j−1]+1D[i−1][j−1]+c(eliminacioˊn)(insercioˊn)(sustitucioˊn)donde el coste de sustitución es 0 cuando los caracteres coinciden y 1 cuando difieren. La respuesta queda en la celda inferior derecha. Rellenar la tabla lleva un tiempo proporcional al producto de las dos longitudes, .
Ejemplo resuelto
Tomemos el par clásico «kitten» y «sitting». Recorrer el camino óptimo por la tabla da tres ediciones:
kittensittensittin→sitten→sittin→sitting(sustituir k→s)(sustituir e→i)(insertar g)No existe ninguna secuencia más corta, así que la distancia es 3. La cadena más larga tiene 7 caracteres, de modo que la similitud es , es decir, alrededor del 57 %.
La similitud y sus límites
La calculadora normaliza la distancia bruta en una puntuación de similitud mediante
Dividir entre la longitud de la cadena más larga mantiene el resultado entre el 0 % para cadenas totalmente distintas y el 100 % para idénticas; dos cadenas vacías se consideran idénticas. Esta es una de las normalizaciones habituales —otras herramientas dividen entre la suma de las longitudes o usan medidas basadas en proporciones—, por lo que las cifras de similitud de fuentes diferentes no son directamente comparables.
Dónde se utiliza
Los correctores ortográficos ordenan las correcciones candidatas según su distancia de edición respecto de la palabra mal escrita. Los sistemas de búsqueda y de bases de datos la usan para la coincidencia aproximada, tolerando erratas al consultar nombres o direcciones. En bioinformática, la distancia de edición sustenta el alineamiento de secuencias para comparar ADN, ARN y proteínas, donde las inserciones y eliminaciones corresponden a mutaciones. El modelo de coste de Levenshtein simple trata todas las ediciones por igual; las aplicaciones que necesitan penalizaciones distintas para operaciones distintas, o que deben alinear con eficiencia secuencias muy largas, lo amplían con costes ponderados o con algoritmos de alineamiento especializados.
Preguntas frecuentes (FAQ)
¿Qué es la distancia de Levenshtein?
La distancia de Levenshtein, también llamada distancia de edición, es el número mínimo de ediciones de un solo carácter —inserciones, eliminaciones o sustituciones— necesarias para convertir una cadena en otra. Fue introducida en 1965 por el matemático soviético Vladímir Levenshtein.
Por ejemplo, la distancia entre «kitten» y «sitting» es 3: sustituir k→s, sustituir e→i e insertar una g al final. No existe ninguna secuencia de ediciones más corta.
El valor se calcula con una tabla de programación dinámica cuyas celdas contienen la distancia de edición entre prefijos de las dos cadenas. Rellenar la tabla lleva un tiempo proporcional al producto de las dos longitudes.
¿En qué se diferencia de la distancia de Hamming?
La distancia de Hamming cuenta solo sustituciones y se define únicamente para cadenas de igual longitud, ya que compara los caracteres posición por posición. La distancia de Levenshtein también permite inserciones y eliminaciones, por lo que funciona con cadenas de distinta longitud y capta los desplazamientos de alineación.
Para dos cadenas de la misma longitud, la distancia de Levenshtein siempre es menor o igual que la de Hamming, porque la sustitución es una de sus operaciones, pero puede encontrar un camino más económico mediante inserciones y eliminaciones.
¿Cómo se calcula el porcentaje de similitud?
La similitud se expresa como 1 − distancia / max(len_a, len_b), en forma de porcentaje. Dividir entre la longitud de la cadena más larga normaliza la puntuación al rango de 0 % (completamente distintas) a 100 % (idénticas). Cuando ambas cadenas están vacías, la similitud se define como 100 %.
Esta es una de las normalizaciones habituales; otras herramientas dividen entre la suma de las longitudes o usan medidas basadas en proporciones, por lo que las puntuaciones de similitud no son directamente comparables entre definiciones distintas.