Алгоритъм на Кнут-Морис-Прат

Проблемът, който решаваме е често срещан - търсене на един низ в друг. Така можем да мислим, че имаме един малък низ, който наричаме шаблон, и стандартно означаваме дължината му с $m$. Този шаблон търсим дали се среща (или всички срещания) в голям низ, който наричаме текст, а дължината му означаваме с $n$.

Има лесен наивен алгоритъм за тази задача, като просто за всяка възможна позиция в текста проверяваме дали там се среща шаблонът. Понеже тази проверка е линейна по шаблона, то общо сложността на алгоритъма е $O(nm)$. Често срещана грешна оптимизация на наивния алгоритъм е да търсим шаблона не от всяка една възможна позиция в текста, а когато не го намерим, да пробваме от буквата, до която сме стигнали и сме се провалили. Разбира се, лесно се стига до пропуски с този начин. Нека например шаблонът е $ababac$, а текстът е $abababac$. Лесно се вижда, че шаблонът се среща на позиция 3 в текста. Но с грешната оптимизация първо ще пробваме за срещане на позиция 1, ще установим, че не се среща чак когато сравним 6-тата буква на текста с тази на шаблона и установим разлика, след което ще пробваме да намерим шаблона на позиция 6 и така ще пропуснаме неговото срещане на позиция 3.

Всъщност КМР алгоритъмът представлява точно оптимизиация на наивния, но направена правилно и постигаща линейна сложност - $O(n+m)$. Идеята е да се възползваме от получената информация - това, че вече сме сравнили част от буквите, когато не успеем да намерим шаблона на дадена позиция. Проблемът на грешната оптимизация е, че шаблонът е възможно да се среща и по-рано от първата разлика. Затова можем да изпозваме знанието, че първите пет букви от шаблона и текста съвпадат (разликата е при 6-тата) и така следващата смислена позиция, на която да търсим шаблона е 3, защото 3-тата, 4-тата и 5-тата буква на текста съвпадат с първите три буква на шаблона. Хитрото е, че няма да сравняваме отново тези букви, а директно като търсим шаблона от позиция 3 в текста, ще сравняваме 6-тата буква в текста с 4-тата на шаблона и като продължим ще намерим срещането. Сложната част разбира се е как скачаме на следваща позиция и с този въпрос ще се занимаваме в следващата точка.

Хубаво е да споменем и алгоритъма на Рабин-Карп, който се занимава със същия проблем. Той е със същата сложност като КМР, но е с по-голяма константа, заради хеширането, а има и друг недостатък. Поради използването на хеширането не е гарантирано, че винаги ще е коректен (или ако го реализираме коректен, няма да е гарантирано, че ще има линейна сложност). Така че КМР алгоритъмът има значително предимство пред Рабин-Карп, а също така се пише и доста кратко, макар да е доста по-сложен за разбиране.

Както горе беше подсказано, като знаем, че някаква част от шаблона вече се среща в текста и получим разлика, трябва да знаем къде да търсим след това в текста. Тук можем да се възползваме, че еднаквата част е някакъв префикс на шаблона, т.е. нужната информация винаги е за някой префикс на шаблона. Това, което искаме да знаем, е къде трябва да се предвижим като следваща позиция за търсене. Разбира се, от тази позиция нататък трябва отново да имаме съвпадение със шаблона. Ако разгледаме отново предния пример със шаблон $\underline{ababa}c$ (съвпадащата част с текста е подчертана), то следващата удачна позиция е третата - $ab\underline{aba}c$. Така, ако почнем от там (на съответното място в текста), знаем, че първите три символа на шаблона ги има. Сега вече можем по-формално да кажем какво търсим: за даден префикс на шаблона търсим най-дългия му суфикс, който се явява префикс на шаблона. Нека означим шаблона със $s$.

Определение: Един суфикс на префикса $s[0...i]$, ще наричаме добър за позиция $i$, ако той е същински суфикс и се явява префикс на $s$. Тогава функция на неуспеха (още се нарича префиксна) за низа $s$, ще наричаме $f$, където $f(i)=|$най-дългият добър суфикс за позиция $i|$.

Важно е, че гледаме същински суфикси, защото иначе $f(i)=i+1$ за всяко $i$. Освен това гледаме и суфикси с нулева дължина, за да имаме винаги поне един добър суфикс. Лесно се вижда, че ако сметнем тази функция вече ще можем при неуспех на търсенето на шаблона да скачаме директно на следващата възможна позиция и да направим грешната оптимизация вярна. Ще се концентрираме върху намирането на функцията $f$. Можем да подходим с динамично програмиране. За целта нека разпишем функцията на неуспеха за по-интересния шаблон $s=aabaabaaac$.

