Rabin-Karp algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. június 13-án felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

A Rabin-Karp algoritmus egy karakterlánc-kereső algoritmus , amely egy mintát, azaz egy részkarakterláncot keres a szövegben hash segítségével . Michael Rabin és Richard Karp tervezte 1987 -ben . [egy]

Az algoritmust ritkán használják egyetlen minta illesztésére, de jelentős elméleti jelentőséggel bír, és nagyon hatékony több azonos hosszúságú minta egyeztetésében. Egy n hosszúságú szöveg és egy m hosszúságú minta esetén az átlagos és legjobb végrehajtási ideje O ( n ) a hash függvény megfelelő megválasztásával (lásd alább), de a legrosszabb esetben O( nm ) hatásfokú. , ami az egyik oka annak, hogy nem használják széles körben. Azoknál az alkalmazásoknál, ahol a keresési téves pozitív eredmények elfogadhatók, azaz ahol a minta talált előfordulásai nem feltétlenül egyeznek meg a mintával, a Rabin-Karp algoritmus garantált O( n ) időn belül fut, és a véletlenszerű hash függvény megfelelő megválasztásával ( lásd alább) a hiba valószínűsége nagyon kicsire tehető. Az algoritmusnak van egy olyan egyedi tulajdonsága is, hogy átlagosan (a hash függvény megfelelő megválasztásával) O( n ) idő alatt megtalálja a megadott k azonos hosszúságú karakterláncok bármelyikét , függetlenül k méretétől .

A Rabin-Karp algoritmus egyik legegyszerűbb gyakorlati alkalmazása a plágium észlelése. Tegyük fel például, hogy egy diák dolgozatot ír Moby Dickről . A rábeszélő professzor különféle Moby Dick -forrásanyagokat talál, és automatikusan kivonja a mondatok listáját ezekből az anyagokból. Ekkor a Rabin-Karp algoritmus gyorsan példákat talál egyes mondatok előfordulására az ellenőrzött cikk forrásanyagaiból. Annak érdekében, hogy az algoritmus kevésbé legyen érzékeny az apró eltérésekre, az olyan részleteket, mint a kis- és nagybetűk vagy az írásjelek , figyelmen kívül lehet hagyni azok eltávolításával. Mivel a keresett karakterláncok száma, k , nagyon nagy, a szokásos egykarakterláncú keresési algoritmusok hatástalanná válnak.

Alkarakterlánc-keresés shift és versengő algoritmusok alapján

Az algoritmus fő feladata, hogy egy n hosszúságú szövegben találjon egy m hosszúságú karakterláncot , amelyet mintának nevezünk . Az egyik legegyszerűbb algoritmus ehhez a feladathoz egyszerűen minden lehetséges helyen megkeresi az alkarakterláncot:

1 függvény NaiveSearch( string s[1..n], string sub[1..m]) 2 for i 1 -től n -m+1- ig 3 for j - hez 1 -től m 4 -ig ha s[i+j-1] ≠ sub[j] 5 ugrás a külső ciklus következő iterációjára 6 return i 7 return nem található

Ez az algoritmus sok gyakorlati esetben jól működik, de teljesen hatástalan, ha például egy 10 ezer "a" karakterből álló karakterláncot talál, amelyet "b" követ egy 10 millió "a" karakterből álló sztringben. Ebben az esetben a legrosszabb Θ ( mn ) végrehajtási idejét mutatja.

A Knuth-Morris-Pratt algoritmus ezt az időt Θ( n )-re csökkenti, az előszámítást egyszer felhasználva a szöveg minden karakteréhez; A Boyer-Moore algoritmus nem csak egy karaktert hagy ki, hanem annyit, amennyit csak lehetséges, hogy a keresés sikeres legyen, így hatékonyan csökkenti az iterációk számát a külső cikluson keresztül, így az összehasonlítandó karakterek száma n/m -hez hasonlítható. legjobb esetben. A Rabin-Karp algoritmus ehelyett a 3-6. sorok felgyorsítására összpontosít, amiről a következő részben lesz szó.

A hash segítségével részkarakterláncokat kereshet a

