Algoritmul Rabin-Karp

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 13 iunie 2021; verificările necesită 3 modificări .

Algoritmul Rabin-Karp este un algoritm de căutare de șiruri care caută un model, adică un subșir, într-un text folosind hashing . A fost proiectat în 1987 de Michael Rabin și Richard Karp . [unu]

Algoritmul este rar utilizat pentru potrivirea unui singur model, dar are o importanță teoretică considerabilă și este foarte eficient în potrivirea mai multor modele de aceeași lungime. Pentru un text de lungime n și un model de lungime m , timpul său mediu și cel mai bun de execuție este O ( n ) cu alegerea corectă a funcției hash (vezi mai jos), dar în cel mai rău caz are o eficiență de O ( nm ) , care este unul dintre motivele pentru care nu este utilizat pe scară largă. Pentru aplicațiile în care căutarea fals pozitive este acceptabilă, adică în cazul în care unele dintre aparițiile găsite ale modelului pot să nu se potrivească de fapt cu modelul, algoritmul Rabin-Karp rulează într-un timp O( n ) garantat și cu o alegere adecvată a funcției hash randomizate ( vezi mai jos) probabilitatea de eroare poate fi făcută foarte mică. De asemenea, algoritmul are o caracteristică unică de a găsi oricare dintre k șiruri date de aceeași lungime în medie (cu alegerea corectă a funcției hash) în timp O( n ), indiferent de dimensiunea lui k .

Una dintre cele mai simple aplicații practice ale algoritmului Rabin-Karp este detectarea plagiatului. Să presupunem, de exemplu, că un student scrie o lucrare despre Moby Dick . Profesorul convizional găsește diverse materiale sursă Moby Dick și extrage automat o listă de propoziții din acele materiale. Apoi algoritmul Rabin-Karp poate găsi rapid exemple de apariții ale unor propoziții din materialele sursă din articolul verificat. Pentru a face algoritmul mai puțin sensibil la diferențele mici, detalii precum majusculele sau semnele de punctuație pot fi ignorate prin eliminarea acestora. Deoarece numărul de șiruri pe care îl căutăm, k , este foarte mare, algoritmii obișnuiți de căutare a unui singur șir devin ineficienți.

Căutare subșiruri prin schimbare și algoritmi concurenți

Sarcina principală a algoritmului este de a găsi un șir de lungime m , numit model , într-un text de lungime n . Unul dintre cei mai simpli algoritmi pentru această sarcină caută pur și simplu subșirul în toate locurile posibile:

1 funcție NaiveSearch( șir s[1..n], șir sub[1..m]) 2 pentru i de la 1 la n-m+1 3 pentru j de la 1 la m 4 dacă s[i+j-1] ≠ sub[j] 5 merge la următoarea iterație a buclei exterioare 6 return i 7 return negăsit

Acest algoritm funcționează bine în multe cazuri practice, dar este complet ineficient, de exemplu, la găsirea unui șir de 10 mii de caractere „a” urmate de „b” într-un șir de 10 milioane de caractere „a”. În acest caz, arată cel mai prost timp de execuție Θ ( mn ).

Algoritmul Knuth-Morris-Pratt reduce acest timp la Θ( n ), folosind precalcularea o dată pentru fiecare caracter al textului; Algoritmul Boyer-Moore omite nu doar un caracter, ci cât mai multe posibile pentru ca căutarea să reușească, reducând efectiv numărul de iterații prin bucla exterioară, astfel încât numărul de caractere cu care trebuie comparat poate fi comparabil cu n/m cel mai bun la. Algoritmul Rabin-Karp se concentrează în schimb pe accelerarea liniilor 3-6, care vor fi discutate în secțiunea următoare.

Folosind hashing pentru a găsi subșiruri prin deplasarea

În loc să folosească o ignorare mai inteligentă, algoritmul Rabin-Karp încearcă să accelereze verificarea echivalenței modelului cu subșiruri din text folosind o funcție hash . O funcție hash este o funcție care convertește fiecare șir într-o valoare numerică numită valoare hash (hash) ; de exemplu, putem avea hash-ul șirului „hello” egal cu 5. Algoritmul folosește faptul că, dacă două șiruri sunt la fel, atunci și valorile lor hash sunt, de asemenea, aceleași. Astfel, tot ce ne trebuie este să calculăm valoarea hash a subșirului căutat și apoi să găsim subșirul cu aceeași valoare hash.

