El algoritmo Wagner-Fischer es un algoritmo de distancia de edición entre cadenas. El cálculo es general, basta con darte una distancia entre personajes. Por tanto, podemos aplicarlo al caso particular de la distancia de Levenshtein .
La distancia de edición entre dos cadenas de caracteres es el número mínimo de operaciones de edición elementales necesarias para transformar la primera cadena en la segunda (o viceversa, por simetría de la distancia).
En el caso de la distancia de Levenshtein, las operaciones de edición elementales son tres: inserción, eliminación o sustitución de un carácter, y cada una tiene un costo de 1. También podemos aplicar el algoritmo de Wagner y Fischer en el caso de dos operaciones solo: inserción y eliminación. En este caso, la sustitución equivale a una eliminación seguida de una inserción y tiene un costo de 1 + 1 = 2.
El principio es encontrar el costo mínimo para transformar un canal en otro. La idea es escribir una función recursiva d (i, j) que devuelva el número mínimo de transformaciones para que las subcadenas A [1..i] y B [1..j] sean idénticas. La solución está dada por d (n1; n2). Tenemos dos casos: o A [i] = B [j] yd (i; j) = d (i-1; j-1), o tenemos una letra diferente, y luego debemos elegir el menor costo entre las tres posibilidades:
• igualar A [1..i-1] y B [1..j]. Para eso quitamos la letra A [i]. Esto tiene un costo de d (i-1; j) +1 (si la remoción tiene un costo de 1);
• igualar A [1..i] y B [1..j-1]. Para eso insertamos la letra B [j]. Esto tiene un costo de d (i; j-1) +1 (si la inserción tiene un costo de 1);
• igualar A [1..i-1] y B [1..j-1]. Para eso sustituimos B [j] por A [i]. Esto tiene un costo de d (i-1; j-1) +1 (si la sustitución tiene un costo de 1).
De la descripción dada arriba, es obvio que podemos calcular d recursivamente. Para evitar repetir los mismos cálculos varias veces, lo que tendría un costo de cálculo prohibitivo, los resultados intermedios se almacenan en una matriz (memorización).
En pseudocódigo podemos hacerlo.
entier inf = 1000000000; entier maxN = 10000; entier maxD = 100; tableau cache [maxN][maxD*2+10]; // Initialement initialisé à -1 fonction editDistance(entier i, entier j, chaîne u, chaîne v ) { si(i==taille(u)) { renvoyer taille(v)-j; } si(j==taille(v)) { renvoyer taille(v)-i; } si(valeur_absolue(i-j)>maxD) { renvoyer inf; } entier res=cache[i][i-j+maxD]; si(res>0) { renvoyer res; } res=inf; res=min(res, editDistance(i+1, j, u, v)+1); res=min(res, editDistance(i, j+1, u, v)+1); si(u[i]==v[j]) { res=min(res, editDistance(i+1, j+1, u, v)); } sinon { res=min(res, editDistance(i+1, j+1, u, v)+1); } cache[i][i-j+maxD]=res; renvoyer res; }