11.2. Rabin-Karp algoritmus

Az előző módszernél újra és újra megvizsgáljuk T egyes elemeit. A soron következ ő módszernél egy tömbelemet rendszerint elegendő kétszer megvizsgálni. A módszer lényege a következő: mind a mintához, mind a szöveg mintával megegyez ő hosszúságú részeihez egy-egy számot rendelünk egy hasítófüggvény felhasználásával. A szöveg egymást átfedő ilyen részeihez tartozó számokat könnyen

Procedure EGYSZERű-MINTAILLESZTő(T,P) 
Input: T szöveg, P minta 
Eredmény: illeszkedés esetén figyelmeztetés 
1 n = T.hossz 
2 m = P.hossz 
3 for s = 0 to n − m do 
4    if P[1..m] == T[s + 1..s + m] then 
5       kiír( A minta előfordul s eltolással ) 
6    endif 
7 endfor 

meghatározhatjuk, csak a belépő és kilépő tömbelemeket kell felhasználni a számolás során. Az s eltolásnál a számhoz a következő értéket rendeljük

Ugyanez s + 1 eltolásnál

azaz az eggyel eltolt mintához tartozó mennyiség a minta határainál található értékek alapján meghatározható. Mivel hosszabb minta esetén kényelmetlen a dm méretű számokkal dolgozni, érdemes a hányados módszert használni egy q prímszámmal, s a korábbi mennyiségek maradékaival számolni. A 2. táblázatban a Rabin-Karp algoritmusa futását követhetjük nyomon, ahol q = 17 és d = 2. A táblázatból látható, hogy a minta hasítóértéke 14. Az első öt eltolás esetén a szöveg megfelelő részeinél a hasítóértékek három esetben egyeznek meg ezzel, de mint azt már láttuk, hogy az ütközéseknél nem feltétlenül egyeznek meg a kulcsok. Esetünkben is csak az 1 eltolásnál egyezik meg a minta a szöveg megfelelő részével. Mivel csak a hasítóértékek egybeesésénél kell a szövegrészek egyezését figyelni, a bonyolultság nagyjából O(m + n). A rabin. htm állomány egy olyan programot tartalmaz, amely véletlen módon generált szövegre és mintára végrehajta a Rabin-Karp módszert. A pontok jelzik a teljes szöveget, a kék számok a hasító értéket, a piros számok az ütközést, a zöld számok minta illesztését jelzik. A számok szöveg megvizsgált betűit jelölik, az aláhúzások az eltolásra utalnak.

11.2. táblázat - 2. táblázat. Rabin-Karp algoritmus


Procedure RABIN-KARP-ILLESZTő(T,P,d,q) 
Input: T szöveg, P minta, d egész, q prím 
Eredmény: illeszkedés esetén figyelmeztetés 
1  n = T.hossz 
2  m = P.hossz 
3  h = dm−1 mod q 
4  p = 0 
5  t = 0 
6  for i = 1 to m do 
7     p = (dp + P[i]) mod q 
8     t = (dt + T[i]) mod q 
9  endfor 
10 for s = 0 to n − m do 
11    if p == t then 
12       if P[1..m] == T[s+1..s+m] then 
13          kiír ( A minta előfordul s eltolással )
14       endif 
15    endif 
16    if s ≤ n − m then 
17       t = (d(t − T[s + 1]h) + T[s + m + 1]) mod q 
18    endif 
19 endfor