Algoritmul Rabin-Karp pentru potrivirea sirurilor

3

rabin1Potrivirea sirurilor este o problema destul de mare si are o aplicabilitate imensa in domeniul IT si nu numai.Aceasta problema insa a fost abordata de multe persoana ajungandu-se la solutii foarte eficiente.Putem spune ca sunt folosite in algoritmii intellisense, sintax highlighiting , pattern match, etc.

Problema

Se dau doua siruri S si P, se cere gasirea tuturor aparitiilor sirului P in sirul S.Fisierul sir.in contine pe pe prima linia sirul P iar pe a doua sirul S, fisierul de iesire sir.out va avea pe prima linie pozitiile in ordine crescatoare unde se gasesc potriviri.

Exemplu :
sir.in

ABA
CABBCABABAB

sir.out

2
5 7

O abordare naiva ar fi sa incercam pentru fiecare pozitie din sirul S sa gasim o potrivire a sirului P la fiecare pas.In cazul in care nu vom gasi ne vom deplasa un pas mai in fata.Aceasta abordare necesita o parcurgere intr-un timp patratic ( O(|S|*|P|) ) si implicit nu va duce la punctajele maxime ale problemelor abordate.
Solutia folosind algoritmul naiv de potrivire a sirurilor

O solutie mult mai eficienta a acestui algoritm consta in rezolvarea in timp liniar folosind algoritmul Rabin-Karp, ce are la baza hashuri.Acest algoritm are timpul de executie O(|S|+|P|).

Cum lucreaza acest algoritm?
Practic vom construi initial hash-ul patternului P si in acelasi timp a primelor |P| caractere din S.Ne putem folosi de faptul ca orice caracter are o reprezentare decimala.La fiecare pas i vom compara valoarea hash a patternului cu valoarea hash a |P| caractere din S.Daca acestea doua sunt echivalente vom considera ca avem o posibila potrivire la pasul i.Pentru a ne deplasa,pur si simplu vom elimina primul caracter si vom adauga unul in partea dreapta.
Exemplu :

cde – sirul P
abcdef – sirul S

Pasul i = 0 : hash(cde) != hash(abc) -> nu este potrivire , i++
Pasul i = 1 : hash(cde) != hash(bcd) -> nu este potriivre , i++
Pasul i = 2 : hash(cde) == hash(cde) -> potrivire , i++
Pasul i = 3 : hash(cde) != hash(def) -> nu este potriivre ,i++
STOP.

Intrebarea este cum vom elimina un caracter dintr-o valoare hash si cum vom adauga un alt caracter la acel hash?
Pentru a pastra unicitatea la fiecare pas vom inmulti intreg hash`ul cu o baza,dupa care vom adauga caracterul nou.Pentru ca aceasta valoare poate fi imensa ne vom folosi de o tehnica clasica a hash`urilor, aceasta valoare supunand`o la o reducere printr`un modul.

Pentru a construi hashul initial va trebui sa lucram asemanator ca mai jos :

hashi = (hashi-1 * baza + P[i]) % MODUL; // MODUL va avea regulile specifice unei valori de la hashuri,sa nu fie o putere a lui 2 si sa fie cat mai departe de 2 puteri ale acestui numar.

Cum stergem un caracter si cum adaugam un alt caracter la hash?

hashpos+1 = ((hashpos – (S[pos] * VV) % MODUL + MODUL) * baza + S[pos+|P|]) % MODUL; // unde pos este pozitia de inceput a subsirului, VV = (VV*baza)%MODUL, de |P| ori

Cei care stiu hash`uri isi vor pune urmatoarea intrebare : Ce se intampla cu coliziunile?Intradevar, folosind metodele de hashing + reducerea valorilor prin module vom avea riscul sa apara coliziuni.In aceasta situatie este bine sa lucram pe 2 hash`uri,astfel construim cate 2 hash`uri la fiecare subsir si daca ambele sunt potrivite atunci consideram o potrivire la pasul pos.

Solutie folosind algoritmul de potrivire a sirurilor Rabin-Karp

Un alt algoritm ce este folosit pentru potrivirea sirurilor este algoritmul Knuth-Morris-Pratt(KMP) dar acesta va fi prezentat intr-o lectie viitoare. 😀

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!

Etichete:

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

3 Comentarii

  1. Andrei Misarca spune:
    august 14, 2009 la 5:59 pm

    Un algoritm foarte folositor si bine explicat, insa lipseste un mic detaliu, fara de care implementarea poate deveni un calvar.
    Ce reprezinta defapt acel hash? Sa zicem ca am cuvantul format din literele ABCDEF…Z. El este format din N litere sa zicem.
    Practic hashul nost’ reprezinta A*P^(N-1) + B*P^(N-2) + C*P(N-3) + … + Y*P + Z modulo ceva. Si acum sa zicem ca vreau sa elimin A si sa mai adaug o litera, sa zicem U. Practic din hash scad A*P^(N-1), P^(N-1) reprezentand exact acel H1 din sursa lui Andrei de mai sus iar hashul devine B*P^(N-2) + C*P^(N-3) + … + Z. Urmatorul pas este sa inmultesc totul cu P si sa adaug U, iar treaba devine B*P^(N-1) + C*P^(N-2) + … + Z*P + U, de zici rezultand si corectitudinea algoritmului (evident pot aparea si acele cazuri de coliziune despre care a specificat Andrei in articol).

  2. Avadanei Andrei spune:
    august 14, 2009 la 6:01 pm

    Am omis doar situatia in care se va adauga un nou caracter in hash, dar am presupus ca se subintelege din crearea hash`ului pentru pattern.Multumesc de completare. 🙂

  3. Algoritmul Knuth-Morris-Pratt(KMP) pentru potrivirea sirurilor | WorldIT spune:
    noiembrie 16, 2009 la 10:04 am

    […] cu siruri de caractere si anume potrivirea unui subsir.Am prezentat doua solutii in legatura cu potrivirea sirurilor : algoritmul naiv de potrivire a sirurilor si un algoritm ce se foloseste de hashuri(Rabin-Karp) […]