Distanta Levenstein – algoritmul de editare

Cu totii ne confruntam in viata de zi cu zi cu aplicatii informatice ce detin o cantitate uriasa de informatie si resurse. Pentru a multumi utilizatorul intr-un timp foarte scurt aceste aplicatii au dezvoltat diverse sisteme pentru a facilita accesul la informatiile detinute. Este foarte comod sa cautam pe Google (sau in oricare alt motor de cautare) ce dorim in loc sa luam o lista de cateva trilioane de site-uri pentru a face aceeasi operatie.

Una din problemele majore cu care se confrunta motoarele de cautare este neatentia end-userilor. Nu de putine ori se intampla sa scriem un cuvant gresit. Motorul de cautare Google, spre exemplu, are un sistem de sugestii ce ofera alternative la cuvintele scrise de tine, optiune ce se dovedeste una dintre cele mai utile din intreg ansamblu de facilitati ale engine-ului. Spre exemplu, daca vom scrie „prgramator” ar fi foarte util ca un sistem sa detecteze eroarea si sa ne corecteze oferindu-ne si varianta „programator”.

Ce este distanta de editare sau distanta Levenstein?

Distanta Levenstein este un algoritm ce poate ajuta la determinarea similaritatii intre expresii sau cuvinte utilizate in cautari. Functia poate fi folosita pentru a compara diverse deosebiri intre doua cuvinte. Prin distanta Levenstein se intelege numarul de caractere ce trebuie inlocuite, inserate, eliminate din prima expresie pentru a obtine a doua expresie.

Aplicabilitate

• Motoarea de cautare
• Inteligenta artificiala primitiva
• Dictionare sinonime, antonime etc.
• Cea mai lunga subsecventa comuna
• Distanta Damerau–Levenshtein
• Distanta Hamming

Probleme

1. Problema siruri2 de pe campion.
Distanta Levenshtein dintre doua siruri de caractere este egala cu numarul minim de operatii necesare pentru a transforma primul sir in celalalt. Operatiile permise sunt inserarea unui caracter, stergerea unui caracter sau inlocuirea unui caracter cu un alt caracter.

Cerinta

Cunoscand cele doua siruri de caractere, sa se determine care este numarul minim de operatii necesare pentru a transforma primul sir in cel de-al doilea sir.

Solutie

Evident, aceasta problema se rezolva prin aplicarea algoritmului clasic al distantei Levenstein. Solutia se bazeaza pe programare dinamica. De remarcat este faptul ca nu trebuie sa se faca diferenta intre majuscule si restul caracterelor.

2. Problema cuvinte1 de pe campion
Balaurul Arhirel se decide sa invete biologie, asa ca doreste sa cumpere manualul de clasa a X-a. Din pacate, acesta nu se mai gaseste pe piata, dar Balaurul reuseste sa gaseasca o copie la un prieten. Dupa ce incepe sa citeasca, Balaurul Arhirel observa ca exista greseli in copia prietenului, iar intr-un impuls de energie, se hotaraste sa corecteze manualul. El are la dispozitie un dictionar de M cuvinte dintre care trebuie sa extraga variante pentru cuvantul gresit. Asupra cuvantului gresit balaurul poate sa faca urmatoarele schimbari in asa fel incat acesta sa ajunga la o varianta din dictionar:
– poate sterge o litera ;
– poate insera o litera ;
– poate schimba o litera in alta litera.
Totusi, Balaurul Arhirel este lenes, asa ca nu doreste sa opereze mai mult de K schimbari in cuvantul gresit pentru a-l aduce la o forma corecta (existenta in dictionar).

Cerinta

Ajutati-l pe Balaurul Arhirel sa afle care dintre cuvintele din dictionar ar putea fi variante ale cuvantului gresit.

Solutie

Observam ca o complexitate ca in cazul primei solutii nu va duce la o rezolvare de 100 de puncte. Algoritmul clasic pentru determinarea distantei Levenstein, este O(n*m), unde n si m reprezinta lungimea celor doua cuvinte comparate. Asadar, O(n*m*k) va iesi cu siguranta din timpul de executie. Pentru asta, trebuie observat faptul ca noi nu suntem interesati decat de diagonala principala si (cu elementele din jurul ei) si doar de primii k pasi (avem nevoie de minim k incrementari pentru a decide daca putem sau nu transforma cuvantul in maxim k pasi). Si aceasta solutie foloseste algoritmul de editare Levenstein, implicit programare dinamica.

Imbunatatiri

• Observam ca avem nevoie de memorie O(m*n), dar dinamica necesita doar pastrarea ultimilor doua linii din matrice asa ca se poate reduce doar la O(2*n).
• Putem memora operatiile de stergere, editare, inserare separat.
• Daca suntem interesati doar de determinarea distantelor de editare ce sunt mai mici decat o valoare k, vom folosi o complexitate similara cu cea a problemei 2 din acest articol.
• Putem normaliza rezultatele in intervalul [0,1]

double _levenshtein(char* s1, char* s2) 
{
    return 1-levenshtein(s1, s2)/max(strlen(s1), strlen(s2));
}

• Putem da diverse valori de penalitate pentru inserare, inlocuire, stergere.

Completari

Puteti arunca o privire pe functia Levenstein din PHP.
Levenstein Distance pe Wikipedia.

Daca acest articol contine o greseala, selecteaza cuvintele sau fraza gresita si tasteaza combinatia de taste Shift + Enter sau apasa click aici pentru a o raporta. Multumim!