Проналажење свих појављивања ниски у тексту је проблем који се јако често јавља у програмима за уређивање текста. Наравно, текст у документима се мења па тражење ниски заправо зависи од тога шта корисник уноси. Ефикасни алгоритми за овај проблем могу у великој мери да помогну одзиву таквих програма. Овакви алгоритми се поред наведене примене могу користити код претраживања ДНК секвенци, и разним другим областима.

Увод

Овај проблем можемо формализовати на следећи начин. Претпоставимо да је текст низ 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+P))). Вредност 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