Poređenje Rabin-Karp i naivnog algoritma
Pronalaženje svih pojavljivanja niski u tekstu je problem koji se jako često javlja u programima za uređivanje teksta. Naravno, tekst u dokumentima se menja pa traženje niski zapravo zavisi od toga šta korisnik unosi. Efikasni algoritmi za ovaj problem mogu u velikoj meri da pomognu odzivu takvih programa. Ovakvi algoritmi se pored navedene primene mogu koristiti kod pretraživanja DNK sekvenci, i raznim drugim oblastima.
Uvod uredi
Ovaj problem možemo formalizovati na sledeći način. Pretpostavimo da je tekst niz T[1...n] dužine n i neka je niska koju tražimo niz P[1...m] dužine m ≤ n. Sledeća pretpostavka jeste da su elementi nizova T i P karakteri izvučeni iz konačnog alfabeta (jezika) Σ, na primer Σ = {0,1} ili Σ = {a,b,c,...,z}. Često se karakteri nizova T i P nazivaju nizovi karaktera.
Kažemo da se niska P pojavljuje sa pomakom s u tekstu T (ili pojavljivanje niske P počinje od pozicije s+1 u tekstu T), ako 0 ≤ s ≤ n-m i T[s+1...s+m] = P[1...m] (odnosno ako T[s+j] = P[j] za svako 1 ≤ j ≤ m). Ako se niska P pojavljuje sa pomakom s onda to zovemo validno šiftovanje, u suprotnom je s nevalidno šiftovanje. Problem pronalaženja niski jeste problem pronalaženja svih valdnih šiftovanja zadate niske P u zadatom tekstu T.
Neki poznatiji algoritmi koji se bave ovim problemima su naivni algoritam, Rabin-Karp, konačni automat, Knut-Moris-Prat, Bojer-Mur-Horspul, itd. Ovde ćemo pažnju posvetiti osnovnoj ideji i poređenju Rabin-Karp i naivnog algoritma.
Terminologija uredi
Neka sa Σ* (čitamo sigma-zvezda) označimo skup svih konačnih niski koji se mogu izvesti korišćenjem karaktera iz Σ. Smatraćemo da su stringovi samo one niske koje imaju konačnu dužinu. Praznu nisku označićemo sa ε, koja takođe pripada Σ*. Dužinu niske x označićemo sa |x|. Konkatenaciju (nadovezivanje) dve niske x i y označićemo sa xy, a njihovu dužinu sa |x| + |y|, što podrazumeva da prvo idu karakteri niske x, a za njima slede karakteri niske y.
Kažemo da je niska w prefiks niske x, ako je x = wy za neki string y iz Σ*. Primetimo da je |w| ≤ |x|. Slično, kažemo da je niska w sufiks niske x, ako je x = yw za neki string y iz Σ*. Takođe važi ako je w sufiks niske x, onda je w ≤ x. Jasno je da je prazna niska ε i prefiks i sufiks svake niske. Na primer, važi da je ab prefiks niske abcca i cca sufiks niske abcca. Korisno je zapaziti da za neke niske x i y i neki karakter a, važi x je sufiks niske y ako i samo ako važi da je xa sufiks niske ya. Pored ostalog primetimo da su prefiks i sufiks tranzitivne relacije. Sad navodimo lemu koja nam će nam biti potrebna kasnije.
Lema 1 (preklapajuća sufiks lema): Pretpostavimo da su x, y i z niske tako da važi x je sufiks od z i y je prefiks od z. Ako je |x| ≤ |y|, onda je x sufiks od y. Ako je |x| ≥ |y|, onda je x prefiks od y. Ako je |x| = |y|, onda x = y.
Naivni algoritam uredi
U ovom poglavlju navešćemo samo ideju naivnog algoritma, da bi razimeli kako on radi jer nam je to potrebno pri poređenju sa Rabin-Karp algoritmom.
Naivni algoritam pronalazi sva validna šiftovanja koristeći petlju koja proverava uslov P[1...m] = T[s+1...s+m] za svako od n-m+1 mogućih vrednosti s. Pseudo-kod:
NAIVNI_STRING_ALGORITAM(T, P)
n ← duzina[T]
m ← duzina[P]
for s ← 0 to n-m do
if P[1...m] = T [s+1...s+m] then
stampaj "Niska pronadjena na pomaku s"
Naivni algoritam se može interpretirati grafički kao klizni šablon (prozor) koji sadrži nisku koja se traži u tekstu, pomerajući šablon niz tekst i poredeći sve karaktere šablona sa svim karakterima teksta, kao što je prikazano na primeru ispod:
Korak 1:
Текст: [a c a] a b c
= ≠
Ниска: [a a b]
Nevalidno šiftovanje.
Korak 2:
Текст: a [c a a] b c
≠
Ниска: [a a b]
Nevalidno šiftovanje.
Korak 3:
Текст: a c [a a b] c
= = =
Ниска: [a a b]
Validno šiftovanje.
Korak 4:
Текст: a c a [a b c]
= ≠
Ниска: [a a b]
Nevalidno šiftovanje.
U najgorem slučaju ovaj algoritam ima složenost O((n-m+1)m). Na primer, razmotrimo tekst an (tekst dužine n sa svim karakterima a) i nisku am. Za svako od n-m+1 mogućih vrednosti pomaka s, petlja for mora da uporedi odgovarajuće karaktere m puta da bi šiftovanje bilo validno. Kako je u najgorem slučaju složenost O((n-m+1)m), ako je m ceo deo od n/2 dobijamo ukupnu složenost O(n2). Ovaj algoritam je neefikasan jer informaciju koju je stekao o tekstu za jednu vrednost s, je ignorisao za drugu vrednost za s. Takve informacije mogu da budu jako korisne. Na primer, ako je za nisku P[0...2] pronađeno da je validno šiftovanje s=0, onda sigurno šiftovanja 1, 2 i 3 nisu validna pa ih ne moramo ispitivati.
Rabin-Karp algoritam uredi
Rabin i Karp su predložili algoritam pronalaženja niski u tekstu koji se pokazao dobar u praksi, i koji generalizuje druge algoritme srodnih problema kao što su dvodimenzionalno pronalaženje niski. Rabin-Karp algoritam koristi Θ(m) vremena za preprocesiranje, a u najgorem slučaju zahteva Θ((n-m+1)m). Međutim, njegovo prosečno vreme izvršavanja je bolje.
Ideja uredi
Ovaj algoritam koristi osnovne pojmove teorije brojeva kao što su ekvivalentnost dva broja po modulu trećeg broja.
Da bi pojasnili, pretpostavimo da je Σ = {0, 1, ...,9} tako da je svaki karakter decimalna cifra. U opštem slučaju možemo pretpostaviti da je svaki karakter u intervalu d gde je d = |Σ|. Onda možemo posmatrati nisku k kao uzastopne karaktere koji predstavljaju k-dužinu decimalnog broja. Na primer, niska 31415 odgovara decimalnom broju 31,415. Imajući u vidu dvostruko tumačenje ulaznih karaktera kao grafičkih simbola i cifara, pogodno je da u ovom odeljku ih posmatramo kao cifre u standardnom tekstualnom fontu.
Za datu nisku P[1...m] neka p označava odgovarajuću decimalnu vrednost. Na sličan način, za dati tekst T[1...n] neka ts označava decimalnu vrednost podteksta T[s+1...s+m] dužine m, za s = 0,1,...,n-m. Svakako, ts = p ako i samo ako T[s+1...s+m] = P[1...m], odnosno s je validno šiftovanje ako je ts = p. Ako možemo da izračunamo vrednost p u vremenu Θ(m) i sve vrednosti ts u vremenu Θ(n-m+1), onda bi mogli da odredimo sva validna šiftovanja s u ukupnom vremenu Θ(m) + Θ(n-m+1) = Θ(n) poredeći p sa svakim ts. Na trenutak zanemarimo da p i ts mogu da budu jako veliko brojevi.
Mi možemo da računamo p u vremenu Θ(m) koristeći Hornerovu šemu:
p = P[m]+10 * (P[m-1]+10 * (P[m-2]+...+10 * (P[2]+P[1]))).
Vrednost t0 se može slično izračunati iz T[1...m] u vremenu Θ(m).
Za računanje ostalih vrednosti t1,t2,...,t(n-m) potrebno je Θ(n-m) vremena, to je posledica toga da se t(s+1) računa iz ts za konstantno vreme, na sledeći način:
t(s+1) = 10 * (ts - 10(m-1) * T[s+1]) + T[s+m+1].
Na primer, neka je m=5 i ts = 31415, ako želimo da uklonimo najvišu cifru T[s+1] = 3 i dodamo novu najnižu cifru na primer 2 tako da je T[s+5+1] = 2, onda računamo sledeće:
t(s+1) = 10 * (31415 - 10000 * 3) + 2 = 14152. (једначина 1)
Uklanjanjem 10(m-1)T[s+1] najviše cifre iz ts i množenjem sa 10, šiftovali smo broj za jednu poziciju ulevo, i dodali smo na T[s+m+1] odgovarajuću najnižu cifru. Ako je konstanta 10(m-1) izračunata ranije, što može da se uradi za vreme O(log(m)) koristeći tehnike modularne aritmetike iako je za ovu primenu i O(m) prihvatljivo, onda svako izvršavanje jednakosti iz leme 1 se izvodi za konstantan broj koraka. Dakle, možemo izračunati p u vremenu Θ(n) i t0,t1,...,t(n-m) u vremenu Θ(n-m+1), i možemo pronaći sva pojavljivanja niske P[1...m] u tekstu T[1...n] sa Θ(m) preprocesorskog vremena i Θ(n-m+1) poređenja.
Jedini problem sa ovakvom procedurom jeste taj da p i ts mogu biti toliko veliki da nije ugodno raditi sa njima. Ako P sadrži m karaktera, onda pretpostavka da svaka aritmetička operacija nad p koji ima m cifara se izvršava za konstantno vreme je netačna. Srećom postoji jednostavno rešenje za ovaj problem, koje je prikazano na primeru ispod. Računanje p i ts se izvodi po modulu q. Kada izračunamo p i t0, ponavljanja iz jednačine 1 mogu se obavljati po modulu q, a videćemo da računanje p mod q možemo izračunati u Θ(m) vremenu i ts mod q u vremenu Θ(n-m+1). Modul q se generalno bira tako da 10 * q može da stane u jednu kompjutersku reč, koja omogućava da sve neophodne promene obavljamo sa jednostrukom preciznošću (eng. single-precision arithmetic). Ako uopštimo ovo, kažemo da u d-arnom jeziku {0,1,...,d-1} mi biramo q tako da d * q odgovara kompjuterskoj reči, tako da se ponavljanje jednačine 1 radi po modulu q i postaje:
t(s+1) = d * (ts - T[s+1] * h) + T[s+m+1] mod q (једначина 2),
gde je h logički ekvivalentno sa d(m-1) mod q, odnosno vrednost prve (najviše) cifre od m cifara tekstualnog prozora. Primer gde je tekst predstavljen niskom cifara T = 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 5 3, niska koja se traži je predstavljena niskom cifara P = 3 1 4 1 5, skup d čine cifre {0,1,2,3,4,5,6,7,8,9}, a za q je uzet broj 13:
Korak 1:
Текст: [2 3 5 9 0] 2 3 1 4 1 5 2 6 7 3 9 9 5 3
Ниска: [3 1 4 1 5]
(23590 mod 13 = 8) ≠ (31415 mod 13 = 7)
Nevalidno šiftovanje.
Korak 2:
Текст: 2 [3 5 9 0 2] 3 1 4 1 5 2 6 7 3 9 9 5 3
Ниска: [3 1 4 1 5]
(35902 mod 13 = 9) ≠ (31415 mod 13 = 7)
Nevalidno šiftovanje.
Korak 3:
Текст: 2 3 [5 9 0 2 3] 1 4 1 5 2 6 7 3 9 9 5 3
Ниска: [3 1 4 1 5]
(59023 mod 13 = 3) ≠ (31415 mod 13 = 7)
Nevalidno šiftovanje.
Korak 4:
Текст: 2 3 5 [9 0 2 3 1] 4 1 5 2 6 7 3 9 9 5 3
Ниска: [3 1 4 1 5]
(90231 mod 13 = 11) ≠ (31415 mod 13 = 7)
Nevalidno šiftovanje.
Korak 5:
Текст: 2 3 5 9 [0 2 3 1 4] 1 5 2 6 7 3 9 9 5 3
Ниска: [3 1 4 1 5]
(02314 mod 13 = 0) ≠ (31415 mod 13 = 7)
Nevalidno šiftovanje.
Korak 6:
Текст: 2 3 5 9 0 [2 3 1 4 1] 5 2 6 7 3 9 9 5 3
Ниска: [3 1 4 1 5]
(23141 mod 13 = 1) ≠ (31415 mod 13 = 7)
Nevalidno šiftovanje.
Korak 7:
Текст: 2 3 5 9 0 2 [3 1 4 1 5] 2 6 7 3 9 9 5 3
Ниска: [3 1 4 1 5]
(31415 mod 13 = 7) = (31415 mod 13 = 7)
Pogodak, proveravmo karakter po karakter i dobijamo da je validno šiftovanje.
Korak 8:
Текст: 2 3 5 9 0 2 3 [1 4 1 5 2] 6 7 3 9 9 5 3
Ниска: [3 1 4 1 5]
(14152 mod 13 = 8) ≠ (31415 mod 13 = 7)
Nevalidno šiftovanje.
Korak 9:
Текст: 2 3 5 9 0 2 3 1 [4 1 5 2 6] 7 3 9 9 5 3
Ниска: [3 1 4 1 5]
(41526 mod 13 = 4) ≠ (31415 mod 13 = 7)
Nevalidno šiftovanje.
Korak 10:
Текст: 2 3 5 9 0 2 3 1 4 [1 5 2 6 7] 3 9 9 5 3
Ниска: [3 1 4 1 5]
(15267 mod 13 = 5) ≠ (31415 mod 13 = 7)
Nevalidno šiftovanje.
Korak 11:
Текст: 2 3 5 9 0 2 3 1 4 1 [5 2 6 7 3] 9 9 5 3
Ниска: [3 1 4 1 5]
(52673 mod 13 = 10) ≠ (31415 mod 13 = 7)
Nevalidno šiftovanje.
Korak 12:
Текст: 2 [3 5 9 0 2] 3 1 4 1 5 [2 6 7 3 9] 9 5 3
Ниска: [3 1 4 1 5]
(26739 mod 13 = 11) ≠ (31415 mod 13 = 7)
Nevalidno šiftovanje.
Korak 13:
Текст: 2 3 5 9 0 2 3 1 4 1 5 2 [6 7 3 9 9] 5 3
Ниска: [3 1 4 1 5]
(67399 mod 13 = 7) = (31415 mod 13 = 7)
Pogodak, proveravamo karakter po karakter i dobijamo da je lažan pogodak (nevalidno šiftovanje).
Korak 14:
Текст: 2 3 5 9 0 2 3 1 4 1 5 2 6 [7 3 9 9 5] 3
Ниска: [3 1 4 1 5]
(73995 mod 13 = 9) ≠ (31415 mod 13 = 7)
Nevalidno šiftovanje.
Korak 15:
Текст: 2 3 5 9 0 2 3 1 4 1 5 2 6 7 [3 9 9 5 3]
Ниска: [3 1 4 1 5]
(39953 mod 13 = 9) ≠ (31415 mod 13 = 7)
Nevalidno šiftovanje.
Rešenje sa modulom nije idealno, jer iz činjenice da je t_s logički ekvivalentno sa p mod q ne sledi da važi t_s = p. Sa druge strane, ako t_s nije logički ekvivalentno sa p mod q onda sigurno važi t_s ≠ p, i pomak s je nevalidan. Na ovaj način možemo da koristimo test t_s logički ekvivalentno sa p mod q kao brz test za heurističko odbacivanje nevalidnih pomaka s. Bilo koji pomak s za koji važi da je t_s logički ekvivalentno sa p mod q mora biti testiran dalje da se proveri da li je to zaista validan pomak ili samo lažan pogodak (eng. spurious hit). Ovo testiranje može da se uradi eksplicitnom proverom uslova P[1...m] = T[s+1...s+m]. Ako je q dovoljno veliko, onda se nadamo da će se lažni pogodak dešavati toliko retko da dodatna cena se ne povećava mnogo.
Sledi procedura ispod prati prikazane ideje. Ulaz u proceduru jesu tekst T, niska P, radijus d i q.
RABIN_KARP_ALGORITAM(T, P, d, q)
n ← duzina[T]
m ← duzina[P]
h ← d(m-1) mod q
p ← 0
t0 ← 0
//preprocesiranje
for i ← 1 to m do
p ← (d * p + P[i]) mod q
t0 ← (d * t0 + T[i]) mod q
//provera poklapanja
for s ← 0 to n - m do
if p = ts then
if P[1...m] = T[s+1...s+m] then
stampaj "Validan pomak s"
if s < n-m then
t(s+1) ← (d * (ts - T[s+1] * h) + T[s+m+1]) mod q
Procedura radi na sledeći način. Svi karakteri se tumače u radijusu od d cifara. Dužine su izvučene radi jasnoće, i program radi ispravno ako su sve dužine postavljene ispravno. Zatim se inicijalizuje promenljiva h koja predstavlja najvišu cifru od m cifara prozora. Zatim se radi preprocesiranje u kome se računaju vrednosti p kao P[1...m] mod q i t0 kao T[1...m] mod q. Naredna petlja iterira kroz sve pomake s, i kad god važi p = ts, računa ts = T[s+1...s+m] mod q.
Ako je p = ts (pogodak), onda moramo proveriti da li je P[1...m] = T [s+1...s+m] da bi isključili lažne pogotke. Svako validno šiftovanje koje se pronađe se zatim ispisuje. Ako je ispunjen uslov s < n-m koji se proverava u istoj petlji, to znači da će se petlja izvršiti najmanje još jednom. Pa je potrebno računati t(s+1) ← (d * (ts - T[s+1] * h) + T[s+m+1]) mod q kako bi se osigurala invarijanta petlje kada se ponovo dođe do provere p = ts. Računanje vrednosti t(s+1) mod q iz ts mod q se postiže za konstantno vreme koristeći jednakost 2.
Implementacija C++ uredi
void pretraga(char *tekst, char *niska, int radius, int mod){
/* m - duzina niske, n - duzina teksta, p - hes vrednost niske */
/* t - hes vrednost teksta, h - najveca cifra */
int m = strlen(niska);
int n = strlen(tekst);
int p = 0, t = 0, h = 1;
/* preprocesiranje */
for(int i=0; i<m-1; i++)
h=(radius*h) % mod;
for(int i=0; i<m; i++){
p=(radius*p+niska[i]) % mod;
t=(radius*t+tekst[i]) % mod;
}
/* pronalazenje niske u tekstu */
for(int i=0; i<=n-m; i++){
/* ako je t==p potrebno je proveriti da li se stvarno */
/* poklapaju karakter po karakter */
if(t==p){
for(int j=0; j<m; j++){
if(tekst[i+j]!=niska[j])
break;
if(j==m-1) cout << "Pronadjena je nisak! Pomak = " << i << endl;
}
}
/* racunamo sledeci prozor za tekst koristeci prethodnu vrednost */
if(i<n-m){
t = (radius * (t - tekst[i]*h) + tekst[i+m]) % mod;
if(t < 0)
t = (t + mod);
}
}
}
Poređenje sa naivnim algoritmom uredi
Rabin-Karp algoritam zahteva Θ(m) preprocesorskog vremena, i Θ((n-m+1)m) pronalaženja niski u najgorem slučaju, jer kao naivni algoritam Rabin-Karp algoritam eksplicitno potvrđuje svaki validni pomak. Ako je P = am i T = an, onda je provera zahteva Θ((n-m+1)m) vremena, jer svaki od n-m+1 pomaka je validan.
U mnogim aplikacijama, mi očekujemo nekoliko validnih pomaka, neki konstantan broj c. U takvim aplikacijama očekivano vreme izvršavanja nalaženja niski je samo O((n-m+1)+cm) = O(n+m), plus vreme za procesiranje lažnih pogodaka. Možemo zasnivati heurističku analizu na pretpostavci da smanjimo vrednosti po modulu q kao slučajno mapiranje iz Σ* u Ζq. Takođe za očekivati je da broj lažnih pogodaka bude O(n/q), jer verovatnoća da je proizvoljan ts jednak p mod q se može oceniti sa 1/q.
Pošto postoji O(n) pozicija na kojima provera p = ts ne uspeva, i kako trošimo O(m) vremena za svaki pogodak, očekujemo da će vreme izvršavanja pronalaska niske Rabin-Karp algoritmom biti
O(n) + O(m(v+n/q)),
gde je v broj validnih pomaka. Vreme izvršavanja je O(n), ako je v = O(1) i izaberemo q ≤ m. Odnosno, ako je broj ispravnih pomaka mali (O(1)) i q je izabrano tako da bude veće od dužine niske, onda očekujemo da Rabin-Karp ima vreme izvršavanja samo O(n+m). Ako je m ≤ n, onda je očekivano vreme izvršavanja O(n).
Dakle, Rabin-Karp algoritam u najgorem slučaju ima istu složenost kao i naivni algoritam. Međutim, u nekim slučajevima može dostići i linearno vreme, tako što koristi neke dodatne tehnike kako bi smanjio broj poređenja. Dok kod naivnog algoritma broj poređenja je u svakom slučaju značajno veći, a samim tim i složenost.
Zaključak uredi
Videli smo kako se formalizuje problem pronalaženja niske u tekstu. Prikazali smo matematičku osnovu Rabin-Karp algoritma koji pokušava da poboljša efikasnost naivnog algoritma koji ne koristi znanje koje može da izvuče iz iteracija. I on u tome uspeva, iako mu je složenost najgoreg slučaja ista kao kod naivnog algoritma on u proseku je mnogo bolji. A tu je i implementacija algoritma u programskom jeziku C++.
Ova klasa problema je široko primenljiva u raznim segmentima računarstva kao što su detekcija upada i sigurnosti mreža, pretrage bibliografija, bioinformatika. Rabin-Karp algoritam sa prosečnom linearnom složenošću je među lepšim algoritmima. Pored njega koji je zasnovan na heširanju, u primeni se mogu naći i razni algoritmi zasnovani na heuristikama, na automatima i bit-paralelizmu.
Vidi takođe uredi
Reference uredi
Literatura uredi
1. Cormen, Leiserson, Rivest, Stein, Introduction to algorithms, 2. izdanje, 2002.