Algoritmo de Levenshtein

La distancia de Levenshtein entre dos cadenas de texto es el número mínimo de ediciones de un solo carácter —inserciones, eliminaciones y sustituciones— necesarias para transformar una cadena en la otra. Es la más conocida de las llamadas «distancias de edición»: cuanto menor es, más se parecen las dos cadenas. Por ejemplo, convertir kitten en sitting cuesta tres ediciones.

De dónde viene

La definió el matemático soviético Vladímir Levenshtein en 1965 (su traducción al inglés apareció en 1966), en un artículo sobre códigos capaces de corregir errores. Fue el primero en formalizar esta distancia y demostrar que se comporta como una verdadera medida de distancia.

Cómo se calcula

El cálculo se hace por programación dinámica, rellenando una matriz que compara los prefijos de ambas cadenas: cada celda combina las soluciones de los subproblemas más pequeños. El algoritmo clásico para ello es el de Wagner y Fischer (1974), y su coste es proporcional al producto de las longitudes de las dos cadenas. Hay incluso un resultado teórico reciente que sugiere que ese coste cuadrático es, en esencia, insuperable salvo que caigan ciertas conjeturas de la teoría de la complejidad.

Propiedades y parientes

La distancia de Levenshtein es una métrica: cumple, entre otras, la desigualdad triangular. Tiene parientes cercanos: la distancia de Hamming, que solo permite sustituciones y exige cadenas de igual longitud, y la distancia de Damerau-Levenshtein, que añade una cuarta operación, el intercambio de dos caracteres contiguos, muy útil para modelar erratas de tecleo.

Para qué sirve

Sus aplicaciones son numerosas: la corrección ortográfica y el autocompletado, el cotejo aproximado de cadenas (fuzzy matching), la detección de plagio y, muy destacada, la bioinformática, donde comparar secuencias de ADN es, en el fondo, medir cuántas mutaciones —inserciones, deleciones o sustituciones de nucleótidos— las separan.