Calculadora Distancia de Levenshtein

Calcula la distancia de Levenshtein (edit distance) entre cadenas, similitud porcentual, Damerau con transposición y búsqueda de palabra más cercana.

Parámetros de cálculo
Scegli il tipo di calcolo.
Prima stringa da confrontare.
Seconda stringa. Per 'closest_word' è la parola di riferimento.
Per modo closest_word: dizionario in cui cercare la parola più vicina a s1.
¿Te ha sido útil esta calculadora?

La distancia de Levenshtein

La distancia de Levenshtein, introducida por el matemático ruso Vladimir Levenshtein en 1965, cuenta el número mínimo de operaciones elementales (inserción, eliminación o sustitución) para transformar una cadena en otra.

Operaciones elementales

  1. Inserción.
  2. Eliminación.
  3. Sustitución.

Distancia entre «kitten» y «sitting» = 3.

Los cuatro modos

  1. Distancia clásica con matriz DP.
  2. Similitud normalizada (0-100%).
  3. Damerau-Levenshtein con transposición.
  4. Palabra más cercana en lista.

Algoritmo DP de Wagner-Fischer

d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+c), c = 0 si iguales, 1 si no. Complejidad O(m·n).

Damerau-Levenshtein

Agrega transposición: d[i][j] ≤ d[i-2][j-2]+1 si a[i-1]=b[j-2] y a[i-2]=b[j-1]. «teh» → «the» = 1 en Damerau.

Variantes

  • Hamming: solo sustituciones en cadenas de igual longitud.
  • Jaro/Jaro-Winkler: destaca prefijos comunes.
  • N-gram / Jaccard: conjuntos de subcadenas k.
  • Needleman-Wunsch: generalización ponderada, bioinformática.
  • Smith-Waterman: alineación local.

Aplicaciones

  • Correctores: Aspell, Hunspell.
  • Fuzzy search: Elasticsearch, Solr.
  • Diff/merge: Unix, Git (Myers 1986).
  • ADN: BLAST, FASTA.
  • Deduplicación de registros.
  • Post-procesamiento OCR.

Optimizaciones

  • Memoria O(min(m,n)): solo se necesitan dos arrays 1D (fila actual y anterior).
  • Ukkonen cutoff: si buscamos distancia ≤ k, nos limitamos a una banda diagonal de ancho 2k+1, complejidad O(k·max(m,n)).
  • Bit-parallel Myers 1999: con SIMD y operaciones bitwise, ~60× más rápido para cadenas cortas (hasta 64 caracteres).
  • Filtrado q-gram antes del cálculo exacto: descarta candidatos lejanos con hash.

Ejemplo paso a paso

Calculemos la distancia entre «kitten» y «sitting». La matriz DP 7×8 da d[6][7] = 3. Sequencia óptima: k→s (sustitución), e→i (sustitución), fin «g» (inserción). Verificación: 3 operaciones mínimas para transformar «kitten» en «sitting». Similitud = 1 − 3/7 = 0,571 = 57,1%.

Donde la distancia de edicion impulsa el software cotidiano

La distancia de Levenshtein es una de esas ideas discretas que operan sin verse en herramientas que usamos cada dia. El corrector ortografico la emplea para proponer la palabra correcta mas cercana a la que escribiste mal, y el autocorrector del telefono la utiliza para adivinar tu intencion a partir de pulsaciones erroneas. La busqueda difusa, que encuentra resultados aunque el termino tenga faltas, se apoya en un umbral de similitud derivado de esta distancia, y los sistemas de reconocimiento optico de caracteres la usan para corregir lecturas dudosas comparandolas con un diccionario.

Su alcance va mucho mas alla del texto ordinario. En bioinformatica, variantes de la misma idea alinean secuencias de ADN y proteinas para medir su parentesco evolutivo, un problema en el corazon de la genomica moderna. Los detectores de plagio comparan documentos, los sistemas de vinculacion de registros fusionan bases de datos identificando entradas casi identicas escritas de forma distinta, y las herramientas de control de versiones calculan las diferencias entre archivos. En todos estos casos, contar el numero minimo de ediciones ofrece una medida robusta y universal de cuanto se parecen dos cadenas.