$i$ $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$
$s$ $a$ $a$ $b$ $a$ $a$ $b$ $a$ $a$ $a$ $c$
$f$ $0$ $1$ $0$ $1$ $2$ $3$ $4$ $5$ $2$ $0$

Забелязваме, че стойностите нарастват най-много с 1. Това лесно се вижда. Ако допуснем, че за някоя позиция $i+1$: $f(i+1)=f(i)+k$, където $k>1$, то ако махнем последния символ на максималния добър суфикс за позиция $i+1$, ще получим суфикс на $s[0...i]$, който се явява и префикс на $s$ с дължина $f(i+1)-1=$ $f(i)+k-1>f(i)$ при $k>1$. Така получаваме по-дълъг добър суфикс за позиция $i$ и стигаме до противоречие с намерената стойност за $f(i)$. Освен това много лесно можем да разберем дали сме в този случай. Нека сме намерили стойностите $f(0), f(1), ..., f(i)$ и трябва да намерим $f(i+1)$. Нека означим $f(i)=l$. Имаме 2 случая. Първият, по-лесен случай, е ако $s[l]=s[i+1]$. Тогава можем да удължим намерения най-дълъг добър суфикс за позиция $i$ с текущия символ на низа (...) и да получим добър суфикс за позиция $i+1$ (равенството на символите позволява след удължаването на суфикса с текущия символ, той да остане префикс на $s$). За по-добро разбиране можем да разгледаме $f(5)$. Имаме, че $f(4)=2$ или: $\colorbox{lightblue}{$aa$}b\colorbox{lightblue}{$aa$}b...$ Понеже $s[l]=s[2]=b$ и $s[5]=b$, то като удължим добрия суфикс $aa$ за позиция 4 с $b=s[5]$, получаваме добър суфикс за позиция 5 - $\colorbox{lightblue}{$aab$}\textcolor{blue}{aab}...$ Съответно, това е най-дългият добър суфикс за позиция 5 (...), защото от наблюдението по-рано, ако има по-дълъг, то щяхме да получим по-дълъг и за $f(4)$. Така за лесния случай получаваме, че просто $f(i+1)=f(i)+1$ - случая, когато дължината нараства с 1.

Сега ще разгледаме трудния случай, когато $s[l] \neq s[i+1]$ и не можем просто да удължим стария най-дълъг добър суфикс, за да получим новия. Тук дължината почти винаги намалява (...). Нека погледнем как най-дългият добър суфикс за позиция $i+1$ се отнася към този за позиция $i$. Схематично, ако означим със син цвят най-дългия добър суфикс за позиция $i$, то имаме следната ситуация: $\colorbox{lightblue}{$s_0 \space s_1 \space ... \space s_{l-1}$}s_l$ $...\space s_{i-l} \colorbox{lightblue}{$s_{i-l+1} \space ... \space s_i$}s_{i+1} \space ...$, където съответният префикс, който трябва да съвпада с добрия суфикс, също е оцветен в синьо. (...) Нека $f(i+1)=t$, където $t \lt l$ и означим схематично с лилав цвят, най-дългия добър суфикс за позиция $i+1$. Тогава имаме следната ситуация: $\colorbox{lightblue}{$\textcolor{magenta}{s_0 \space s_1 \space ... \space s_{t-1}} \space s_t \space ... \space s_{l-1}$}s_l$ $... \space s_{i-l} \colorbox{lightblue}{$s_{i-l+1} \space ... \space s_{i-t+1} \space \textcolor{magenta}{s_{i-t+2} \space ... \space s_i}$}\textcolor{magenta}{s_{i+1}} \space ...$ Но от това, че двете сини части съвпадат, се получава, че има още лилави области, които са еднакви. Ако премахнем последния символ на най-дългия добър суфикс за позиция $i+1$ и само това остане лилаво, то ако пренесем лилавия суфикс на втората синя част като суфикс на първата синя част, получаваме следното: $\colorbox{lightblue}{$\textcolor{magenta}{s_0 \space s_1 \space ... \space s_{t-2}} \space s_{t-1} \space ... \space s_{l-t} \space \textcolor{magenta}{s_{l-t+1} \space ... \space s_{l-1}}$}s_l$ $... \space s_{i-l} \colorbox{lightblue}{$s_{i-l+1} \space ... \space s_{i-t} \space \textcolor{magenta}{s_{i-t+1} \space ... \space s_i}$}s_{i+1} \space ...$ (...). Важното наблюдение, което можем да направим е, че лилавият низ се явява добър суфикс за позиция $l-1$ и също е вярно, че $s[t-1]=s[i+1]$.