Cu toate acestea, există două probleme asociate cu aceasta. Primul este că, deoarece există atât de multe șiruri diferite, poate apărea o coliziune între două șiruri diferite - coincidența hashurilor lor. În astfel de cazuri, este necesar să se verifice potrivirea subșirurilor în sine caracter cu caracter, ceea ce necesită mult timp dacă aceste subșiruri sunt lungi (această verificare nu este necesară dacă aplicația dvs. permite rezultate false pozitive). Cu funcții hash rezonabil de bune (vezi mai jos), coliziunile sunt extrem de rare și, ca urmare, timpul mediu de căutare este scurt.

Exemplu de algoritm (codul sursă al aplicației):

1 funcție RabinKarp( șir s[1..n], șir sub[1..m]) 2 hsub := hash(sub[1..m]) 3 hs := hash(s[1..m]) 4 pentru i de la 1 la (n-m+1) 5 dacă hs = hsub 6 dacă s[i..i+m-1] = sub 7 return i 8 hs := hash(s[i+1..i +m]) 9 return nu a fost găsit

Liniile 2, 3 și 6 au nevoie de timp pentru a fi executate . Cu toate acestea, liniile 2 și 3 sunt executate o singură dată, iar linia 6 este executată numai atunci când valorile hash se potrivesc, ceea ce se întâmplă rar. Linia 5 este executată o dată, dar întotdeauna durează constant. $\Omega (m)$ $n$

A doua problemă este recalcularea hashului. s[i+1..i+m]Este nevoie de timp pentru a recalcula în mod naiv valoarea hash a unui subșir , și deoarece acest lucru se face în fiecare buclă, algoritmul va petrece timp , care este același lucru pe care îl petrec majoritatea algoritmilor simpli. Soluția la această problemă este să presupunem că variabila conține deja valoarea hash a subșirului . Dacă îl folosiți pentru a calcula următoarea valoare hash în timp constant, atunci problema este rezolvată. $O(m)$ $\Omega (mn)$ hss[i..i+m-1]

Acest lucru se realizează prin utilizarea a ceea ce este cunoscut sub numele de hash inel . Cel mai simplu exemplu de hash inel este să adăugați valorile fiecărui caracter ulterior într-un subșir și apoi să utilizați această formulă pentru a calcula fiecare valoare hash ulterioară într-o perioadă fixă de timp:

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

O astfel de formulă nu oferă nicio garanție că coliziunile nu vor avea loc des și este foarte ușor să vă asigurați că în majoritatea aplicațiilor, atunci când o utilizați, expresia din linia 6 va fi executată mai des decât atunci când utilizați alte aplicații mai „inteligente”. ” funcții hash de inel.

Rețineți că dacă avem foarte ghinion sau avem o funcție hash foarte proastă, cum ar fi o funcție constantă (hash=const), linia 6 este foarte probabil să fie executată o dată, adică la fiecare iterație a buclei. Deoarece este nevoie de timp , algoritmul în sine va lua timp . $n$ $\Omega (m)$ $\Omega (mn)$

Funcția hash utilizată

Cheile performanței algoritmului Rabin-Karp sunt probabilitatea scăzută de coliziuni și calculul eficient al valorii hash a subșirurilor succesive de text. Rabin și Karp [1] au sugerat utilizarea unui așa-numit hash polinom (deși orice alt hash inel ar funcționa, de asemenea). Pentru un șablon dat , un astfel de hash este definit după cum urmează: $p[1..m]$

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

unde este un număr prim și este un număr de la până la . Valorile hash ale subșirurilor consecutive și pentru un hash polinom sunt calculate după cum urmează (rețineți că pentru eficiență, numărul este numărat înainte de procedura principală de căutare Rabin-Karp): $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]\dreapta){\bmod {q))

De exemplu, fie , în mod arbitrar, și avem textul „abracadabra” și căutăm un model de lungime 3. Putem calcula hash-ul subșirului „bra” din hash-ul subșirului „abr” (subșirul anterior) prin scăzând numărul adăugat pentru prima literă „a” din „abr”, adică ( - ASCII pentru „a”), înmulțirea cu bază și, în final, adăugarea ultimului număr pentru „sutien”, adică . Pentru a evita depășirea numărului întreg, în majoritatea implementărilor, după fiecare dintre aceste patru operații (înmulțirea în calcul este o operație separată), trebuie să luați rezultatul modulo . $x=101$ $q$ $97\times 101^{2}$ $97$ $101$ $97\times 101^{0}=97$ $97\times 101^{2}$ $q$

