1

Distancia de Levenshtein / Distancia de Levenshtein ponderada

Si hay una cosa que debo agradecer al Concurso de Programación de Tuenti, entre otras, es el haber aprendido algoritmos de los que jamás había escuchado hablar. Otra de las cosas es el haberme demostrado a mí mismo de qué soy capaz en lo que a un concurso de programación se refiere (y he de decir que ha sido mi primero).

En esta ocasión voy a rememorar el Desafío 7 de dicho concurso, en el cual había que encontrar la forma más barata de transformar una cadena de caracteres en otra teniendo en cuenta que podemos añadir caracteres, quitar caracteres e intercambiar caracteres.

Tras buscar en Google y tal, llegué a la página de Wikipedia de la Distancia de Levenshtein, el cual sirve para ésto precisamente. La única pega es que el algoritmo considera que todas las operaciones tienen coste 1. Sin embargo en el concurso, los pesos de cada operación eran diferentes. Esta entrada, por tanto, trata del Algoritmo de Levenshtein (también conocida como Distancia de Edición), de su funcionamiento y de su ampliación para hacerlo ponderado (que es lo que se pedía en el desafío).
Leer más…