Algoritmul Wagner-Fischer este un algoritm de editare distanță între șiruri. Calculul este general, este suficient să vă acordați o distanță între caractere. Prin urmare, îl putem aplica cazului particular al distanței Levenshtein .
Distanța de editare dintre două șiruri de caractere este numărul minim de operații de editare elementare necesare pentru a transforma primul șir în al doilea (sau invers, prin simetria distanței).
În cazul distanței Levenshtein, există trei operații de editare elementare: inserarea, ștergerea sau înlocuirea unui caracter și fiecare are un cost de 1. Putem aplica algoritmul lui Wagner și Fischer doar în cazul a două operații: inserarea și ștergerea. În acest caz, substituția este echivalentă cu o ștergere urmată de o inserție și are un cost de 1 + 1 = 2.
Principiul este de a găsi costul minim pentru a transforma un canal în altul. Ideea este de a scrie o funcție recursivă d (i, j) care returnează numărul minim de transformări pentru a face șirurile A [1..i] și B [1..j] identice. Soluția este dată de d (n1; n2). Avem două cazuri: fie A [i] = B [j] și d (i; j) = d (i-1; j-1), fie avem o literă diferită și trebuie să alegem apoi cel mai mic cost între cele trei posibilități:
• faceți egal A [1..i-1] și B [1..j]. Pentru aceasta, eliminăm litera A [i]. Acesta are un cost de d (i-1; j) +1 (dacă eliminarea are un cost de 1);
• faceți egal A [1..i] și B [1..j-1]. Pentru aceasta, inserăm litera B [j]. Acesta are un cost de d (i; j-1) +1 (dacă inserția are un cost de 1);
• faceți egal A [1..i-1] și B [1..j-1]. Pentru aceasta înlocuim B [j] cu A [i]. Acesta are un cost de d (i-1; j-1) +1 (dacă înlocuirea are un cost de 1).
Din descrierea dată mai sus, este evident că putem calcula d recursiv. Pentru a evita repetarea acelorași calcule de mai multe ori, care ar avea un cost de calcul prohibitiv, rezultatele intermediare sunt stocate într-o matrice (memoizare).
În pseudo-cod putem face acest lucru.
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; }