Az intelligensebb kihagyás helyett a Rabin-Karp algoritmus megpróbálja felgyorsítani a minta ekvivalencia ellenőrzését a szövegben lévő részkarakterláncokkal egy hash függvény segítségével . A hash függvény egy olyan függvény, amely minden karakterláncot numerikus értékké alakít, amelyet hash értéknek (hash) neveznek ; Például a "hello" karakterlánc hash-je egyenlő 5-tel. Az algoritmus azt a tényt használja, hogy ha két karakterlánc azonos, akkor a hash értéke is megegyezik. Így csak ki kell számítanunk a keresett részkarakterlánc hash értékét, majd meg kell találnunk az azonos hash értékű részstringet.

Ehhez azonban két probléma kapcsolódik. Az első az, hogy mivel nagyon sok különböző karakterlánc létezik, ütközés léphet fel két különböző karakterlánc között - a hash-eik egybeesése miatt. Ilyen esetekben maguknak a részkarakterláncoknak az illeszkedését kell karakterenként ellenőrizni, ami sok időt vesz igénybe, ha ezek a karakterláncok hosszúak (ez az ellenőrzés nem szükséges, ha az alkalmazás lehetővé teszi a hamis pozitív értékeket). Meglehetősen jó hash-függvények esetén (lásd alább) az ütközések rendkívül ritkák, és ennek következtében az átlagos keresési idő rövid.

Példa az algoritmusra (alkalmazás forráskódja):

1 függvény RabinKarp( string s[1..n], string sub[1..m]) 2 hsub := hash(sub[1..m]) 3 hs := hash(s[1..m]) 4 for i 1 -től ( n-m+1) 5 -ig ha hs = hsub 6 if s[i..i+m-1] = sub 7 return i 8 hs := hash(s[i+1..i +m]) 9 visszatérés nem található

A 2., 3. és 6. sor végrehajtása időt vesz igénybe . A 2. és 3. sor azonban csak egyszer kerül végrehajtásra, a 6. sor pedig csak akkor, ha a hash értékek egyeznek, ami ritkán történik meg. Az 5. sor egyszer kerül végrehajtásra, de mindig állandó időt vesz igénybe. $\Omega (m)$ $n$

A második probléma a hash újraszámítása. s[i+1..i+m]Időbe telik egy részkarakterlánc hash értékének naiv újraszámítása , és mivel ez minden ciklusban megtörténik, az algoritmus időt tölt , ami megegyezik a legtöbb egyszerű algoritmus elköltésével. A probléma megoldása, ha feltételezzük, hogy a változó már tartalmazza a részstring hash értékét . Ha ezt használja a következő hash érték kiszámításához állandó időben, akkor a probléma megoldódott. $O(m)$ $\Omega (mn)$ hss[i..i+m-1]

Ezt az úgynevezett gyűrű hash használatával érik el . A gyűrűs hash legegyszerűbb példája az, hogy minden egyes következő karakter értékét hozzáadjuk egy részkarakterlánchoz, majd ezt a képletet használjuk az egyes további hash-értékek kiszámításához meghatározott időn belül:

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

Egy ilyen képlet nem ad garanciát arra, hogy az ütközések ritkán fordulnak elő, és nagyon könnyű megbizonyosodni arról, hogy a legtöbb alkalmazásban a használatakor a 6. sorban lévő kifejezés gyakrabban kerül végrehajtásra, mint más, "okosabb" ” ring hash függvényeket.

Vegye figyelembe, hogy ha nagyon szerencsétlenek vagyunk, vagy nagyon rossz hash-függvényünk van, például egy állandó függvény (hash=const), akkor a 6. sort nagy valószínűséggel egyszer, azaz a ciklus minden iterációján végre kell hajtani. Mivel időbe telik , maga az algoritmus is időt vesz igénybe . $n$ $\Omega (m)$ $\Omega (mn)$

A hash függvény

A Rabin-Karp algoritmus teljesítményének kulcsa az ütközések alacsony valószínűsége és az egymást követő szövegrészek hash értékének hatékony kiszámítása. Rabin és Karp [1] egy úgynevezett polinomiális hash használatát javasolta (bár bármely más gyűrűs hash is működne). Egy adott sablon esetén egy ilyen hash meghatározása a következő: $p[1..m]$

