DevBentoCalculadora de Distancia Levenshtein
Calcula la distancia de edición Levenshtein entre dos cadenas de texto. Ve cuántas inserciones, eliminaciones y reemplazos se necesitan.
Calculadora de distancia Levenshtein
Este ejemplo calcula la distancia Levenshtein de String Tools, precargado con la clásica comparación de “kitten” a “sitting”. Escribe dos strings y ve el número mínimo de ediciones de un solo carácter necesarias para transformar uno en el otro.
Cómo funciona
La distancia Levenshtein usa programación dinámica. Se construye una matriz donde cada celda representa la distancia de edición entre subcadenas. El algoritmo rellena la matriz considerando tres operaciones en cada posición:
| Operación | Descripción | Costo |
|---|---|---|
| Insert | Agregar un carácter | 1 |
| Delete | Eliminar un carácter | 1 |
| Substitute | Reemplazar un carácter | 1 (si es distinto) |
El valor final en la celda inferior derecha de la matriz es la distancia Levenshtein.
El ejemplo de “kitten” a “sitting”
El ejemplo clásico requiere 3 ediciones:
- kitten → sitten (sustituye k por s)
- sitten → sittin (sustituye e por i)
- sittin → sitting (inserta g al final)
Distancia = 3.
Complejidad de tiempo y espacio
El algoritmo corre en tiempo y espacio O(m x n), donde m y n son las longitudes de los dos strings. Para la mayoría de comparaciones prácticas de texto (menos de 1000 caracteres), se ejecuta al instante en el navegador.
Variaciones
Varios algoritmos modifican Levenshtein para casos de uso específicos:
- Damerau-Levenshtein agrega la transposición (intercambiar caracteres adyacentes) como cuarta operación
- Levenshtein ponderado asigna costos distintos a las operaciones (p. ej. la sustitución cuesta más que la inserción)
- distancia de edición restringida limita qué operaciones están permitidas
Cómo usar
- Escribe el primer string en el campo de entrada
- Escribe el segundo string en el segundo campo
- La distancia de edición aparece en el área de resultado
- La herramienta también muestra la transformación paso a paso
Preguntas comunes
¿Cuál es la distancia máxima posible?
La distancia máxima es la longitud del string más largo, que ocurre cuando un string está totalmente vacío y debes insertar cada carácter. Para dos strings de longitudes m y n, la distancia es como máximo max(m, n).
¿Cómo afecta la sensibilidad a mayúsculas al resultado?
La comparación distingue mayúsculas. Hello y hello tienen distancia 1 (la diferencia H/h). Para una comparación insensible a mayúsculas, convierte ambos strings a minúsculas primero.
¿Puedo usarlo para comparar secuencias de ADN?
Sí. La distancia Levenshtein se usa mucho en bioinformática para medir similitud entre secuencias de ADN o proteínas. Cada carácter representa un nucleótido o aminoácido, y la distancia de edición refleja el número de mutaciones entre secuencias.
Nothing you paste leaves this tab. Every tool runs entirely in your browser — no upload, no server, no account.