La distancia de Levenshtein es el número mínimo que necesitamos para convertir una palabra en otra, un ejemplo pelo y perro tienen una distancia de 2 porque tendríamos que sustituir la l por una r y añadir una r, dos movimientos, distancia 2. Otro ejemplo, murcielago y muerdago que tienen una distancia de 5, ya que a murciélago le tenemos que quitar c,i,e,l y a muerdago le quitamos la d, por tanto necesitamos 5 movimientos para convertir una palabra en otra. Resumiendo, cuanto más pequeña sea la distancia, más parecidas son las dos palabras.

¿Esto para que sirve?, pues muy fácil, para obtener palabras similares en los buscadores o mostrar palabras alternativas por ejemplo. Vamos a ver el algoritmo y como funciona.

Este algoritmo es una matriz de n filas por m columnas donde n y m son el número de caracteres + 1 de cada palabra. El primer paso que se realiza es rellenar la primera fila y la primera columna con números secuenciales de 0 hasta n+1 y desde 0 hasta m+1 , quedando del siguiente modo para el caso del ejemplo inicial la matriz de 11×9:

Una vez tenemos la matriz inicial, empezaremos a realizar comparaciones por filas de cada caracter con el caracter de cada columna. En cada operación, obtenemos primero el peso y tres valores de los cuales deduciremos el menor de ellos como valor final y con un ejemplo lo veremos mejor.

Comenzamos comparando los caracteres, la letra «m» de murcielago (en la columna), lo comparamos con la «m» de muerdago (filas), si es el mismo caracter se le asigna un peso de 0 y si es diferente, le asignamos 1, en este caso como son iguales, le asignamos un 0. A continuación obtenemos los tres valores, el primero con la casilla superior sumándole al valor de esta un 1, en este caso 1+1=2, el siguiente con la casilla que está situada a su izquierda haciéndolo de igual modo, 1+1=2 y por último a la casilla superior izquierda, la que está situada en la diagonal a la que le sumaremos el valor del peso, 0+0=0; de estos tres valores, cogeremos el menor que en este caso es el 0. 

Vamos a por el siguiente, peso igual a 0, porque u es igual a u, por la izquierda, 0+1=1, la diagonal 1+0=1 y la superior 1+2=2, el mínimo de los tres es 1

continuando con las comparaciones y obtención del mínimo, quedaría nuestra matriz completa del siguiente modo:

El último valor, es la distancia de Levenshtein, en este caso es 5, si quisieramos ver la proporción de acierto, deberíamos obtener la la diferencia con la unidad de la relación entre la distancia y el número de caracteres del mayor en este caso, 1 – (5/10)=0,5 o 50%. La distancia de «murcielago» y «cerro muriano» es de 10, por tanto 1-(10/13)=0.2308 o del 23,08%.

El algoritmo implementado con lenguajes de programación no tiene ningún misterio para el que esté acostumbrado a las matrices, además en Wikipedia, podéis encontrar su implementación en diferentes lenguajes, por ejemplo en php ya tiene una función como tal.

¿Que utilidades podemos darle? por ejemplo palabras sugerentes en base a un diccionario o aproximaciones, corrección de ortografía, etc. y además, existen variantes del algoritmo como la de Damerau-Levenshtein, otros más complejos, algoritmos fonéticos.

Este algoritmo se lo debemos a Vladimir Levenshtein, un matemático ruso que lo desarrolló en 1965.

He hecho en C# una app de consola como muestra para obtener la matriz y en base a un diccionario, nos muestre sugerencia de palabra.