La idea de la programacion dinamica tras el algoritmo

El calculo eficiente de la distancia de Levenshtein es un ejemplo clasico de programacion dinamica. En lugar de probar todas las secuencias posibles de ediciones, que serian astronomicamente numerosas, se construye una tabla en la que cada celda guarda la distancia entre dos prefijos de las cadenas. El valor de cada celda se obtiene de sus tres vecinos ya calculados, eligiendo el minimo entre insertar, eliminar o sustituir un caracter. Esta propiedad de subestructura optima permite resolver el problema en tiempo proporcional al producto de las longitudes.

Rellenada la tabla, la esquina inferior derecha contiene la distancia buscada, y recorriendo la matriz hacia atras se recupera la secuencia concreta de operaciones que la realiza. Esta misma estructura conecta con el problema de la subsecuencia comun mas larga y con el alineamiento de secuencias de Needleman-Wunsch, del que la distancia de edicion es una variante. La calculadora muestra la matriz completa para cadenas cortas, de modo que se puede seguir visualmente como cada valor se propaga desde la esquina superior izquierda hasta la solucion final.

Actualizado a julio de 2026

Preguntas frecuentes

Que es la distancia de Levenshtein?

Es el numero minimo de operaciones elementales (insertar, eliminar o sustituir un caracter) necesarias para transformar una cadena en otra. Introducida por el matematico ruso Vladimir Levenshtein en 1965, es la medida mas usada para cuantificar cuanto difieren dos palabras o textos. Para "kitten" y "sitting" vale 3.

Que modos ofrece la calculadora?

Cuatro: la distancia clasica con la matriz de programacion dinamica, la similitud normalizada de 0 a 100%, la variante Damerau-Levenshtein que anade la transposicion de caracteres adyacentes, y la busqueda de la palabra mas cercana en una lista. Cada modo muestra la secuencia de operaciones optima.

Como se calcula la distancia?

Con programacion dinamica: se construye una matriz en la que d[i][j] es la distancia entre los primeros i caracteres de la primera cadena y los primeros j de la segunda. Cada celda es el minimo de d[i-1][j]+1, d[i][j-1]+1 y d[i-1][j-1]+coste, donde el coste es 0 si los caracteres coinciden, 1 en caso contrario.

Que es la similitud normalizada?

Es la distancia expresada como porcentaje respecto a la longitud maxima de las dos cadenas: similitud = (1 - distancia/max(|s1|, |s2|)) x 100%. Vale 100% para cadenas identicas y baja hacia 0 para cadenas muy distintas. En el fuzzy matching suele usarse un umbral del 80% para considerar dos cadenas similares.

Que es la distancia de Damerau-Levenshtein?

Es una variante que anade una cuarta operacion: la transposicion de dos caracteres adyacentes, con coste 1. Captura mejor los errores de tecleo como el intercambio de letras vecinas ("teh" en vez de "the"). La calculadora muestra tanto la distancia de Levenshtein como la de Damerau para comparar.

Cual es la complejidad del algoritmo?

El calculo con la matriz requiere tiempo y espacio proporcionales al producto de las longitudes de las dos cadenas, es decir O(m x n). Existen optimizaciones: la version de banda diagonal para distancias pequenas, el algoritmo bit-parallel de Myers y el filtrado q-gram, que aceleran mucho las comparaciones sobre grandes diccionarios.

Donde se usa la distancia de Levenshtein?

En los correctores ortograficos y la autocorreccion, en la busqueda difusa, en el reconocimiento optico de caracteres, en la bioinformatica para alinear secuencias de ADN y proteinas, en la deteccion de plagio, en la deduplicacion de bases de datos y en las herramientas de comparacion de archivos. Se usa dondequiera que haya que medir la semejanza entre textos.

Como se encuentra la palabra mas similar?

Se calcula la distancia de Levenshtein entre la cadena dada y cada palabra de una lista candidata, eligiendo la de distancia minima. Es el mecanismo de las sugerencias de los correctores y del autocompletado: entre todas las palabras del diccionario, se propone la que requiere menos modificaciones para coincidir con lo tecleado.

Comentarios (0)

Sin comentarios aún. ¡Sé el primero!