hash(p[1..m])=\left(\sum _{i=1}^{m}p[i]x^{mi}\right){\bmod {q)),

ahol néhány prímszám, és egy szám -tól -ig . Az egymást követő részkarakterláncok és a polinomiális hash hash értékeit a következőképpen számítjuk ki (vegye figyelembe, hogy a hatékonyság érdekében a számot a fő Rabin-Karp keresési eljárás előtt számoljuk): $q$ $x$ $0$ $q-1$ $s[i..i+m-1]$ $s[i+1..i+m]$ $x^{m-1}{\bmod {q))$

hash(s[i+1..i+m])=\left((hash(s[i..i+m-1])-s[i]\cdot x^{m-1} )\cdot x+s[i+m]\right){\bmod {q))

Például legyen , tetszőlegesen, és az "abracadabra" szövegünk van, és egy 3-as hosszúságú mintát keresünk. A "bra" részkarakterlánc hash-ét az "abr" (előző részkarakterlánc) részkarakterlánc hashéből számíthatjuk ki úgy, hogy kivonjuk az első 'a' betűhöz hozzáadott számot az "abr"-ból, azaz ( - ASCII az 'a'-ból), megszorozzuk az alappal , végül hozzáadjuk az utolsó számot a "bra"-hoz, azaz . Az egész számok túlcsordulása elkerülése érdekében a legtöbb megvalósításban e négy művelet mindegyike után (a számításban a szorzás egy külön művelet) a modulo eredményt kell venni . $x=101$ $q$ $97\times 101^{2}$ $97$ $101$ $97\times 101^{0}=97$ $97\times 101^{2}$ $q$

Rabin és Karp bebizonyította, hogy ha (vagyis rögzített) és egy prímszámot véletlenszerűen választunk ki a tartományból , akkor az ütközés valószínűsége egy hosszúságú szövegben minta keresése során nem haladja meg a -t . De egy ilyen hash függvénynek két jelentős hátránya van: egyrészt a véletlen prímszám kiválasztásának algoritmusa meglehetősen nehézkes, másrészt a moduláris aritmetika a gyakorlatban nagyon lelassítja az ilyen hash-t (megjegyezzük, hogy az egymást követő részstringek kivonatainak képletében minden aritmetika modulo kell , hogy legyen, azaz a modulus felvétele négyszer megtörténik). $x=2$ $x$ $q$ $[2..n^{3}]$ $n$ $O(1/n)$ $q$

A polinomi hash Ditzfelbinger és munkatársai [2] által javasolt modern módosítása nem rendelkezik ezekkel a hiányosságokkal. Ennek az opciónak az a különbsége, hogy a prímszám fix, és a szám véletlenszerűen kerül kiválasztásra a tól és ig terjedő tartományból , mielőtt az algoritmus elindulna ( egyáltalán nem kell prímnek lennie). Bebizonyosodott [2] , hogy egy ilyen hash függvénynél az ütközés valószínűsége, amikor egy karakterláncban mintát keresünk , nem haladja meg a -t , természetes feltétel mellett, hogy az összes esetén . A moduláris aritmetika felgyorsítása érdekében választhat kettő mínusz egy hatványt (az úgynevezett Mersenne-prímek ): 32 bites gépekhez ez a legalkalmasabb , 64 bites gépekhez - ; Az ilyen értékek modulo - ját gyors bitenkénti műveletekkel számítják ki [3] . Egy másik lehetséges választás a vagy értékek, amelyekhez szintén vannak gyors algoritmusok a [4] -gyel való osztás maradékának figyelembevételére (az elfogadható értékek tartománya kissé szűkült). Csak egyszer választhat a program elején, majd minden hash-ben használhatja. $q$ $x$ $0$ $q-1$ $x$ $s[1..n]$ ${\displaystyle q>n^{c))$ $c>2$ $1/n^{c-2}$ $0\leq s[i]<q$ $i=1,2,\ldots ,n$ $q$ $q=2^{31}-1$ $q=2^{61}-1$ $q$ $q$ $q=2^{32}-5$ $q=2^{64}-59$ $q$ $x$ $x$

Tévhitek a polinomiális hashekkel kapcsolatban

