Поређење Рабин-Карп и наивног алгоритма
Проналажење свих појављивања ниски у тексту је проблем који се јако често јавља у програмима за уређивање текста. Наравно, текст у документима се мења па тражење ниски заправо зависи од тога шта корисник уноси. Ефикасни алгоритми за овај проблем могу у великој мери да помогну одзиву таквих програма. Овакви алгоритми се поред наведене примене могу користити код претраживања ДНК секвенци, и разним другим областима.
Увод уреди
Овај проблем можемо формализовати на следећи начин. Претпоставимо да је текст низ T[1...n] дужине n и нека је ниска коју тражимо низ P[1...m] дужине m ≤ n. Следећа претпоставка јесте да су елементи низова T и P карактери извучени из коначног алфабета (језика) Σ, на пример Σ = {0,1} или Σ = {a,b,c,...,z}. Често се карактери низова T и P називају низови карактера.
Кажемо да се ниска P појављује са помаком s у тексту T (или појављивање ниске P почиње од позиције s+1 у тексту T), ако 0 ≤ s ≤ n-m и T[s+1...s+m] = P[1...m] (односно ако T[s+j] = P[j] за свако 1 ≤ j ≤ m). Ако се ниска P појављује са помаком s онда то зовемо валидно шифтовање, у супротном је s невалидно шифтовање. Проблем проналажења ниски јесте проблем проналажења свих валдних шифтовања задате ниске P у задатом тексту T.
Неки познатији алгоритми који се баве овим проблемима су наивни алгоритам, Рабин-Карп, коначни аутомат, Кнут-Морис-Прат, Бојер-Мур-Хорспул, итд. Овде ћемо пажњу посветити основној идеји и поређењу Рабин-Карп и наивног алгоритма.
Терминологија уреди
Нека са Σ* (читамо сигма-звезда) означимо скуп свих коначних ниски који се могу извести коришћењем карактера из Σ. Сматраћемо да су стрингови само оне ниске које имају коначну дужину. Празну ниску означићемо са ε, која такође припада Σ*. Дужину ниске x означићемо са |x|. Конкатенацију (надовезивање) две ниске x и y означићемо са xy, а њихову дужину са |x| + |y|, што подразумева да прво иду карактери ниске x, а за њима следе карактери ниске y.
Кажемо да је ниска w префикс ниске x, ако је x = wy за неки стринг y из Σ*. Приметимо да је |w| ≤ |x|. Слично, кажемо да је ниска w суфикс ниске x, ако је x = yw за неки стринг y из Σ*. Такође важи ако је w суфикс ниске x, онда је w ≤ x. Јасно је да је празна ниска ε и префикс и суфикс сваке ниске. На пример, важи да је ab префикс ниске abcca и cca суфикс ниске abcca. Корисно је запазити да за неке ниске x и y и неки карактер a, важи x је суфикс ниске y ако и само ако важи да је xа суфикс ниске yа. Поред осталог приметимо да су префикс и суфикс транзитивне релације. Сад наводимо лему која нам ће нам бити потребна касније.
Лема 1 (преклапајућа суфикс лема): Претпоставимо да су x, y и z ниске тако да важи x је суфикс од z и y је префикс од z. Ако је |x| ≤ |y|, онда је x суфикс од y. Ако је |x| ≥ |y|, онда је x префикс од y. Ако је |x| = |y|, онда x = y.
Наивни алгоритам уреди
У овом поглављу навешћемо само идеју наивног алгоритма, да би разимели како он ради јер нам је то потребно при поређењу са Рабин-Карп алгоритмом.
Наивни алгоритам проналази сва валидна шифтовања користећи петљу која проверава услов P[1...m] = T[s+1...s+m] за свако од n-m+1 могућих вредности s. Псеудо-код:
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"
Наивни алгоритам се може интерпретирати графички као клизни шаблон (прозор) који садржи ниску која се тражи у тексту, померајући шаблон низ текст и поредећи све карактере шаблона са свим карактерима текста, као што је приказано на примеру испод:
Корак 1:
Текст: [a c a] a b c
= ≠
Ниска: [a a b]
Невалидно шифтовање.
Корак 2:
Текст: a [c a a] b c
≠
Ниска: [a a b]
Невалидно шифтовање.
Корак 3:
Текст: a c [a a b] c
= = =
Ниска: [a a b]
Валидно шифтовање.
Корак 4:
Текст: a c a [a b c]
= ≠
Ниска: [a a b]
Невалидно шифтовање.
У најгорем случају овај алгоритам има сложеност O((n-m+1)m). На пример, размотримо текст an (текст дужине n са свим карактерима a) и ниску am. За свако од n-m+1 могућих вредности помака s, петља for мора да упореди одговарајуће карактере m пута да би шифтовање било валидно. Како је у најгорем случају сложеност O((n-m+1)m), ако је m цео део од n/2 добијамо укупну сложеност O(n2). Овај алгоритам је неефикасан јер информацију коју је стекао о тексту за једну вредност s, је игнорисао за другу вредност за s. Такве информације могу да буду јако корисне. На пример, ако је за ниску P[0...2] пронађено да је валидно шифтовање s=0, онда сигурно шифтовања 1, 2 и 3 нису валидна па их не морамо испитивати.
Рабин-Карп алгоритам уреди
Рабин и Карп су предложили алгоритам проналажења ниски у тексту који се показао добар у пракси, и који генерализује друге алгоритме сродних проблема као што су дводимензионално проналажење ниски. Рабин-Карп алгоритам користи Θ(m) времена за препроцесирање, а у најгорем случају захтева Θ((n-m+1)m). Међутим, његово просечно време извршавања је боље.
Идеја уреди
Овај алгоритам користи основне појмове теорије бројева као што су еквивалентност два броја по модулу трећег броја.
Да би појаснили, претпоставимо да је Σ = {0, 1, ...,9} тако да је сваки карактер децимална цифра. У општем случају можемо претпоставити да је сваки карактер у интервалу d где је d = |Σ|. Онда можемо посматрати ниску k као узастопне карактере који представљају k-дужину децималног броја. На пример, ниска 31415 одговара децималном броју 31,415. Имајући у виду двоструко тумачење улазних карактера као графичких симбола и цифара, погодно је да у овом одељку их посматрамо као цифре у стандардном текстуалном фонту.
За дату ниску P[1...m] нека p означава одговарајућу децималну вредност. На сличан начин, за дати текст T[1...n] нека ts означава децималну вредност подтекста T[s+1...s+m] дужине m, за s = 0,1,...,n-m. Свакако, ts = p ако и само ако T[s+1...s+m] = P[1...m], односно s је валидно шифтовање ако је ts = p. Ако можемо да израчунамо вредност p у времену Θ(m) и све вредности ts у времену Θ(n-m+1), онда би могли да одредимо сва валидна шифтовања s у укупном времену Θ(m) + Θ(n-m+1) = Θ(n) поредећи p са сваким ts. На тренутак занемаримо да p и ts могу да буду јако велико бројеви.
Ми можемо да рачунамо p у времену Θ(m) користећи Хорнерову шему:
p = P[m]+10 * (P[m-1]+10 * (P[m-2]+...+10 * (P[2]+P[1]))).
Вредност t0 се може слично израчунати из T[1...m] у времену Θ(m).
За рачунање осталих вредности t1,t2,...,t(n-m) потребно је Θ(n-m) времена, то је последица тога да се t(s+1) рачуна из ts за константно време, на следећи начин:
t(s+1) = 10 * (ts - 10(m-1) * T[s+1]) + T[s+m+1].
На пример, нека је m=5 и ts = 31415, ако желимо да уклонимо највишу цифру T[s+1] = 3 и додамо нову најнижу цифру на пример 2 тако да је T[s+5+1] = 2, онда рачунамо следеће:
t(s+1) = 10 * (31415 - 10000 * 3) + 2 = 14152. (једначина 1)
Уклањањем 10(m-1)T[s+1] највише цифре из ts и множењем са 10, шифтовали смо број за једну позицију улево, и додали смо на T[s+m+1] одговарајућу најнижу цифру. Ако је константа 10(m-1) израчуната раније, што може да се уради за време O(log(m)) користећи технике модуларне аритметике иако је за ову примену и O(m) прихватљиво, онда свако извршавање једнакости из леме 1 се изводи за константан број корака. Дакле, можемо израчунати p у времену Θ(n) и t0,t1,...,t(n-m) у времену Θ(n-m+1), и можемо пронаћи сва појављивања ниске P[1...m] у тексту T[1...n] са Θ(m) препроцесорског времена и Θ(n-m+1) поређења.
Једини проблем са оваквом процедуром јесте тај да p и ts могу бити толико велики да није угодно радити са њима. Ако P садржи m карактера, онда претпоставка да свака аритметичка операција над p који има m цифара се извршава за константно време је нетачна. Срећом постоји једноставно решење за овај проблем, које је приказано на примеру испод. Рачунање p и ts се изводи по модулу q. Када израчунамо p и t0, понављања из једначине 1 могу се обављати по модулу q, а видећемо да рачунање p mod q можемо израчунати у Θ(m) времену и ts mod q у времену Θ(n-m+1). Модул q се генерално бира тако да 10 * q може да стане у једну компјутерску реч, која омогућава да све неопходне промене обављамо са једноструком прецизношћу (енг. single-precision arithmetic). Ако уопштимо ово, кажемо да у d-арном језику {0,1,...,d-1} ми бирамо q тако да d * q одговара компјутерској речи, тако да се понављање једначине 1 ради по модулу q и постаје:
t(s+1) = d * (ts - T[s+1] * h) + T[s+m+1] mod q (једначина 2),
где је h логички еквивалентно са d(m-1) mod q, односно вредност прве (највише) цифре од m цифара текстуалног прозора. Пример где је текст представљен ниском цифара Т = 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 5 3, ниска која се тражи је представљена ниском цифара P = 3 1 4 1 5, скуп d чине цифре {0,1,2,3,4,5,6,7,8,9}, а за q је узет број 13:
Корак 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)
Невалидно шифтовање.
Корак 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)
Невалидно шифтовање.
Корак 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)
Невалидно шифтовање.
Корак 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)
Невалидно шифтовање.
Корак 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)
Невалидно шифтовање.
Корак 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)
Невалидно шифтовање.
Корак 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)
Погодак, проверавмо карактер по карактер и добијамо да је валидно шифтовање.
Корак 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)
Невалидно шифтовање.
Корак 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)
Невалидно шифтовање.
Корак 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)
Невалидно шифтовање.
Корак 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)
Невалидно шифтовање.
Корак 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)
Невалидно шифтовање.
Корак 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)
Погодак, проверавамо карактер по карактер и добијамо да је лажан погодак (невалидно шифтовање).
Корак 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)
Невалидно шифтовање.
Корак 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)
Невалидно шифтовање.
Решење са модулом није идеално, јер из чињенице да је t_s логички еквивалентно са p mod q не следи да важи t_s = p. Са друге стране, ако t_s није логички еквивалентно са p mod q онда сигурно важи t_s ≠ p, и помак s је невалидан. На овај начин можемо да користимо тест t_s логички еквивалентно са p mod q као брз тест за хеуристичко одбацивање невалидних помака s. Било који помак s за који важи да је t_s логички еквивалентно са p mod q мора бити тестиран даље да се провери да ли је то заиста валидан помак или само лажан погодак (енг. spurious hit). Ово тестирање може да се уради експлицитном провером услова P[1...m] = T[s+1...s+m]. Ако је q довољно велико, онда се надамо да ће се лажни погодак дешавати толико ретко да додатна цена се не повећава много.
Следи процедура испод прати приказане идеје. Улаз у процедуру јесу текст T, ниска P, радијус d и 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
Процедура ради на следећи начин. Сви карактери се тумаче у радијусу од d цифара. Дужине су извучене ради јасноће, и програм ради исправно ако су све дужине постављене исправно. Затим се иницијализује променљива h која представља највишу цифру од m цифара прозора. Затим се ради препроцесирање у коме се рачунају вредности p као P[1...m] mod q и t0 као T[1...m] mod q. Наредна петља итерира кроз све помаке s, и кад год важи p = ts, рачуна ts = T[s+1...s+m] mod q.
Ако је p = ts (погодак), онда морамо проверити да ли је P[1...m] = T [s+1...s+m] да би искључили лажне поготке. Свако валидно шифтовање које се пронађе се затим исписује. Ако је испуњен услов s < n-m који се проверава у истој петљи, то значи да ће се петља извршити најмање још једном. Па је потребно рачунати t(s+1) ← (d * (ts - T[s+1] * h) + T[s+m+1]) mod q како би се осигурала инваријанта петље када се поново дође до провере p = ts. Рачунање вредности t(s+1) mod q из ts mod q се постиже за константно време користећи једнакост 2.
Имплементација C++ уреди
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);
}
}
}
Поређење са наивним алгоритмом уреди
Рабин-Карп алгоритам захтева Θ(m) препроцесорског времена, и Θ((n-m+1)m) проналажења ниски у најгорем случају, јер као наивни алгоритам Рабин-Карп алгоритам експлицитно потврђује сваки валидни помак. Ако је P = am и T = an, онда је провера захтева Θ((n-m+1)m) времена, јер сваки од n-m+1 помака је валидан.
У многим апликацијама, ми очекујемо неколико валидних помака, неки константан број c. У таквим апликацијама очекивано време извршавања налажења ниски је само O((n-m+1)+cm) = O(n+m), плус време за процесирање лажних погодака. Можемо заснивати хеуристичку анализу на претпоставци да смањимо вредности по модулу q као случајно мапирање из Σ* у Ζq. Такође за очекивати је да број лажних погодака буде O(n/q), јер вероватноћа да је произвољан ts једнак p mod q се може оценити са 1/q.
Пошто постоји O(n) позиција на којима провера p = ts не успева, и како трошимо O(m) времена за сваки погодак, очекујемо да ће време извршавања проналаска ниске Рабин-Карп алгоритмом бити
O(n) + O(m(v+n/q)),
где је v број валидних помака. Време извршавања је O(n), ако је v = O(1) и изаберемо q ≤ m. Односно, ако је број исправних помака мали (O(1)) и q је изабрано тако да буде веће од дужине ниске, онда очекујемо да Рабин-Карп има време извршавања само O(n+m). Ако је m ≤ n, онда је очекивано време извршавања O(n).
Дакле, Рабин-Карп алгоритам у најгорем случају има исту сложеност као и наивни алгоритам. Међутим, у неким случајевима може достићи и линеарно време, тако што користи неке додатне технике како би смањио број поређења. Док код наивног алгоритма број поређења је у сваком случају значајно већи, а самим тим и сложеност.
Закључак уреди
Видели смо како се формализује проблем проналажења ниске у тексту. Приказали смо математичку основу Рабин-Карп алгоритма који покушава да побољша ефикасност наивног алгоритма који не користи знање које може да извуче из итерација. И он у томе успева, иако му је сложеност најгорег случаја иста као код наивног алгоритма он у просеку је много бољи. А ту је и имплементација алгоритма у програмском језику C++.
Ова класа проблема је широко применљива у разним сегментима рачунарства као што су детекција упада и сигурности мрежа, претраге библиографија, биоинформатика. Рабин-Карп алгоритам са просечном линеарном сложеношћу је међу лепшим алгоритмима. Поред њега који је заснован на хеширању, у примени се могу наћи и разни алгоритми засновани на хеуристикама, на аутоматима и бит-паралелизму.
Види такође уреди
Референце уреди
Литература уреди
1. Cormen, Leiserson, Rivest, Stein, Introduction to algorithms, 2. издање, 2002.