Visualizador de Distancia de Levenshtein

Introduce dos cadenas para ver su distancia de Levenshtein (edición) — el número mínimo de ediciones de un solo carácter necesarias para transformar una en la otra.

Ejemplo resuelto — Visualizador de Distancia de Levenshtein

Distancia de edición	3
Similitud	57,14%

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — Visualizador de Distancia de Levenshtein

La distancia de Levenshtein entre dos cadenas es el menor número de ediciones de un solo carácter que convierte una en la otra, siendo una edición una inserción, un borrado o una sustitución. Es un mínimo sobre todas las maneras posibles de hacerlo, y eso es justo lo que la hace difícil de estimar a ojo y fácil de calcular con una cuadrícula: hay una cantidad astronómica de secuencias de edición, y este procedimiento encuentra la más corta sin enumerar ninguna.

Qué significa cada símbolo

m, n: las longitudes de las dos cadenas, A y B.
D(i, j): la forma más barata de convertir los i primeros caracteres de A en los j primeros caracteres de B. Una celda de la tabla de esta página.
[aᵢ ≠ bⱼ]: vale 1 cuando esos dos caracteres difieren y 0 cuando coinciden: el precio de la sustitución, que se anula si no hay nada que sustituir.
d: la respuesta, D(m, n): la celda inferior derecha.

De dónde viene la fórmula

Decide qué significa una celda antes de rellenar ninguna. Sea D(i, j) el mínimo de ediciones que convierte los i primeros caracteres de A en los j primeros de B. El número que buscas es D(m, n), y cualquier otra celda es una versión menor de la misma pregunta.
Los bordes no exigen pensar. Para construir los j primeros caracteres de B partiendo de nada hay que hacer j inserciones, así que D(0, j) = j. Para reducir a nada los i primeros de A hay que hacer i borrados, así que D(i, 0) = i. Esa es la fila superior y la columna izquierda de la cuadrícula, y por eso se limitan a contar.
Ahora el paso que hace todo el trabajo. Toma cualquier guion óptimo para D(i, j) y mira solo su último movimiento. Hay tres posibilidades y ninguna más: borró aᵢ, dejando la tarea D(i−1, j); insertó bⱼ, dejando D(i, j−1); o emparejó aᵢ con bⱼ, dejando D(i−1, j−1). Cada una de ellas es una celda que tú ya has rellenado.
Así que la celda es la más barata de las tres: D(i, j) = min( D(i−1, j) + 1, D(i, j−1) + 1, D(i−1, j−1) + [aᵢ ≠ bⱼ] ). Rellena la cuadrícula de izquierda a derecha y de arriba abajo, y al llegar a cualquier celda sus tres vecinas ya se conocen. Ese es el algoritmo entero: m × n celdas, tres comparaciones cada una.

Cómo leer lo que ves

La cuadrícula de esta página es esa tabla. Las filas son A, las columnas son B, y la fila y la columna extra de la esquina superior izquierda son los prefijos vacíos del paso 2, por eso cuentan 0, 1, 2, 3. El sombreado de cada celda es su valor: el pasillo diagonal pálido es donde las dos cadenas aún coinciden de forma barata. Pasa el ratón o toca cualquier celda y el panel de debajo detalla el paso 3 para esa celda concreta: los tres candidatos, cada uno con su aritmética, y el ganador resaltado. La línea de color es una ruta óptima trazada hacia atrás desde la esquina inferior derecha, y la tira de alineamiento de debajo es esa misma ruta escrita en caracteres.

