Rabin-Karp algoritam
U informatici Rabin-Karp algoritam je algoritam za pretragu niski koji su stvorili Majkl O. Rabin i Ričard Karp 1987. godine, koji koristi heširanje da pronađe bilo koju kombinaciju niski u tekstu. Za tekst dužine n i p kombinacija dužine m, prosečna i najbolja vremenska složenost iznosi O (n + n) u prostoru O (p), ali je njegova najgora vremenska složenost O (nm). Nasuprot tome, Aho-Korasik algoritam za pronalaženje niski ima asimptotsku najgoru vremensku složenost O (n +m) u prostoru O (m).
Praktična primena Rabin-Karp algoritma je otkrivanje plagijata. Uzimajući u obzir izvorni materijal, Rabin-Karp može brzo da vrši pretragu preko papira za lokaciju rečenica izvornog materijala, zanemarujući detalje kao što su veličina slova i znakove interpunkcije. Zbog obilja traženih niski, algoritmi za pretragu pojedinačnih niski su nepraktični.
Pretraga podniske u pokretu i konkurentski algoritmi uredi
Algoritam grube sile za pretragu podniske proverava sve moguće pozicije:
function NaiveSearch(string s[1..n], string sub[1..m])
for i from 1 to n-m+1
for j from 1 to m
if s[i+j-1] ≠ sub[j]
jump to next iteration of outer loop
return i
return not found
Ovaj algoritam radi dobro u mnogim praktičnim slučajevima, ali može da se izvršava relativno dugo za određene primere, kao što je pretraga niza od 10.000 slova a, nakon kojeg sledi slovo b u nizu od 10 miliona slova a , u tom slučaju on ispoljava najgoru vremensku složenost O (mn).
Knut-Moris-Prat algoritam smanjuje ovu složenost na O (n) koristeći računanje unapred da bi ispitao svaki tekstualni karakter samo jednom, Bojer Mur-algoritam za pretragu niske preskače ne 1, već što je više moguće da bi pretraga uspela, i efikasno smanjuje broj puta koji smo iterativno pristupili sloljašnjoj petlji, tako da broj karaktera koji su ispitani teži ka n / m u najboljem slučaju. Rabin-Karp algoritam se umesto toga fokusira na ubrzanju linija 3-6.
Upotreba heširanja za pretragu podniske u pokretu uredi
Umesto da sprovodi prefinjenije preskakanje, Rabin-Karp algoritam pokušava da ubrza testiranje podudaranja obrazaca podniski u tekstu upotrebom heš funkcija. Heš funkcija je funkcija koja pretvara sve niske u numeričku vrednost, koja se zove heš vrednost, na primer, da imamo heš ("zdravo") = 5. Rabin-Karp koristi činjenicu da ako su dve niske jednake, njihove heš vrednosti su jednake. Dakle, čini se da sve što treba da uradimo je da izračunamo heš vrednost podniske koju tražimo, a zatim pronađemo podnisku sa istom vrednošću.
Međutim, ovde postoje dva problema. Prvi, zato što postoji toliko različitih niski, da bi heš vrednosti bile male moramo dodeliti nekim niskama isti broj. To znači da ako se heš vrednosti poklapaju, niske ne moraju da se poklapaju; moramo da potvrdimo da se poklapaju, što može da potraje dugo vremena za duže niske. Srećom, dobra heš funkcija nam obećava da se za najrazumnije ulaze ovo neće dogoditi previše često, što nam daje dobro prosečno vreme pretrage.
Algoritam je prikazan:
function RabinKarp(string s[1..n], string sub[1..m])
hsub := hash(sub[1..m]); hs := hash(s[1..m])
for i from 1 to n-m+1
if hs = hsub
if s[i..i+m-1] = sub
return i
hs := hash(s[i+1..i+m])
return not found
Linije 2, 5, 7 O (m) vremena. Međutim, linija 2 će se izvršiti samo jednom, a linija 5 će se izvršiti samo ako se heš vrednosti podudaraju, što je malo verovatno da će se dogoditi više od nekoliko puta. Linija 4 se izvršava n puta, ali zahteva konstantno vreme. Dakle, jedini problem je linija 7.
Ako naivno ponovo izračunamo heš vrednost za podnisku s[i+1..i+m], to bi zahtevalo O (m) vremena, a pošto se izvršava za svaku petlju, algoritam bi zahtevao O (mn) vremena, isto kao i najnaivniji algoritami. Trik za rešavanje ovoga je da promenljiva hs već sadrži heš vrednost s[i..i+m-1]. Ako možemo iskoristiti ovo da izračunamo narednu heš vrednost u konstantnom vremenu, onda je naš problem rešen.
Ovde koristimo nešto što se zove kotrljajući heš. Kotrljajući heš je heš funkcija specijalno napravljena da omogući ovu operaciju. Jedan jednostavan primer je sabiranje vrednosti svakog karaktera u podstringu. Zatim, možemo da koristimo ovu formulu za izračunavanje sledeće heš vrednost u konstantnom vremenu:
s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]
Ova jednostavna funkcija radi, ali će dovesti do toga da se 5. red izvršava češće od drugih složenih kotrljajućih heš funkcija.
Primetimo da ako baš nemamo sreće, ili imamo veoma lošu heš funkciju kao što je konstantna funkcija, postoji dobra šansa da će se 5. linija izvršiti n puta, pri svakoj iteraciji petlje. Zato što zahteva O (m) vremena, ceo algoritam ima vremensku složenost u najgorem slučaju O (mn).
Korišćena heš funkcija uredi
Glavna stvar kod izvođenja Rabin-Karp algoritma je efikasno izračunavanje heš vrednost uzastopnih podniski u tekstu. Korišćena i efikasna kotrljajuća heš funkcija tretira svaku podnisku kao broj u nekoj bazi, a baza je obično veliki prost broj. Na primer, ako je podniska "hi", a baza je 101, heš vrednost će biti 104 × 101 1 + 105 × 101 0 = 10609 (ASCII od 'h' je 104, a od 'i' je 105).
Tehnički, ovaj algoritam je samo sličan stvarnom broju u ne-decimalnom sistemu, jer na primer možemo imati "bazu" sa manje od jedne "cifre“. Suštinska korist postignuta takvim prikazivanjem je da je moguće da se izračuna heš vrednost sledeće podniske od prethodne koristeći samo konstantan broj operacija, nezavisno od dužine podniske.
Na primer, ako imamo tekst "abrakadabra" i mi smo u potrazi za uzorkom dužine 3, možemo izračunati heš od "bra" iz heša od "abr" (prethodna podniska) oduzimanjem broja koji je dodat za prvo "a" u "abr", odnosno 97 × 101 2 (97 je ASCII za "a" i 101 je baza koju koristimo), množenjem baze i dodavanjem poslednjeg 'a' od "bra", odnosno 97 × 101 0 = 97. Ako su u pitanju podniske koje su dugačke, ovaj algoritam postiže velike uštede u poređenju sa mnogim drugim heširanjima.
Teoretski, postoje i drugi algoritmi koji mogu da obezbede pogodno izračunavanje, npr. množenjem ASCII vrednosti svih znakova, tako da pomerajući podniz bi podrazumevao samo deljenje prvim znakom i množenjem poslednjim. Ograničenje, međutim, je ograničena veličina int i neophodnost korišćenja modularne aritmetike radi smanjivanja heš rezultata. Naivne heš funkcije, koje ne bi mogle da proizvedu velike brojeve velikom brzinom, kao npr dodavanje ASCII vrednosti, verovatno će izazvati mnoge heš kolizije a i samim tim usporiti algoritam. Otuda je obično najupotrebljivija Rabin-Karp heš funkcija.
Rabin-Karp i pretraga po više obrazaca uredi
Rabin-Karp je za pretragu pojedinačnih obrazaca lošiji od Knut-Moris-Prat algoritma, Bojer Moore algoritma za pretragu niski i nekih drugih algoritama zbog svog sporog ponašanja u najgorem slučaju. Ipak, Rabin-Karp je algoritam izbora za pretragu po više obrazaca.
To jest, ako želimo da pronađete bilo koji obrazac fiksne dužine u tekstu, npr k, možemo da napravite jednostavnu varijantu Rabin-Karp koji koristi Blum filter ili set strukture podataka da bi proverili da li heš datog niza pripada skupu heš vrednosti obrazaca koje tražimo:
function RabinKarpSet(string s[1..n], set of string subs, m):
set hsubs := emptySet
foreach sub in subs
insert hash(sub[1..m]) into hsubs
hs := hash(s[1..m])
for i from 1 to n-m+1
if hs ∈ hsubs and s[i..i+m-1] ∈ subs
return i
hs := hash(s[i+1..i+m])
return not found
Pretpostavljamo da sve podniske imaju fiksnu dužinu m.
Naivni način pretrage za k obrazaca je da se ponovi pretraga pojedinačnih obrazaca koja se izvršava za O (n) vremena, u ukupnom iznosu od O (nk). Nasuprot tome, varijanta Rabin-Karp od malopre može da pronađe sve k obrasce u O (n + k) vremenu, jer heš tabela proverava da li je heš podniske jednak nekom od šablona heševa u O (1).
Reference uredi
Literatura uredi
- Karp, Richard M.; Rabin, Michael O. (1987). „Efficient randomized pattern-matching algorithms” (PDF). 31 (2). Arhivirano iz originala (PDF) 20. 09. 2006. g. Pristupljeno 14. 10. 2008.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. „The Rabin–Karp algorithm”. Introduction to Algorithms (2nd izd.). Cambridge, Massachusetts: MIT Press. str. 911–916. ISBN 978-0-262-03293-3.
- K. Selçuk Candan; Maria Luisa Sapino (2010). Data Management for Multimedia Retrieval. Cambridge University Press. str. 205—206. ISBN 978-0-521-88739-7. (for the Bloom filter extension)