Ismételten megjegyezzük, hogy a polinomi hash által biztosított ütközések hiányának garanciái nagyon erősek: még akkor is, ha valaki tudva , de nem tudva , kifejezetten kiválasztja a mintát és a hosszúságú karakterláncot a kereséshez úgy, hogy a Rabin-Karp algoritmus egy polinomiális hash a lehető legtöbb ütközést ad, mindenesetre egyeseknél (azaz kellően nagy és nem szupernagy esetén) és ha valóban véletlenszerűen választjuk, akkor akár egyetlen ütközés valószínűsége sem lesz több, mint , nagyon kicsi. Ennek eléréséhez fontos az eredmény, ami egy prímszám. Gyakori hiba például az, hogy feltételezzük vagy (vagyis egyáltalán nem használunk moduláris aritmetikát); egy példa egy karakterláncra, amelyben sok polinomi hash ütközést találhatunk ilyenekhez , és függetlenül a számválasztástól , a Morse-Thue sorozat . [5] $q$ $x$ $n$ ${\displaystyle q>n^{c))$ $c>2$ $q$ $n$ $x$ $1/n^{c-2}$ $q$ $q=2^{32}$ $q=2^{64}$ ${\displaystyle q=2^{k))$ $x$

A polinomiális hash következő értelmezése népszerű: minden karakterláncot egy számmal jelképeznek egy bázissal , majd ezt a számot modulo vesszük . Az ilyen értelmezés nem ad egyértelművé egy adott hash hatékonyságának természetét, míg a polinomi hash megfelelő polinomként való értelmezése, amelynek együtthatói megegyeznek a szimbólumok értékével, egyszerűen az alacsony valószínűség bizonyításához vezet. véletlenszerű választással való ütközésről [2] : vegyünk két különböző karakterláncot és ; ezeknek a karakterláncoknak a polinomiális hash-ei akkor és csak akkor egyenlők ; de Bezout tételéből az következik, hogy egy olyan fokszámú polinomnak , amely nem azonos a nullával a maradékok modulo mezőjében ( egyszerűre választják, pontosan azért, hogy a maradékok gyűrűjét mezővé alakítsuk) legfeljebb gyöke van, ami azt jelenti, hogy a valószínűség az ütközés mértéke még véletlenszerű választás esetén sem haladja meg ; ezért, ha néhány esetén, a két különböző hosszúságú karakterlánc ütközésének valószínűsége nem haladja meg (ezért különösen annak a valószínűsége, hogy a karakterláncban egy minta keresése során hiba lép fel). $x$ $q$ $x$ $p_{1}[1..m]$ $p_{2}[1..m]$ $\sum _{i=1}^{m}(p_{1}[i]-p_{2}[i])x^{mi}\equiv 0{\pmod {q))$ ${\displaystyle \sum _{i=1}^{m}(p_{1}[i]-p_{2}[i])x^{mi))$ $m-1$ $q$ $q$ $m-1$ $p_{1}$ $p_{2}$ $x$ $(m-1)/q$ ${\displaystyle q>n^{c}\geq m^{c))$ $c>1$ $m$ ${\megjelenítési stílus (m-1)/q<n/q<1/n^{c-1))$ $1/n^{c-2}$

Néha találkozhatunk olyan ajánlással is, hogy prímszámként használjunk , de nyilvánvalóan néhány igen korlátozott mennyiségű adatra vonatkozó empirikus megfigyelésektől eltekintve ez a tanács már nem megalapozott. $x$

Rabin-Karp és a sok példány keresése

A legrosszabb eset lassú viselkedése miatt a Rabin–Karp algoritmus rosszabb, mint a Knuth–Morris–Pratt algoritmus , a Boyer–Moore algoritmus és más gyors karakterlánc - kereső algoritmusok . Mindazonáltal a Rabin–Karp algoritmus felhasználható arra, hogy a legjobb esetben lineáris időben, a legrosszabb esetben pedig négyzetes időben találjunk meg mintákat; bár itt is veszít a legrosszabb esetben a lineáris futásidejű Aho-Korasik algoritmussal szemben.

