Algoritmul Rabin-Karp

Algoritmul Rabin-Karp este un algoritm de căutare în șiruri de caractere, creat de Michael Rabin și Richard Karp și care folosește hashingul pentru a găsi un subșir al șirului de căutat. Pentru un text de lungime n și un șablon de lungime m, complexitatea în timp cea mai bună și cea medie este de O(n), dar în cazurile cele mai rele, ea este de O(mn), și de aceea algoritmul nu este folosit pe scară largă. Totuși, el prezintă avantajul că are aceeași complexitate indiferent de numărul de șabloane căutate. O utilizare practică a acestui algoritm este detecția plagiatului. Cu ajutorul algoritmului Rabin-Karp se pot căuta rapid mai multe propoziții din documentul sursă în același timp în documentul suspect. Din cauza numărului mare de șiruri care se caută, algoritmii de căutare care oferă performanțe la căutarea unui singur șir sunt nepractici.

Utilizarea funcțiilor hash modificare

Algoritmul Rabin-Karp caută să accelereze testarea egalității șablonului cu subșirurile textului cu ajutorul unei funcții hash. Aici, se folosește o funcție hash care convertește orice șir într-o valoare numerică. Rabin-Karp exploatează faptul că dacă două șiruri sunt egale, valorile hash-urilor lor sunt egale. Astfel, ar putea părea că tot ce trebuie făcut este calculul valorii hash a șablonului, și apoi căutat un subșir cu aceeași valoare a hash-ului.

Însă, deoarece există multe șiruri, vor exista mai multe șiruri diferite cu aceeași valoare a hash-ului. Deci, dacă se potrivesc valorile hash, șirurile s-ar putea să nu fie identice; trebuie să se facă o verificare suplimentară în acest sens, verificare care ar putea să dureze mult pentru subșirurile lungi. Dar o funcție hash bună promite că pentru cele mai rezonabile intrări, aceasta nu se întâmplă prea des, timpul mediu de căutare rămânând scurt.

Algoritmul poate fi descris de următorul pseudocod:

 1 function RabinKarp(string s[1..n], string sub[1..m])
 2     hsub := hash(sub[1..m])     
 3     for i from 1 to n-m+1
 4         if hs = hsub
 5             if s[i..i+m-1] = sub
 6                 return i
 7         hs := hash(s[i+1..i+m])
 8     return not found

Liniile 2, 5, și 7 necesită fiecare timp Θ(m). Totuși, linia 2 se execută doar o dată, iar linia 5 se execută doar dacă valorile hash sunt identice, ceea ce se poate întâmpla doar de câteva ori. Linia 4 se execută de n ori, dar necesită timp constant. Deci singura problemă rămâne linia 7.

Dacă se recalculează cu totul hash-ul pentru subșirul s[i+1..i+m], aceasta ar necesita un timp Θ(m), și deoarece aceasta se face la fiecare buclă, algoritmul ar necesita timp Ω(mn), la fel ca cei mai simpli algoritmi. Soluția acestei probleme este de a observa că variabila hs conține deja valoarea hash-ului șirului s[i..i+m-1]. Dacă acest lucru poate fi folosit pentru a calcula următoarea valoare hash în timp constant, problema este rezolvată.

Acest lucru se realizează cu ceea ce se numește hash rulant. Un hash rulant este o funcție hash proiectată special pentru a activa această operație. Un exemplu simplu este adunarea valorilor fiecărui caracter din subșir. Atunci, se poate folosi această formulă pentru a calcula următoarea valoare hash în timp constant:

 s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

Această funcție simplă funcționează, dar are ca rezultat execuția prea deasă a liniei 5.

Într-un caz extrem, sau în cazul unei funcții hash foarte slabe, cum ar fi cea constantă, linia 5 ar putea fi executată chiar de n ori, la fiecare iterație. Deoarece ea necesită un timp Θ(m), întregul algoritm durează Θ(mn).

Funcția hash folosită modificare

Cheia performanței algoritmului Rabin-Karp este calculul eficient al funcției hash a subșirurilor succesive de text. O funcție populară și eficientă de hash rulant tratează fiecare subșir ca un număr într-o anume bază, baza fiind de regulă un număr prim mare. De exemplu, dacă subșirul este "hi" iar baza este 101, valoarea hash este 104 × 101¹ + 105 × 101⁰ = 10609 (codul ASCII al lui 'h' este 104 iar al lui 'i' este 105).

Beneficiul obținut de o astfel de reprezentare este că se poate calcula valoarea hash a următorului șir pe baza celui anterior efectuând doar un număr constant de operații, independent de lungimea subșirului.

De exemplu, dacă avem textul "abracadabra" și căutăm un șablon de lungime 3, se poate calcula hash-ul lui "bra" pe baza hash-ului lui "abr" (șirul anterior) scăzând numărul adăugat pentru primul a din "abr", adică 97 × 101² (97 este codul ASCII al lui 'a' iar 101 este baza folosită), înmulțind cu baza și adăugând pentru ultimul a din "bra", adică 97 × 101⁰ = 97. Dacă subșirurile în discuție sunt lungi, algoritmul are performanțe foarte bune comparativ cu multe alte scheme de hashing.

Teoretic, există alți algoritmi care furnizează o recalculare convenabilă, cum ar fi înmulțirea valorilor ASCII ale tuturor caracterelor astfel încât deplasarea la următorul subșir presupune împărțirea la primul caracter și înmulțirea cu ultimul. Limitarea este, însă, vine de la dimensiunea limitată a reprezentării unui număr întreg și necesitatea folosirii aritmeticii modulare pentru a scala rezultatele hash-ului; în același timp, acele funcții hash simple care nu produc numere mari repede, cum ar fi adăugarea de valori ASCII, pot cauza multe coliziuni și deci ar încetini algoritmul. Astfel, funcția hash descrisă este de obicei cea preferată în algorimtul Rabin-Karp.

Bibliografie modificare

Lucrarea originală a lui Karp și Rabin: Karp, Richard M.; Rabin, Michael O. (Martie 1987). "Efficient randomized pattern-matching algorithms". IBM Journal of Research and Development 31 (2), 249-260.