Rabin și Karp au demonstrat că dacă (adică fix) și un număr prim este ales aleatoriu din intervalul , atunci probabilitatea unei coliziuni la căutarea unui model într-un text de lungime nu depășește . Dar o astfel de funcție hash are două dezavantaje semnificative: în primul rând, algoritmul pentru alegerea unui număr prim aleatoriu este destul de greoi și, în al doilea rând, aritmetica modulară face ca un astfel de hash să fie foarte lent în practică (rețineți că toată aritmetica din formula pentru hashe-uri ale subșirurilor succesive). trebuie să fie modulo , adică luarea modulului va fi efectuată de patru ori). $x=2$ $X$ $q$ $[2..n^{3}]$ $n$ $O(1/n)$ $q$

Modificarea modernă a polinomului hash propusă de Ditzfelbinger și colab. [2] nu prezintă aceste neajunsuri. Diferența acestei opțiuni este că numărul prim este fix, iar numărul este selectat aleatoriu din intervalul de la până la înainte de începerea algoritmului ( nu trebuie să fie deloc prim). S-a dovedit [2] că pentru o astfel de funcție hash probabilitatea unei coliziuni la căutarea unui model într-un șir pentru unii nu depășește , în condiția naturală că pentru toți . Pentru a accelera aritmetica modulară , puteți alege o putere egală cu doi minus unu (așa-numitele prime Mersenne ): pentru mașinile pe 32 de biți este cel mai potrivit , pentru mașinile pe 64 de biți - ; modulo pentru astfel de valori este calculat folosind operații rapide pe biți [3] . O altă opțiune posibilă sunt valorile sau , pentru care există și algoritmi rapidi pentru a lua restul împărțirii cu [4] (intervalul valorilor acceptabile este ușor restrâns). Puteți alege o singură dată la începutul programului și apoi îl puteți utiliza în toate hashe-urile. $q$ $X$ $0$ $q-1$ $X$ $s[1..n]$ $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$

Concepții greșite despre hash-uri polinomiale

Încă o dată, observăm că garanțiile absenței coliziunilor oferite de hash-ul polinom sunt foarte puternice: chiar dacă cineva, știind dar neștiind , va selecta în mod specific modelul și șirul de lungime pentru căutare, astfel încât algoritmul Rabin-Karp cu un hash polinom dă cât mai multe ciocniri posibil, oricum, pentru unii (adică pentru un suficient de mare și nu super-mare ) și dacă este ales într-adevăr aleatoriu, probabilitatea chiar și a unei singure coliziuni nu va fi mai mare de , că este foarte mic. Pentru a realiza acest lucru, este important rezultatul, care este un număr prim. De exemplu, o greșeală comună este să presupunem sau (adică să nu folosiți deloc aritmetica modulară); un exemplu de șir în care se pot găsi multe coliziuni hash polinomiale pentru astfel de , și indiferent de alegerea numărului , este secvența Morse-Thue . [5] $q$ $X$ $n$ $q>n^{c)$ $c>2$ $q$ $n$ $X$ $1/n^{c-2}$ $q$ $q=2^{32}$ $q=2^{64}$ $q=2^{k)$ $X$

Următoarea interpretare a unui hash polinom este populară: fiecare șir este reprezentat de un număr cu o bază , iar apoi acest număr este luat modulo . O astfel de interpretare nu adaugă claritate naturii eficacității unui hash dat, în timp ce interpretarea unui hash polinom ca un polinom propriu cu coeficienți egali cu valorile simbolurilor duce pur și simplu la demonstrarea unei probabilități scăzute. a unei coliziuni cu o alegere aleatorie [2] : se consideră două șiruri diferite și ; hashe-urile polinomiale ale acestor șiruri sunt egale dacă și numai dacă ; dar din teorema lui Bezout rezultă că un polinom de grad care nu este identic cu zero în câmpul resturilor modulo ( se alege simplu, tocmai pentru a transforma inelul de reziduuri într-un câmp) are cel mult rădăcini, ceea ce înseamnă că probabilitatea a unei coliziuni nu depășește chiar și cu o alegere aleatorie ; prin urmare, dacă pentru unii , probabilitatea unei coliziuni a două șiruri diferite de lungime nu depășește (de unde, în special, probabilitatea unei erori pentru căutarea unui model într-un șir). $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))$ $\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$ $q>n^{c}\geq m^{c)$ $c>1$ $m$ $(m-1)/q<n/q<1/n^{c-1)$ $1/n^{c-2}$

De asemenea, uneori este posibil să întâlniți o recomandare de a folosi un număr prim ca , dar, aparent, în afară de observațiile empirice asupra unor cantități foarte limitate de date, un astfel de sfat nu mai este fundamentat. $X$

Rabin-Karp și căutarea multor exemplare