Ha egy adott szövegben bármilyen mintát akarunk találni egy nagy halmazból, mondjuk k rögzített egyenlő hosszúságú mintából, akkor módosíthatjuk a Rabin-Karp algoritmust hash táblázat vagy bármilyen más adatstruktúra segítségével, hogy ellenőrizzük, hogy a hash adott karakterlánc a hash készlethez tartozik. mintaértékeket keresünk:

function RabinKarpSet( string s[1..n], string subs halmaza , m ) { set hsubs := minden alegységhez

\varnothing

hsubs := hsubs {hash(sub[1..m])}

\csésze

hs := hash(s[1..m]) i - nek 1 - től (n-m+1) -ig, ha hs ∈ hsubs , ha s[i..i+m-1] = karakterlánc a részekből származó hash-sel hs visszatér i hs := hash(s[i+1..i+m]) visszaküldés nem található }

Más algoritmusok képesek egyetlen mintát keresni O( n ) idő alatt, és így felhasználhatók k minta keresésére O( n k ) idő alatt. Ezzel szemben a Rabin-Karp algoritmus fenti változata meg tudja találni mind a k mintát a várható O( n + k ) idő alatt, mert a hash tábla azt az esetet teszteli, amikor egy részkarakterlánc hashje egyenlő bármelyik minta O(1) időt használ. A gyakorlatban a viszonylag egyszerű megvalósítás és a művelet gyorsasága miatt ez a lehetőség gyakran előnyösebb lehet, mint az Aho-Korasik algoritmus .

Lásd még

Jegyzetek

↑ 1 2 Rabin, Karp, 1987 .
↑ 1 2 3 Dietzfelbinger, Gil, Matias, Pippinger, 1992 .
↑ SE Anderson. Kicsit pörgős hackek. Archiválva 2020. június 1-én a Wayback Machine -nél
↑ Krovetz, Rogaway, 2000 .
↑ Pachocki, Radoszewski, 2013 .

Irodalom

Kormen T. H. , Leyzerson C. E. , Rivest R. L. , Stein K. Algorithms: construction and analysis = Introduction to Algorithms / szerk. S. N. Triguba ; per. angolról. I. V. Krasikov , N. A. Orekhov ,N. Romanov - 2. kiadás - M. : Williams, 2005. - 801 p. — ISBN 5-8459-0857-4 .
Rabin MO , Karp RM Hatékony véletlenszerű mintaillesztési algoritmusok // IBM Journal of Research and Development . - IBM, 1987. - T. 31. , 2. sz . — S. 249–260 . - doi : 10.1147/rd.312.0249 .
Dietzfelbinger M., Gil J., Matias Y., Pippenger N. A polinomiális hash függvények megbízhatóak // Proceedings of the 19th International Colloquium on Automata, Languages and Programming (ICALP'92) . – London, Egyesült Királyság: Springer-Verlag, 1992. – 235–246 . - doi : 10.1007/3-540-55719-9_77 .
Krovetz T., Rogaway P. Gyors univerzális hashing kis kulcsokkal és előfeldolgozás nélkül: a PolyR konstrukció // Proceedings of the International Conference on Information Security and Cryptology. - Berlin, Németország: Springer-Verlag, 2000. - 73–89 . - doi : 10.1007/3-540-45247-8_7 .
Pachocki J., Radoszewski J. Hol használjuk és hogyan ne használjuk a polinomiális karakterlánc -kivonatolást // Informatikai olimpiák. - Vilnius, Litvánia: Vilnus University, 2013. - V. 7 . — S. 90–100 .

Húrok
Karakterlánc hasonlósági mértékek	Távolság Damerau és Loewenstein között Levenshtein távolság Hamming távolság Jaro-Winkler hasonlóságok
Substring keresés	Boyer-Moore algoritmus Boyer-Moore-Horspool algoritmus Knuth-Morris-Pratt algoritmus Rabin-Karp algoritmus előtag funkció Z-függvény Algoritmus Aho - Korasik
palindromák	palindromfa Menedzser algoritmusa
Sorozat-igazítás	Needleman-Wunsha algoritmus Smith-Waterman algoritmus
Utótag szerkezetek	Utótag tömb Utótag automata utótag fa előtag fa
Egyéb	elemzése Mintaillesztés A legnagyobb közös sorozat Legnagyobb közös részkarakterlánc