Algorithme de Wagner-Fischer
L'algorithme de Wagner-Fischer est un algorithme de calcul de distance d'édition entre deux chaînes de caractères. Le calcul est général, il suffit de se donner une distance entre caractères. On peut donc l'appliquer au cas particulier de la distance de Levenshtein.
La distance d'édition entre deux chaînes de caractères est le nombre minimal d'opérations d'edition élémentaires nécessaires pour transformer la première chaîne en la seconde (ou vice versa, par symétrie de la distance).
Dans le cas de la distance de Levenshtein, les opérations d'édition élémentaires sont au nombre de trois : insertion, suppression ou substitution d'un caractère, et chacune a un coût de 1. On peut aussi appliquer l'algorithme de Wagner et Fischer au cas de deux opérations seulement : insertion et suppression. Dans ce cas, la substitution est équivalente à une suppression suivie d'une insertion et a un coût de 1 + 1 = 2.
Description
Le principe est de trouver le coût minimal pour transformer une chaîne en une autre. L'idée est d'écrire une fonction récursive d(i, j) qui retourne le nombre minimal de transformations pour rendre les sous chaînes A[1..i] et B[1..j] identiques. La solution est donnée par d(n1; n2). On a deux cas : soit A[i] = B[j] et d(i; j) = d(i-1; j-1), soit on a une lettre différente, et il faut alors choisir le moindre coût entre les trois possibilités :
• rendre égales A[1..i-1] et B[1..j]. Pour cela on supprime la lettre A[i]. Cela a un coût de d(i-1;j)+1 (si la suppression a un coût de 1) ;
• rendre égales A[1..i] et B[1..j-1]. Pour cela on insère la lettre B[j]. Cela a un coût de d(i; j-1)+1 (si l'insertion a un coût de 1) ;
• rendre égales A[1..i-1] et B[1..j-1]. Pour cela on substitue B[j] à A[i]. Cela a un coût de d(i-1;j-1)+1 (si la substitution a un coût de 1).
D'après la description donnée ci-dessus, il est évident que l'on peut calculer d récursivement. Pour éviter de refaire les mêmes calculs plusieurs fois, ce qui aurait un coût de calcul prohibitif, on stocke les résultats intermédiaires dans un tableau (mémoïsation).
Pseudo-code
En pseudo-code on peut faire ainsi.
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;
}
Source
- Robert A. Wagner et Michael J. Fischer : The string-to-string correction problem, Journal of the ACM, 21(1) :168–173, 1974. DOI 10.1145/321796.321811