Din cauza comportamentului său lent în cel mai rău caz, algoritmul Rabin–Karp este mai rău decât algoritmul Knuth–Morris–Pratt , algoritmul Boyer–Moore și alți algoritmi de căutare rapidă a șirurilor . Cu toate acestea, algoritmul Rabin-Karp poate fi utilizat pentru a găsi un set de eșantioane în timp liniar în cel mai bun caz și timp patratic în cel mai greu de realizat cel mai rău caz; deși și aici pierde în cel mai rău caz în fața algoritmului Aho-Korasik , care are un timp de rulare liniar.

Dacă dorim să găsim orice model într-un text dat dintr-un set mare de, de exemplu, k modele de lungime egală fixă, putem modifica algoritmul Rabin-Karp utilizând un tabel hash sau orice altă structură de date pentru a verifica dacă hash-ul unui șirul dat aparține setului hash. valorile eșantionului pe care le căutăm:

function RabinKarpSet( string s[1..n], set of string subs, m) { set hsubs := pentru fiecare sub in subs

\varnothing

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

\ceașcă

hs := hash(s[1..m]) pentru i de la 1 la (n-m+1) dacă hs ∈ hsubs dacă s[i..i+m-1] = șir din subs cu hash hs return i hs := hash(s[i+1..i+m]) retur nu a fost găsit }

Alți algoritmi pot căuta un singur eșantion în timp O( n ) și, prin urmare, pot fi utilizați pentru a căuta k eșantioane în timp O( n k ). În schimb, varianta algoritmului Rabin-Karp de mai sus poate găsi toate k mostre în timpul așteptat O( n + k ), deoarece tabelul hash folosit pentru a testa cazul în care hash-ul unui subșir este egal cu hash-ul lui oricare dintre probe utilizează timpul O(1). În practică, datorită ușurinței relative de implementare și vitezei de operare, această opțiune poate fi adesea preferabilă algoritmului Aho-Korasik .

Vezi și

Note

↑ 1 2 Rabin, Karp, 1987 .
↑ 1 2 3 Dietzfelbinger, Gil, Matias, Pippinger, 1992 .
↑ SE Anderson. Trucuri care se învârtesc. Arhivat la 1 iunie 2020 la Wayback Machine
↑ Krovetz, Rogaway, 2000 .
↑ Pachocki, Radoszewski, 2013 .

Literatură

Kormen T. H. , Leyzerson C. E. , Rivest R. L. , Stein K. Algorithms: construction and analysis = Introduction to Algorithms / ed. S. N. Triguba ; pe. din engleza. I. V. Krasikov , N. A. Orehov ,N. Romanov - Ed. a II-a. - M. : Williams, 2005. - 801 p. — ISBN 5-8459-0857-4 .
Rabin MO , Karp RM Algoritmi eficienti de potrivire a modelelor randomizate // IBM Journal of Research and Development . - IBM, 1987. - T. 31 , nr. 2 . — S. 249–260 . - doi : 10.1147/rd.312.0249 .
Dietzfelbinger M., Gil J., Matias Y., Pippenger N. Funcțiile hash polinomiale sunt de încredere // Proceedings of the 19th International Coloquium on Automata, Languages and Programming (ICALP'92) . — Londra, Marea Britanie: Springer-Verlag, 1992. — p. 235–246 . - doi : 10.1007/3-540-55719-9_77 .
Krovetz T., Rogaway P. Hashing universal rapid cu chei mici și fără preprocesare: construcția PolyR // Proceedings of the International Conference on Information Security and Cryptology. - Berlin, Germania: Springer-Verlag, 2000. - p. 73–89 . - doi : 10.1007/3-540-45247-8_7 .
Pachocki J., Radoszewski J. Unde se folosește și cum nu se folosește hașarea șirurilor polinomiale // Olimpiade în informatică. - Vilnus, Lituania: Universitatea Vilnus, 2013. - V. 7 . — S. 90–100 .

Siruri de caractere
Măsuri de similitudine a șirurilor	Distanța de la Damerau la Loewenstein Distanța Levenshtein Distanța de Hamming Asemănări Jaro-Winkler
Căutare subșir	Algoritmul Boyer-Moore Algoritmul Boyer-Moore-Horspool Algoritmul Knuth-Morris-Pratt Algoritmul Rabin-Karp funcția de prefix Funcția Z Algoritmul Aho - Korasik
palindromuri	arbore palindrom Algoritmul lui Manaker
Alinierea secvenței	Algoritmul Needleman-Wunsha Algoritmul Smith-Waterman
Structuri de sufix	Matrice de sufixe Sufix automat arbore de sufix arbore de prefix
Alte	analizare Potrivire de model Cea mai mare succesiune comună Cel mai mare subșir comun