A Rabin-Karp vagy Karp-Rabin algoritmus egy szubsztring keresési algoritmus , amelyet Richard M. Karp és Michael O. Rabin (1987) hoztak létre . Ez a módszer hash függvény segítségével keresi a megadott minták (azaz alsztringek) halmazát a szövegben . Az algoritmust nem széles körben használják egyetlen alfejléc-keresésekhez, de elméleti jelentőségű, és nagyon hatékony többszörös rész-kereséshez.
Az n karakter hosszúságú szövegek és az p teljes hosszúságú m részhosszak esetében az átlagos bonyolultság O-ban ( n + m ) van megadva, míg a memória O-ban (p). De a legrosszabb esetben komplexitása O ( nm ), ami megmagyarázza viszonylag korlátozott használatát. Ehhez képest az Aho-Corasick karakterlánc-keresési algoritmus aszimptotikus, a legrosszabb esetben bonyolult O-ban (n + m), míg O-ban (m) memória-felhasználás .
Ennek az az előnye, hogy képes egy láncban k aláncot találni, amely k lánc halmazában van , átlagos O ( n + m ) komplexitással , k méretétől függetlenül . Így hatékonysága több alszöveg keresésére, esetektől és írásjelektől függetlenül, hasznosvá teszi a plágium felismerését .
Ellentétben azzal a naiv algoritmussal, amely közvetlenül összehasonlítja a mintát karakterenként karakterrel a szöveg összes alszövegével, a Rabin-Karp algoritmus összehasonlítja a minta ujjlenyomatát a szöveg alszövegének ujjlenyomataival, hogy összehasonlításokat és részrészeket törjen meg mint egyetlen karakter.
Ez az algoritmus sok valós esetben jól működik, de bizonyos marginális esetekben viszonylag hosszú időket is elérhet, például 10 000 "A" mintát találhat, amelyet egyetlen "B" követ, 10 millió "A" szövegben - ebben az esetben , az idő eléri a legrosszabb komplexitást O-ban ( mn ).
A naiv algoritmus összehasonlítja az összes lehetséges pozíciót:
1. for i from 1 to n-m+1 2. for j from 1 to m 3. if texte[i+j-1] ≠ motif[j] 4. passer à la prochaine itération de i 5. résultat trouvé : i 6. résultat non trouvéA Knuth - Morris - Pratt algoritmus előszámítással csak egyszer vizsgálja meg a szöveg minden elemét (a 4. sor ugrása közvetlenül az i még nem vizsgált következő értékéhez megy ), O ( n ) összetettségével .
A Boyer - Moore algoritmus a lehető legtöbb karaktert kihagyja minden sikertelen mérkőzésen, legjobb esetben csak n / m összehasonlítással.
A Rabin - Karp algoritmus célja a 2. és a 3. sor összehasonlításának felgyorsítása.
A fent említett lenyomatok összehasonlítása nem elegendő, mert a lehetséges lenyomatok számának korlátozása (összehasonlításuk javítása érdekében) azt eredményezi, hogy több minta képes megfelelni ugyanazon lenyomatnak. Ezért szükséges, hogy amikor az ujjlenyomatok megegyeznek, hasonlítsák össze magukat a láncokat, ami megnöveli a teljes időt. A cél tehát ezeknek a karakterlánc-összehasonlításoknak a korlátozása a hash függvénynek köszönhetően (lásd alább).
Feltételezve, hogy a T szöveget és az M mintát karaktertömbökként ábrázolják, hogy a T hossza nagyobb, mint az Mé , és hash- függvényt ad magának , a Rabin-Karp algoritmus a következő:
rabin_karp(T, M) 1 n ← longueur(T) 2 m ← longueur(M) 3 hn ← hach(T[1..m]) 4 hm ← hach(M[1..m]) 5 pour i de 0 à n-m+1 faire 6 si hn = hm 7 si T[i..i+m-1] = M[1..m] 8 résultat trouvé : i 9 hn ← hach(T[i+1..i+m]) 10 résultat non trouvéA 3., 4., 7. és 9. sor O-ban van ( m ). De a 3. és 4. sort csak egyszer hajtják végre, a 7. sort pedig csak akkor, ha az ujjlenyomatok megegyeznek, aminek ritkának kell lennie. A 6. sort n -szer végrehajtják , de állandó időt igényel. A költséges sor tehát a 9. sor.
A T [i + 1..i + m] szubsztrátum lábnyomának naiv újraszámításához időre lenne szükség O ( m ) -ben , és ahogy az egyes hurkokon történik, az algoritmus O-ban ( mn ) lenne, mint a naiv algoritmus . A trükk itt az, hogy észrevesszük, hogy a hn változó már tartalmazza a T [i..i + m-1] lábnyomát. Ha lehetőség van arra, hogy kiszámolja a következő alapterületet fix idővel, akkor a probléma megoldódna.
Ehhez használjon legördülő hash funkciót (in) . Ez egy hash funkció, amelyet kifejezetten egy ilyen művelet lehetővé tesznek. Egyszerű példa az egyes karakterek értékeinek összeadása az alsorban. Így ezt a képletet használhatjuk a következő ujjlenyomat kiszámításához, állandó időben:
T [i + 1..i + m] = T [i..i + m-1] - T [i] + T [i + m]
Ez az leegyszerűsítő funkció működik, de gyakoribbá válhat a 7. sorban, mint a kifinomultabb funkciók, például a következő fejezetben bemutatottak.
Ne feledje, hogy balszerencse vagy nagyon rossz hash függvény esetén a 7-es sort n -szer meg lehet futtatni , a hurok minden egyes áthaladásakor; és mivel O ( m ) -ben van , az algoritmus végül O-ban ( nm ) lesz.
Ha a karaktereket számként ábrázoljuk egy adott b alapban (a gyakorlatban, ha a karakterkódolást 8 biten végezzük, ami 256 lehetséges karaktert ad, akkor egy 256 alapot használunk), és kiválasztunk egy megfelelő q számot , a hash függvény:
hash(t) = t modulo qahol t a szöveg számként való ábrázolása a b alapban .
Vegyük például a következő tizedesjegyű szöveget:
6 5 8 2 4 6 9 1 3A 10. alapot választjuk, és az ebben a szövegben szereplő szöveg természetesen a szám lesz:
658246913Ha a 11-es számot választjuk , akkor a hash függvény a következő lesz:
hash(t) = t modulo 11van
hash(658246913) = 658246913 modulo 11 = 5Ez a hash függvény az a tulajdonsága, hogy képes könnyen kiszámítható a lábnyom T [i + 1..j + 1] függvényében, hogy a T [i..j] . Az előző példában, ha a hash (582) kifejezést a hash (658) függvényében akarjuk kifejezni , láthatjuk, hogy
582 = 58×10 + 2 = (658 - 600) × 10 + 2honnan
hash(582) = [ (hash(658) - hash(600)) × 10 + 2 ] modulo 11Ez a példa bármely bázist általánosít, bármilyen q egész számmal . Így, az előző pszeudokód, i ⩾ 1, akkor ezt az utat, hogy frissítse a változó h T a hash a T [i + 1..i + l M ] alkalmazásával, hogy az al- előző húr , már kiszámítva:
hT ← (hT - T[i]×blM-1) × b + T[i+lM] modulo qA Rabin hash a Rabin-Karp algoritmus népszerű és hatékony gördülő hash függvénye, amelynek teljesítménye közvetlenül kapcsolódik az egymást követő szöveges alszövegek hashainak kiszámításának hatékonyságához. Ez a függvény az egyes alszövegeket egy adott bázis számaként kezeli, általában nagy prímszámként. Például, ha az alsáv "ha" és a 101 alap, a lábnyom 104 × 101 1 + 97 × 101 0 = 10601 lesz ( a "h" ASCII értéke 104, az "a "é pedig 97).
Az ilyen függvény használatának lényeges érdeke, hogy lehetővé teszi a következő alszalag alapterületének kiszámítását az előzőtől, állandó műveletek számával, függetlenül az alsávok hosszától.
Például az "abracadabra" szöveggel és 3 karakteres mintázatot keresve az első "abr" alsor ujjlenyomata a 101 bázis segítségével:
// ASCII a = 97, b = 98, r = 114. hach(« abr ») = (97 × 1012) + (98 × 1011) + (114 × 1010) = 999509A következő alrész, a "melltartó" ujjlenyomatát az "abr" ujjlenyomatából kiszámítjuk, kivonva az "abr" első "a" -jához hozzáadott számot, vagy 97 × 101 2 , megszorozva az alappal és hozzáadva a „melltartó” utolsó „a” -ja, azaz 97 × 101 0 , így:
// base empreinte ancien 'a' nouveau 'a' hach(« bra ») = [101 × (999509 - (97 × 1012))] + (97 × 1010) = 1011309Ha a szóban forgó alszövegek hosszúak, ez az algoritmus sok időt takarít meg más hash függvényekhez képest.
Elméletileg léteznek más algoritmusok, amelyek lehetővé teszik a könnyű újraszámolást, például az egyes karakterek ASCII-értékeinek szorzása közöttük, így az alssorszakasz eltolása csak az első karakterrel való osztást eredményezi, és az utolsó karakterrel való szorzást. Ez a korlátozás az egész típusú méretkorlátozásból és a hash eredmények csökkentésének moduláris aritmetika használatából adódik (lásd a hash függvény cikket ). Ezzel szemben az egyszerű hash függvények nem hoznak létre nagyon gyorsan nagy számokat, de az ASCII értékek egyszerű hozzáadásához hasonlóan sok ujjlenyomat ütközést okozhatnak, és ezért lassíthatják az algoritmust. Ezért a Rabin - Karp algoritmus fent leírt funkciójának előnyben részesítése.
A Rabin - Karp algoritmus a legrosszabb esetekben is alacsonyabb rendű, mint Knuth - Morris - Pratt , Boyer - Moore vagy másoké , mivel egyetlen mintát talált. Előnyös algoritmus azonban több mintázat megtalálásához .
Így, ha nagyszámú k rögzített hosszúságú mintát szeretne találni a szövegben, létrehozhat egy egyszerű változatot a Rabin - Karp algoritmusból, amely egy Bloom szűrőt vagy egy Ensemble adatstruktúrát használ annak ellenőrzésére, hogy egy adott karakterlánc ujjlenyomat-e egy sor lenyomatai a keresett mintákat, és a szöveg T , egy sor mintát m hosszúságú m :
rabin_karp_ensemble(T, M, m) 1. n ← longueur(T) 2. hm ← ensemble vide 3. '''pour chaque''' S '''de l’ensemble''' M 4. '''ajoute''' hach(S[1..m]) '''à''' hm 5. ht ← hach(T[1..m]) 6. '''pour''' i '''de''' 1 '''à''' n-m+1 7. '''si''' ht ∈ hm '''et''' T[i..i+m-1] ∈ M 8. résultat trouvé : i 9. ht ← hach(T[i+1..i+m]) 10. résultat non trouvéÖsszehasonlítva a k minták megkeresésének naiv módjával, ha egyetlen mintakeresést ismételünk meg O ( n ) -ben, ami O ( n k ) keresést eredményez , a fenti algoritmus változata az összes k mintát megtalálhatja O-ban ( n + k ) várható, mert egy lábnyomtáblázat lehetővé teszi annak ellenőrzését, hogy az alszalag lábnyoma megegyezik-e az O (1) egyik mintázatával .