Supone: Cada edición cuesta exactamente 1 y los caracteres se comparan por igualdad exacta: sin plegado de mayúsculas, sin normalización Unicode y sin ninguna noción de qué caracteres se parecen. Aquí se ven dos consecuencias. Lo que se cuenta aquí son unidades de código UTF-16, no lo que tú llamarías letras: escribe un solo emoji en una casilla y la tabla es de 3 × 1, porque un emoji son dos unidades y borrarlo cuesta 2. Y café con una é precompuesta frente a café escrito como e más un acento combinante da distancia 2 aunque en pantalla se vean idénticos.
Falla cuando: La cuadrícula tiene m × n celdas, así que el trabajo crece como el producto de las longitudes. Eso está bien para dos palabras y es inviable para una consulta contra un diccionario de un millón de entradas, que son un millón de cuadrículas. La respuesta natural sería un algoritmo más astuto, y la sorpresa es que prácticamente no existe: Backurs e Indyk demostraron en 2015 que una distancia de edición fuertemente subcuadrática refutaría la hipótesis del tiempo exponencial fuerte. Los correctores ortográficos reales no baten esa cota, la esquivan: se detienen en cuanto la distancia supera un límite pequeño, o indexan de modo que casi ningún candidato llegue a compararse.

La cuadrícula es pequeña porque cada subpregunta se plantea una sola vez 🖖

Buscar entre las posibles secuencias de ediciones es imposible — el número de ordenaciones se dispara con la longitud de las palabras. La idea clave que lo rescata es que cualquier par de prefijos tiene exactamente una respuesta óptima, y esa respuesta nunca cambia sin importar lo que ocurra más adelante en la cadena. Así que, en lugar de explorar secuencias, se llena una cuadrícula: una fila por cada letra de la primera palabra, una columna por cada letra de la segunda, más una fila y columna vacías que representan el prefijo vacío. Convertir kitten en sitting equivale por tanto a 7 × 8 = 56 celdas, cada una resuelta al observar tres vecinas ya completadas, y la respuesta 3 aguarda en la esquina inferior derecha. El trabajo crece con el producto de las dos longitudes, no con el número de formas de editar.

Un intercambio cuesta dos ediciones mientras no digas lo contrario 🖖

Escribe form y from y Levenshtein responde 2. No tiene noción alguna de que las letras se hayan intercambiado, así que paga dos sustituciones. Pero las letras intercambiadas están entre los errores de tecleo más frecuentes que existen, y por eso Damerau añadió un cuarto movimiento: si los dos caracteres que necesitas son exactamente los dos que tienes en el orden inverso, llévate ambos al precio de uno. Cambia el modelo de coste de arriba y el mismo par cuesta 1. Nada ha cambiado en las palabras; ha cambiado la lista de precios. Conviene recordarlo allí donde una distancia de edición se usa como puntuación de similitud, porque el número es tanto una propiedad del modelo de coste elegido como de las dos cadenas.

La versión rápida no puede dibujar esta imagen 🖖

Cada celda solo necesita la fila que tiene encima y la celda que tiene a su izquierda, de modo que las filas anteriores no ganan nada quedándose. Las implementaciones reales aceptan el trato y guardan dos filas en lugar de la tabla entera, lo que lleva la memoria de m × n a min(m, n): para dos cadenas de mil caracteres, de cerca de un millón de celdas a dos mil. Lo que renuncian es exactamente lo que está dibujado arriba. La distancia sobrevive en la última celda, pero el camino hasta ella vivía en las filas sobrescritas, así que una implementación de dos filas puede decirte que dos cadenas están a tres ediciones de distancia y no cuáles tres. Recuperar el camino sin la cuadrícula completa es más difícil de lo que parece; Hirschberg lo resolvió en 1975 partiendo la tabla por la mitad y descendiendo recursivamente por ambas mitades.

Problema resuelto al detalle

La secuencia de edición de menor coste para convertir kitten en sitting 5 pasos
Convierta kitten en sitting. Halle la secuencia de edición de menor coste y demuestre que no existe ninguna más económica; después, calcule cuánto cuesta esto cuando la segunda palabra es un diccionario entero.
1. La relación de recurrencia constituye todo el algoritmo. Cada casilla calcula el coste de llegar hasta ella eliminando, insertando o alineando los dos caracteres actuales (siendo esta última opción gratuita cuando coinciden). Una casilla solo necesita sus tres vecinas situadas encima y a su izquierda, de modo que un único barrido de izquierda a derecha llena la tabla.
  
  $d_{i, j} = min ⎩ ⎨ ⎧ d_{i - 1, j} + 1 d_{i, j - 1} + 1 d_{i - 1, j - 1} + [a_{i} \neq = b_{j}]$