Това, което не знаем, е дали лилавият низ е най-дългият добър суфикс за $l-1$. Ако това е така, то $t-1=f(l-1) \Rightarrow f(i+1)=t=f(l-1)+1$. Лесно можем да разберем дали лилавият низ е най-дългият добър суфикс или не, като просто разгледаме два случая. Ако $s[f(l-1)]=s[i+1]$, то от горната схема се вижда, че наистина можем да продължим префикса, съответстващ на най-дългия добър суфикс за позиция $l-1$, със символа $s[f(l-1)]$ и така ще получим добър суфикс за текущата позиция - $i+1$! А той трябва да е най-дългият иначе ще получим противоречие с някои от предните аргументи. Но пак имаме и втори случай, когато $s[f(l-1)] \neq s[i+1]$. Обаче сега можем с аналогични разсъждения да видим, че търсеният най-дълъг добър суфикс без последната буква ще e добър суфикс освен на позиция $l-1=f(i)-1$ и на позиция $f(l-1)-1$. Всъщност, за да намерим най-дългият добър суфикс трябва да се връщаме по префиксите, съотвестващи на най-дългите добри суфикси, докато не срещнем равенство на съответния символ с текущия $s[i+1]$ (или ако въобще не срещнем равенство, спираме, когато достигнем до префикс с нулева дължина).

Ще илюстрираме вече алгоритъма за конкретен случай - при намирането на $f(8)=2$. Първо, понеже $s[8] \neq s[f(7)]=s[5]$, то трябва да пробваме евентуално за най-дългият добър суфикс на позиция $4$. Имаме следната схема: $\colorbox{lightblue}{$\underline{aa}b\textcolor{blue}{\underline{aa}}$}$$\textcolor{blue}{b\underline{aa}}a...$ (тук вместо да оцветим в лилаво сме подчертали най-дългия добър суфикс за $s[5]$ и гаратираните му срещания на други места). Тук като проверим, че $s[f(4)]=s[2] \neq s[8]$ ще се върнем до префикса на позиция $f(4)-1=1$. Сега имаме следната илюстрация: $\colorbox{lightblue}{$\textcolor{magenta}{a} \space \textcolor{magenta}{a}$}$$baab\colorbox{lightblue}{$a\textcolor{magenta}{a}$}a...$ Вече ще видим, че $s[f(1)]=s[1]=s[8]$, което означава, че можем да удължим префикса $a$, който е най-дългият добър суфикс на позиция $1$, с буквата $s[f(1)]=a$ и получаваме най-дългия добър суфикс за позиция $8$.

За по-добро разбиране е предоставен интерактивен пример, където за даден шаблон $s$ се намира функцията на неуспеха. Освен това може да се проиграе намирането на дадена стойност на $f$ по начина, по който по-горе разсъждавахме.

Последно показваме реализация на функция, която намира стойностите на функцията на неуспеха по описания алгоритъм. Както се вижда, кодът е доста кратък и елегантен.

В предната точка се запознахме с най-важното - как при неуспех на търсенето да знаем на коя следваща позиция трябва да продължим търсенето на шаблона. Нека разгледаме стария пример - шаблон $s=ababac$ и текст $abababac$. В началото започваме да търсим шаблона от първата позиция и виждаме следното съвпадане: $\colorbox{lightblue}{$ababa$}c$, $\colorbox{lightblue}{$ababa$}bac$. Както казахме по-рано, следващата удачна позиция за търсене е позиция $3$ в текста (съответно позиция $3$ и в шаблона). Реално това е позиция $3$, защото търсим позиция в шаблона, така че суфиксът, започващ от нея, да съвпада с префикс (т.е. да е добър) и за да е първата удачна позиция (най-малката възможна) трябва суфиксът да е най-голям или това се явява точно позицията, от която започва най-дългият добър суфикс на позиция $5$ с дължина $f(4)=3$: $\colorbox{lightblue}{$ab\textcolor{blue}{a}$}\textcolor{blue}{ba}c$ (за функцията на неуспeха, индексацията започва от 0, затова вместо $f(5)$ гледаме $f(4)$). Съответно позицията, от която започва този най-дълъг добър суфикс е равна на: $5-f(4)+1=5-3+1=$ точно $3$. Така функцията на неуспеха ни показва от коя следваща позиция на текста (...) трябва да пробваме да търсим шаблона. Дори повече - вече знаем, че част от символите съвпадат и не е нужно пак да ги сравняваме. За примера знаем, че като почнем търсенето от следващата позиция $3$ в текста, то първите $f(4)=3$ символа съвпадат. Това е така, защото на предната стъпка вече сме ги сравнили с добрия суфикс на шаблона, а той от своя страна ще съвпада с префикса, който започва, когато търсим шаблона от новата позиция $3$. Така директно знаем, че символите в текста на позиции $3,4$ и $5$ съвпадат с първите $3$ на шаблона и това означава, че ще започнем следващото сравнение на $1+f(4)=4$-тия символ на шаблона и $3+f(4)=6$-тия символ на текста или $\colorbox{lightblue}{$aba$}\underline{b}ac$, $ab\colorbox{lightblue}{$aba$}\underline{b}ac$. Сега последователно ще видим, че съвпадат символи $6$, $7$ и $8$ със съответните от шаблона и така ще открием срещане на шаблона на позиция $3$ в текста. Понеже няма още символи в текста, то приключваме.

