Algorithme de Wagner-Fischer

L'algorithme de Wagner-Fisher est un algorithme de recherche de distance de Levenshtein. Il s'agit du nombre minimum d'opérations à effectuer pour passer d'une chaine à une autre en n'utilisant que 3 opérations : suppression d'un caractère, insertion d'un caractère ou modification d'un caractère.

Description

Le principe est de trouver le coût minimal pour passer d'une chaine à l'autre. L'idée est d'écrire une fonction récursive d(i,j) qui va renvoyer le nombre minimum de transformations pour rendre les sous chaînes A[1..i] et B[1..j] identiques. La solution est alors donnée par d(n1; n2). On a alors 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 moins coûteux entre :

• rendre égales A[1..i-1] et B[1..j] et supprimer la lettre A[i] : cela a un coût de d(i-1;j)+1;

• rendre égales A[1..i] et B[1..j-1] et insérer la lettre B[j] : cela a un coût de d(i; j-1)+1;

• rendre égales A[1..i-1] et B[1..j-1] et changer A[i] en B[j] : cela a un coût de d(i-1;j-1)+1.

On peut donc calculer d récursivement, pour ne pas refaire les mêmes calculs plusieurs fois, stocker les résultats dans un tableau.

En pseudo-code on peut faire ainsi.

   entier inf = 1000000000;
   entier maxN = 10000;
   entier maxD = 100;
   tableau [maxN][maxD*2+10];
   fontion editDistance(entier i, entier j, chaine u, chaine 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;
       }
       référence sur un entier &res=dyna[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);
       res=min(res, editDistance(i+1, j+1, u, v)+!(u[i]==v[j]));
       renvoyer res;
   }

ou en C++ :

   #include <iostream>
   #include <string>
   using namespace std;
   const int inf = 1000000000;
   const int maxN = 10000;
   const int maxD = 100;
   int dyna [maxN][maxD*2+10];
   int abs(int a)
   {
       if(a>0)
           return a;
       return -a;
   }
   int editDistance(int i, int j, const string& u, const string& v )
   {
       if(i==u.size())
       {
           return v.size()-j;
       }
       if(j==v.size())
       {
           return u.size()-i;
       }
       if(abs(i-j)>maxD)
       {
           return inf;
       }
       int &res=dyna[i][i-j+maxD];
       if(res>0)
       {
           return res;
       }
       res=inf;
       res=min(res, editDistance(i+1, j, u, v)+1);
       res=min(res, editDistance(i, j+1, u, v)+1);
       res=min(res, editDistance(i+1, j+1, u, v)+!(u[i]==v[j]));
       return res;
   }

Source

• Robert A.Wagner et Michael J.Fischer : The string-to-string correction problem. Journal

of the ACM, 21(1) :168–173, 1974.

Articles connexes

• Distance de Levenshtein

• Portail de l’algorithmique