[C++, programare dinamică] Distanța Levenshtein

Fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Se dau două șiruri de caractere A și B, formate din litere mici ale alfabetului englez. Asupra șirului A putem face următoarele trei operații:

1. Inserăm un caracter.
2. Ștergem un caracter.
3. Înlocuim un caracter cu orice alt caracter din alfabetul folosit.

Se cere determinarea numărului minim de operații necesare transformării șirului de caractere A in șirul de caractere B.

Cele două șiruri de caractere se citesc din fișierul lev.in, iar numărul minim de operații se va afișa în fișierul lev.out.

Exemplu:

lev.in           lev.out
---------        ---------
afara            3
afacere

Explicație: se inserează caracterele c și e după afa și se înlocuiește ultimul a cu e.

Problema cere determinarea distanței Levenshtein dintre cele două șiruri de caractere. Aceasta este o distanță de editare, adică un metric folosit pentru măsurarea gradului de asemănare a doua șiruri.

Algoritmul de rezolvare este similar cu algoritmul de găsire a celui mai lung subșir comun. De fapt, cel mai lung subșir comun poate fi privit ca o distanță de editare în care operațiile permise sunt doar inserarea unui caracter și ștergerea unui caracter.

Pentru a rezolva această problemă, vom construi o matrice D unde D[i][j] = numărul minim de operații necesare transformării secvenței A[1, i] în secvența B[1, j]. Răspunsul problemei va fi evident D[lungime(A)][lungime(B)].

Vom trata mai întâi cazurile de bază, presupunând că indicii șirurilor încep de la 1:

1. Pentru a transforma o secvență A[1, i] în secvența nulă B[0, 0] trebuie evident să ștergem toate caracterele din secvența A[1, i], deci D[i][0] = i pentru i de la 0 la lungime(A).
2. Pentru a transforma secvența A[0, 0] într-o secvență B[1, i] trebuie să adăugăm i caractere secvenței A[0, 0], deci D[0][i] = i pentru i de la 0 la lungime(B).

Să presupunem acum că știm valorile D[p][q], D[p + 1][q] și D[p][q + 1] pentru niște poziții p și q valid alese. Putem atunci calcula D[p + 1][q + 1] considerând următoarele cazuri:

1. A[p + 1] == B[q + 1], caz în care putem face abstracție de caracterele A[p + 1] și B[q + 1], fiind suficient să transformăm A[1, p] în B[1, q], lucru pe care îl putem face cu D[p][q] operații.
2. Altfel, fie transformăm A[1. p] în B[1, q + 1] după care ștergem caracterul A[p + 1], fie transformăm A[1, p + 1] în B[1, q] după care inserăm caracterul B[q + 1], fie transformăm A[1, p] în B[1, q] după care înlocuim A[p + 1] cu B[q + 1].

    Așadar:

    D[p + 1][q + 1] = 1 + minim(D[p][q], D[p + 1][q], D[p][q + 1]).

Implementarea prezentată folosește tipul de date string, în care caracterele sunt numerotate de la 0. Rezolvarea însă nu suferă nici o modificare majoră, fiind necesar doar să scădem 1 când accesăm un caracter. Prezentăm doar funcția relevantă, restul programului fiind aproape identic cu cel prezentat în cardul problemei celui mai lung subșir comun.

Se poate face și de această dată optimizarea de a păstra doar două linii ale matricei D, deoarece pentru a calcula un rând al matricei nu folosim decât valori de pe aceeași linie sau de pe linia anterioară. Mai mult, la această problemă este puțin probabil să avem nevoie de reconstituirea soluției.

Am precizat la început că distanța Levenshtein este o distanță de editare dintre două șiruri. Pentru cei interesați prezentăm succint și alte distanțe de editare:

• Distanța Hamming, care se aplică asupra a două șiruri A și B de lungime egală și este egală cu numărul de poziții i pentru care A[i] != B[i].
• Distanța Damerau – Levenshtein, care adaugă operația de interschimbare setului de operații
  permise de distanța Levenshtein.
• Distanța Lee, care calculează sumă din min(|A[i] - B[i]|, σ - |A[i] - B[i]|) pentru fiecare caracter i, unde σ ≥ 2 este dimensiunea alfabetului folosit.

Exerciții:

a) Complexitatea algoritmului de calcul a distanței Levenshtein este O(N·M), unde N și M reprezintă lungimile celor două șiruri. Putem însă optimiza algoritmul dacă știm că putem transforma șirul A în șirul B într-un număr relativ mic de operații k. Cum ne poate ajuta această informație?

b) Considerăm existența unor costuri pentru fiecare operație precum și pentru caracterele asupra cărora se efectuează operații. Scrieți un program care rezolvă această variantă a problemei.

c) Scrieți un program care afișează noul șir A pentru fiecare operație efectuată.

d) Scrieți un program care determină numărul minim de caractere care trebuie inserate într-un șir pentru a-l transforma într-un palindrom.