Така описахме директния оптимизиран алгоритъм за търсене на шаблон в текст, когато сме изчислили функцията на неуспеха. За по-добро разбиране предоставяме анимация, която представя горния алгоритъм и приключва при намирането на първо срещане на шаблона или ако няма срещания, при изчерпване на текста. Тук сме означили с $t$ текста.

Сега прилагаме код, който реализира директно предния алгоритъм. Допълнително той намира всички срещания на шаблона, за да се види една малка особеност в този случай. Както ще се убедите, има доста неприятни моменти с нагласянето на индекси и дължини. Тук считаме, че вече сме намерили функцията на неуспеха и тя е записана в масива \(f\).

На практика тази версия не се използва. Ще приложим програма, която реализира KMP алгоритъма, по малко по-лесен за писане начин и доста по-полезен за други алгоритми. Главната идея е да помним индекса, докъдето сме стигнали в текста, както и големината на префикса, който сме намерили досега. Тук един важен момент за анализа на коректността е, че пазим дължината на префикса с максимална дължина, който завършва на текущата позиция в текста. Очевидно, ако правим това вярно, няма как да изпуснем срещане. Следва реализация на тази идея.

Накрая ще представим най-лесния начин човек да пише линеен алгоритъм на базата на функцията на неуспеха за търсене на шаблон в текст. Той е приложим почти винаги. Нека помислим как може да решаваме задачата само с алгоритъма за намиране на функцията на неуспеха. Ами ако някак при този алгоритъм разгледаме и текста бихме имали шанс. Това всъщност става много лесно. Нека низът, за който изчисляваме функцията на неуспеха е $s\$t$, където $\$$ е символ, който не се среща в низовете. (...). Сега ако разгледаме функцията на неуспеха, лесно се вижда, че ако на някое място \(f(i)=m\), то там завършва срещане на шаблона, защото заради $\$$ няма как да имаме по-голям добър суфикс на тази позиция. Обратно, ако имаме срещане завършващо на дадена позиция $i$, то трябва \(f(i)=m\), защото сложихме $s$ като префикс на низа. Последно, прилагаме код и за този начин, който е най-елегантен от всички досегашни:

Накрая, ще разгледаме как се доказва, че KMP алгоритъма е с линейна сложност. За улеснение (а и предвид последната идея) ще обосновем само частта с намирането на функцията на неуспеха. Може да се докаже, че всека итерация има амортизирана сложност \(O(1)\). Нека помислим общо колко стъпки отнема вътрешния цикъл при намирането на $f$. Проблемът е, че на една итерация относно външния цикъл (този по $i$) може да има доста стъпки. Нека разгледаме при намирането на $f(i)$, през какви стойности минава променливата $l$, която се явява съвпадащата дължина до сега. Докато не срещнем равенство на новите символи във вътрешния цикъл, то $l$ минава през следните стойности: $f(i-1), f(f(i-1)-1), f(f(f(i-1)-1)-1), ...$ Важното тук е, че тези стойности строго намаляват и свършват, когато стигнем $0$. Така схематично можем да мислим, че една нова итерация на вътрешния цикъл (намаляваща текущата съвпадаща дължина), съответства на едно увеличаване с $1$, което сме направили по-рано при намирането на някоя по-стара стойност на функцията. (...)

От тук следва, че сумарният брой стъпки на вътрешния цикъл не може да е по-голям от броя пъти, в които сме увеличавали стойността на $f(i)$ спрямо $f(i-1)$. Но както вече бяхме обосновали, а и от програмата следва, че на една итерация относно $i$, увеличаването е най-много с единица. Така получаваме, че броя стъпки по намаляване $\le$ броя стъпки по увеличаване $\le m$. По този начин излиза, че сумарната работа е най-много $2m$ стъпки. Като обобщим този анализ за целия алгоритъм, аналогично се получава, че той работи най-много $2n+2m$ стъпки. От там сложността е $O(n+m)$.