2. Antes de rellenar nada, acote la respuesta. Las longitudes difieren en una unidad, por lo que al menos una inserción es inevitable; además, reescribir la palabra por completo cuesta 7. La respuesta se encuentra entre ambos valores, lo que descarta de entrada la mayoría de las conjeturas.
  
  $∣ a ∣ - ∣ b ∣ = 1 \leq d \leq max (∣ a ∣, ∣ b ∣) = 7$
3. Tres ediciones bastan: sustituir k → s, sustituir e → i e insertar g. Cada una es una única edición válida y la cadena termina en la palabra destino.
  
  $k \underline{i} tten \to s \underline{i} tten \to sitt \underline{i} n \to sitting$
4. Presentar tres ediciones solo demuestra que la distancia es como máximo 3. La tabla demuestra que es exactamente 3, porque se evalúa la puntuación de cada ruta hasta la esquina inferior derecha y se toma el mínimo en cada casilla del camino. Esa es la diferencia entre encontrar una respuesta y saber que no se puede superar.
  
  $d = 3, similarity = 1 - \frac{3}{7} = 0.5714 = 57.14%$
5. El coste es de una casilla por cada par de caracteres: 42 en este caso, lo cual no es nada. Frente a un diccionario de 100 000 palabras de siete letras cada una, supone más de cuatro millones de actualizaciones de casilla para una sola búsqueda.
  
  $Θ (∣ a ∣ ∣ b ∣) = 6 \times 7 = 42 cells; d (a, c) \leq d (a, b) + d (b, c)$
Respuesta

La herramienta indica 3 y una similitud del 57,14%, que es 1 − 3/7: la distancia normalizada por la palabra más larga. Ambos valores provienen de una tabla que se puede rellenar a mano en un minuto. Lo que no escala es la propia tabla: la complejidad es Θ(mn), de modo que duplicar ambas cadenas la cuadruplica, y todos los correctores ortográficos que ha utilizado se basan en evitar precisamente esto. La solución no pasa por calcular la tabla más rápido. Consiste en que la distancia de Levenshtein satisface la desigualdad triangular, por lo que d(a, c) ≤ d(a, b) + d(b, c) permite a un índice demostrar que un candidato está demasiado lejos sin llegar a medir la distancia exacta.

$d (kitten, sitting) = 3, 1 - \frac{3}{7} = 57.14%$

Referencias (4)

The theory section ends on why nobody has a much faster algorithm. This is the result that says they probably cannot have one: A. Backurs & P. Indyk, "Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)." SIAM Journal on Computing 47(3), 1087–1097, 2018; first presented at STOC 2015.
The grid this tool fills, and why filling each cell once is enough: R. A. Wagner & M. J. Fischer, "The String-to-String Correction Problem." Journal of the ACM 21(1), 168–173, 1974 — the dynamic-programming algorithm for the edit distance Levenshtein had defined in 1965.
The fourth move in the Damerau cost model, and the survey of typing errors that argued for it: F. J. Damerau, "A technique for computer detection and correction of spelling errors." Communications of the ACM 7(3), 171–176, 1964.
Insight block 3 ends on the problem of recovering the route without keeping the grid. This is the paper that solved it: D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequences." Communications of the ACM 18(6), 341–343, 1975.

Por el equipo de 42Math · Actualizado 2026-05-21

Contrastado con fuentes publicadas. Se agradecen correcciones. Política editorial · Correcciones

Todas las lecciones de Informática →

Problemas de ejemplo

kitten → sitting - kitten → sitting es el caso de los libros de texto, y la respuesta es 3: dos sustituciones y una inserción, con un 57,14% de similitud
book → back - book → back son 2 operaciones entre dos palabras de cuatro letras, mostrado como un 50,00% de similitud
Saturday → Sunday - Saturday → Sunday requiere 3 ediciones y da un 62,50% de similitud, dos de ellas borrados
form → from (intercambio) - form → from es un único intercambio bajo Damerau–Levenshtein, que la herramienta lee como un 75,00% de similitud
Comparación de ADN - GATTACA → GCATGCG exige 4 operaciones y un 42,86% — la misma medida aplicada a secuencias