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).
El algoritmo para el cálculo de la Distancia de Levenshtein está definido como el mínimo número de operaciones que hacen falta para transformar una palabra en otra, siendo estas operaciones la inserción, la eliminación y la sustitución de caracteres (como ya dijimos arriba). Se trata de un algoritmo de tipo bottom-up, muy común en la programación dinámica.
Siendo n la longitud de la cadena1 (cadena origen) y m la longitud de la cadena2 (cadena destino), el algoritmo usa una matriz de tamaño (n+1) x (m+1). Esta matriz la vamos a representar de modo que su origen (0,0) se encuentra en la esquina superior izquierda, así que las filas crecen hacia abajo. Vamos a ver los pasos que da el algoritmo para computar dicha distancia. En nuestro ejemplo intentaremos transformar concurrentes en vidas:
- Asignamos a n el valor de la longitud de la cadena concurrentes.
Asignamos a m el valor de la longitud de la cadena vidas.
Creamos una matriz de 0..n filas y 0..m columnas. Es decir, pondremos en vertical nuestra palabra de partida, y en horizontal nuestra palabra objetivo. - Inicializamos la primera fila de 0 a m y la primera columna de 0 a n.
Una vez tenemos inicializada la matriz a los valores que queremos, tenemos que poblarla. Una vez poblada del todo, vamos a obtener la distancia mínima en la celda (n,m).
Para poblar la matriz tenemos que tener en cuenta que el elemento (i,j) será el mínimo entre:
- La celda inmediatamente superior más 1: matrix[i-1][j] + 1.
- La celda inmediatamente a la izquierda más 1: matrix[i][j-1] + 1.
- La celda diagonal superior izquierda. En este caso hay dos alternativas:
- Si cadena1[i-1] == cadena2[j-1], entonces sería el valor de la diagonal tal cual: matrix[i-1][j-1].
- Si cadena1[i-1] != cadena2[j-1], entonces sería el valor de la diagonal más 1: matrix[i-1][j-1] + 1.
Estas operaciones las repetiríamos para todo (i,j). Veamos el primer paso del algoritmo:
En este paso, vamos a poner el valor de matrix[1][1]. Para ello vamos a asignar a esta celda el valor mínimo entre las tres celdas dichas previamente. De modo que tenemos:
- matrix[0][1] + 1 = 2.
- matrix[1][0] + 1 = 2.
- cadena1[0] != cadena2[0], por tanto vamos a usar matrix[0][0] + 1 = 1.
De este modo obtenemos el valor 1 para dicha celda. Si continuamos con dicho algoritmo, llegaremos a algo así:
Fijémonos en la última operación. En este caso estamos dando valor a la celda matrix[n][m]. Calculamos el mínimo entre:
- matrix[n-1][m] + 1 = 12.
- matrix[n][m-1] + 1 = 13.
- cadena1[n] == cadena2[m], por tanto usamos matrix[n-1][m-1] = 11, sin sumarle nada.
Obtenemos entonces que la celda matrix[n][m] es igual a 11. Como hemos acabado, éste es el resultado que devolvemos. El coste de transformar concurrentes en vidas es de 11 unidades. Además hemos podido comprobar que las palabras apenas tenían similitud y por esta razón obtenemos un coste muy elevado.
El código fuente de este algoritmo podemos encontrarlo en la propia página de Wikipedia sobre la Distancia de Levenshtein en diferentes lenguajes.
Hasta aquí todo muy bien, todo muy sencillo. Sin embargo, recordando la razón de por qué cuento este algoritmo, en el desafío 7 del concurso de programación nos pedían que las operaciones de inserción, eliminación y sustitución tuvieran pesos distintos de 1. Es el momento en que piensas en buscar por la red acerca de esta modificación del algoritmo, y es el momento en el que te encuentras que o bien no sabes buscar ni en inglés ni en español, o es que no hay una especificación del algoritmo ponderado o un código en alguno de los lenguajes más populares.
Bien, pues veamos cómo extender este algoritmo para poder aceptar diferentes pesos. En este caso nuestro ejemplo va a ser más corto, y vamos a transformar la palabra cosa en la palabra casco. Además vamos a hacer que cueste más sustituir una letra que eliminar e insertar juntas. De este modo, vamos a usar los siguientes costes:
- Inserción: coste 2.
- Eliminación: coste 3.
- Sustitución: coste 6.
Para este algoritmo modificado, las etapas van a ser las siguientes:
- Asignamos a n el valor de la longitud de la cadena cosa.
Asignamos a m el valor de la longitud de la cadena casco.
Creamos una matriz de 0..n filas y 0..m columnas. Es decir, pondremos en las columnas nuestra palabra de partida, y en las filas nuestra palabra objetivo. - Inicializamos la primera fila de 0 a m y la primera columna de 0 a n.
- Los pesos son distintos esta vez, de modo que vamos a aplicar lo siguiente:
- Multiplicamos toda la primera columna por el coste de eliminación.
- Multiplicamos toda la primera fila por el coste de inserción.
Si seguimos estos primeros tres pasos de inicialización, obtendremos lo siguiente:
Ahora, es el momento de las iteraciones. Si recordamos, en el algoritmo básico elegimos el mínimo entre la celda superior +1, la celda a la izquierda +1 y la celda diagonal superior izquierda (+1 si los caracteres no eran iguales).
En esta ocasión, vamos a sustituir todos esos 1′s por los nuevos valores, de modo que queda de la siguiente manera a la hora de obtener el mínimo:
- Celda superior: matrix[i-1][j] + coste de eliminacion.
- Celda izquierda: matrix[i][j-1] + coste de inserción.
- La celda diagonal superior izquierda, que pueden ocurrir dos cosas:
- Si cadena1[i-1] == cadena2[j-1], entonces sólamente es el coste de matrix[i-1][j-1].
- Si cadena[i-1] != cadena2[j-1], entonces es matrix[i-1][j-1] + coste de sustitución.
Sabiendo esto, hagamos los dos primeros casos:
En este caso tenemos que sacar el mínimo entre 2+3 (matrix[i-1][j]+coste eliminacion), 3+2 (matrix[i][j-1]+coste inserción) y 0 (matrix[i-1][j-1] y nada más, porque C == C). Sigamos:
Esta vez sacamos el mínimo entre 0+3 (celda superior + eliminación), 6+2 (celda izquierda + inserción) y 3+6 (diagonal + sustitución, porque C != O).
Si continuamos de esta forma hasta el final, llegamos a:
Ahora es el momento entonces de comparar ambos algoritmos en lo que a código se refiere. En este caso voy a usar Java para ilustrar el ejemplo ya que no necesita hacer uso de punteros, y facilita la explicación.
Este es el código del Algoritmo de Levenshtein básico, en Java:
public class LevenshteinDistance {
private static int minimum(int a, int b, int c) {
if(a <= b && a <= c)
return a;
if(b <= a && b <= c)
return b;
return c;
}
public static int computeLevenshteinDistance(String str1, String str2) {
return computeLevenshteinDistance(str1.toCharArray(), str2.toCharArray());
}
private static int computeLevenshteinDistance(char[] str1, char[] str2) {
int[][] distance = new int[str1.length+1][str2.length+1];
for(int i = 0; i <= str1.length; i++)
distance[i][0] = i;
for(int j = 0; j <= str2.length; j++)
distance[0][j] = j;
for(int i = 1; i <= str1.length; i++) {
for(int j = 1; j <= str2.length; j++) {
distance[i][j]= minimum(distance[i-1][j] + 1, distance[i][j-1] + 1, distance[i-1][j-1] + ((str1[i-1] == str2[j-1]) ? 0 : 1));
}
}
return distance[str1.length][str2.length];
}
}
Para poder ejecutar dicho código en cualquier programa propio necesitaríamos hacer algo parecido a:
LevenshteinDistance.computeLevenshteinDistance("cosa", "casco");
Ahora veamos el algoritmo modificado para el caso ponderado:
public class WeightedLevenshteinDistance {
private static int minimum(int a, int b, int c) {
if(a <= b && a <= c)
return a;
if(b <= a && b <= c)
return b;
return c;
}
public static int computeLevenshteinDistance(String str1, String str2, int add, int delete, int substitute) {
return computeLevenshteinDistance(str1.toCharArray(), str2.toCharArray(), add, delete, substitute);
}
private static int computeLevenshteinDistance(char[] str1, char[] str2, int insert, int delete, int substitute) {
int[][] distance = new int[str1.length+1][str2.length+1];
for(int i = 0; i <= str1.length; i++)
distance[i][0] = i * delete;
for(int j = 0; j <= str2.length; j++)
distance[0][j] = j * insert;
for(int i = 1; i <= str1.length; i++) {
for(int j = 1; j <= str2.length; j++) {
distance[i][j]= minimum(distance[i-1][j] + delete, distance[i][j-1] + insert, distance[i-1][j-1] + ((str1[i-1] == str2[j-1]) ? 0 : substitute));
}
}
return distance[str1.length][str2.length];
}
}
La forma de invocar a esta función es análoga a la anterior (para nuestro caso de ejemplo):
WeightedLevenshteinDistance.computeLevenshteinDistance("cosa", "casco", 2, 3, 6);
Podemos comprobar que en la línea 22 hemos multiplicado la primera columna por el coste de eliminación, en la línea 24 hemos multiplicado la primera fila por el coste de inserción y en las líneas 29-31 incluimos los costes de inserción, eliminación y sustitución.
También está disponible este código en nuestro repositorio.
Hasta aquí llega la entrada de hoy. Recordemos que en ella hemos aprendido cómo funciona el algoritmo de la distancia de edición (Algoritmo de Levenshtein) tanto en su forma básica como en su forma ponderada, y hemos visto el código en Java para dichos algoritmos (lo cual no era fácil de encontrar para el caso ponderado, al menos yo no lo encontré).
Un saludo para los lectores.
Buena explicación
Una de las típicas prácticas de Algorítmica en Informática.
Saludos,
Jorge