Кнут-Морис-Прат
Knuth-Morris-Pratt
В информатиката често се налага да търсим дали даден стринг се среща в текст (или по-генерално - някаква последователност от символи, числа, или обекти в дадено наредено множество). В тази тема ще разгледаме алгоритъма на Кнут, Морис, и Прат, който много ефективно помага да се справим с тази задача.
Както в състезателната информатика, така и в реалния живот, често се налага да търсим даден стринг или фраза в текст. В следствие на широкото разпространение на този проблем, съществуват редица алгоритми, които се справят с него. Един от тях - rolling hash - вече разгледахме в темата за хеширане. Друга алтернатива е алгоритъмът на Бойер-Муур.
Най-популярният, а и най-простият, от трите най-известни алгоритъма, решаващи този проблем оптимално, е измислен от Доналд Кнут, Вауган Прат, и Джеймс Морис. Алгоритъмът, съответно, е кръстен на тях и можете да срещнете като Knuth-Morris-Pratt, или накратко KMP.
Проблем
Даден ви е текст T с дължина |T| = N. Искате да намерите дали дума W с дължина |W| = M се среща в него (и ако да - къде).Наивно решение
Наивното решение би било за всяко възможно начало на W (всеки символ в текста T) да пробваме дали W се среща започвайки в този символ. Това става просто със следната функция:int strSearchNaive(const string& text, const string& word) {
for (int start = 0; start + (int)word.size() <= (int)text.size(); start++) {
bool match = true;
for (int i = 0; i < (int)word.size(); i++) {
if (word[i] != text[start + i]) {
match = false;
break;
if (match) {
return start;
return -1;
}O(N∙M) в най-лошия случай, която може да се постигне с относително прост пример - текст, съставен само от буквата 'A' и дума W = "АААА....B". Така за всеки от N-те символа на T ще match-нем M-1 символа от W преди да намерим разлика.Идея
Това, което прави наивният алгоритъм бавен, е че всеки път, когато не успеем да match-нем думата, започвайки от дадена позиция P, то започваме от начало от символ P + 1. Както се оказва, обаче, самата дума W и индекса, на който сме срещнали mismatch-а (idx), са достатъчни да определим дали изобщо трябва да разглеждаме започване от P + 1, а не, например, от някаква по-дясна позиция P + X (X ≤ idx + 1). Нещо повече, можем да определим колко символа от W бихме match-нали със сигурност, ако започнем от въпросната позиция.За да стане по-ясно, нека разгледаме текста "ОБРАТЯБРАТЯТАНАСУЛТАНА" ("Обра тя братята на султана") и търсим в него "БРАТЯБРАТУШКИ" ("Братя братушки"). Няма да намерим търсената дума, но поне ще покажем, че ще го направим ефективно!
Първа оптимизация
По стандартния алгоритъм, започвайки от първия символ няма да match-нем нито една буква ('О' ≠ 'Б'), но започвайки от втория ще match-нем цели 9, преди да открием разлика (търсим 'У', но в текста срещаме 'Я'):ОБРАТЯБРАТЯТАНАСУЛТАНА
БРАТЯБРАТУШКИ
В този момент наивният алгоритъм би пробвал за начало третия символ от текста (първото 'Р'). Ние, обаче, сме match-нали 9 букви - от тях имаме информация колко надясно се среща следващото 'Б': тъй като сме match-нали "БРАТЯБРАТ", то знаем, че следващото 'Б' в текста ще е 5 букви надясно от предходното начало, тоест можем да започнем директно от там:
ОБРАТЯБРАТЯТАНАСУЛТАНА
БРАТЯБРАТУШКИ
Втора оптимизация
Можем да доразвием горната идея, като не само скочим на правилната позиция, ами счетем за match-нати и правилния брой символи след него. Както забелязвате, след 'Б'-то имаме 'Р', което също match-ва (а след него и 'А' и 'Т'). За да не ги обхождаме отново, ще си направим табличка с преходи, наричани fail link-ове отговаряща на въпроса "Ако съм мачнал първите idx символа от търсената дума преди да срещна разлика, то колко символа надясно в текста трябва да отида и колко символа ще съм мачнал със сигурност, ако започна от там?"В случая, тази табличка трябва да ни каже, че ако сме мачнали "БРАТЯБРАТ", то можем да скочим 5 символа надясно и всички символи до 4-тия от думата със сигурност ще мачнат. Тоест, ползвайки тази таблица с fail link-ове, можем директно от:
ОБРАТЯБРАТЯТАНАСУЛТАНА
БРАТЯБРАТУШКИ
да скочим на:
ОБРАТЯБРАТЯТАНАСУЛТАНА
БРАТЯБРАТУШКИ
Забележете, че тези фейл линкове ни казват колко символа със сигурност ще мачнат (на базата на досега мачнатите символи от търсената дума). Възможно е и повече да мачват (например горе имаме отново match: 'Я'-то в думата мачва 'Я'-то в текста), но в случая няма как да знаем за това предварително, тъй като преди да последваме фейл линка сме били матчнали само "БРАТЯБРАТ" - тоест нямаме информация за буквата след това.Алгоритъм на Кнут-Морис-Прат
Най-основното от алгоритъма на Кнут-Морис-Прат ни дава точно това - стъпките, с които да построим въпросната таблицата с fail link-ове. Допълнително ще покажем и самото обхождане на стринга и ползването на тази таблица за да намерим дума в текст.Строене на таблицата с фейл линкове
За всяка позиция от търсената дума можем да пазим едно единствено число - дължината на най-дългият префикс, който е и суфикс, завършващ в този индекс. Разбира се, суфиксът трябва да не започва в началото на думата, тъй като вече сме открили, че не ни върши работа.Нека, например, разгледаме думата "ЛИЛИЕВЛИЛАВО". Ако сме мачнали "ЛИЛИ" и сме стигнали до буква, различна от 'Е' (мисмач), то най-дългият префикс, който е и суфикс е "ЛИ". В този случай трябва таблицата с фейл линковете да има числото 2. Ако сме мачнали "ЛИЛИЕВЛИЛ" преди да стигнем до мисмач, най-дългият префикс, който е и суфикс, е "ЛИЛ" - тоест в таблицата трябва да имаме числото 3.
Цялата таблица за думата "ЛИЛИЕВЛИЛАВО" би изглеждала по следния начин:
INDEX: 0 1 2 3 4 5 6 7 8 9 10 11
LETTERS: Л И Л И Е В Л И Л А В О
LENGTHS: 0 0 1 2 0 0 1 2 3 0 0 0
Очевидно таблицата трябва да е с M клетки, където M е дължината на търсената дума.Нулевата клетка винаги е нула (има само един символ, тоест няма как да има непразен суфикс, започващ след нея).
За всеки индекс след първия, в началото сетваме фейл линка да е дължината на префикса от предходната позиция. Неговата дължина + 1 (префиксът, допълнен с текущия символ) е теоретично най-дългият префикс, който може да е и суфикс, завършващ в текущата позиция. Разбира се, той може да не е подходящ, тъй като текущият символ не го продължава. В процеса на работа на алгоритъма ще го скъсяваме, докато символът на текущата позиция не мачне продължението на префикса.
След като сме фиксирали началния префикс, алгоритъмът протича по следния начин.
| ? | За изчисляването на следващите клетки ще ползваме вече пресметнати стойности на предходните стъпки - тоест правим нещо като динамично оптимиране. |
Ще пробваме следващия най-дълъг, който все пак е по-къс от текущия. Него можем да намерим ползвайки вече изчислените стойности - той е с дължина
failLinks[failLinks[i] - 1], където failLinks[i] е дължината на префикса, който току-що сме пробвали. Продължаваме така докато или префиксът стане празен, или текущият символ го допълва.Накрая трябва да проверим дали текущият символ допълва намерения префикс - ако да, увеличаваме дължината на най-дългия префикс с 1. Алгоритъмът гарантира, че ако не го допълва, то
failLinks[i] ще бъде нула.Като код, това изглежда по следния начин:
void buildFailLinks(const string& word) {
// Първият символ е винаги нула
failLinks[0] = 0;
// За всеки символ след първия
for (int i = 1; i < (int)word.size(); i++) {
// В началото сетваме текущият префикс да е префикса от предходната позиция
failLinks[i] = failLinks[i - 1];
// Пробваме по-къси и по-къси префикси, докато или дължината им стане нула,
// или текущият символ съвпадне с продължението им.
while (failLinks[i] > 0 && word[failLinks[i]] != word[i])
failLinks[i] = failLinks[failLinks[i] - 1];
// Ако накрая текущият символ допълва правилно намерения префикс
// (било то и празен стринг), увеличаваме неговата дължина с 1.
if (word[failLinks[i]] == word[i])
failLinks[i]++;
}Не е много очевидно, че сложността на тази функция е
O(M). За всеки символ от думата:- Скачаме няколко пъти назад по фейл линковете;
- Добавяме един символ.
O(1). Сега трябва да покажем, и че амортизирано 1) e O(M) за целия стринг.Това може лесно да направим, като съобразим, че е невъзможно да сме скочили повече от M пъти. Тъй като скачаме само назад, то за да скочим назад (намалим дължината на кандидатния префикс), трябва преди това да сме го увеличили. Тъй като, обаче, за всеки символ от думата го увеличаваме са най-много 1, то дори всеки път да скачаме само с по един символ назад, ще сме скочили най-много M пъти.
Търсене на думата в текста
След като сме изчислили таблицата с фейл линковете, самото търсене на думата в текста става относително лесно.В началото започваме от първия символ на текста, като не сме мачнали нито една буква. Докато думата все още може да влиза в текста, започвайки от текущия символ, пробваме да мачваме символ по символ (сходно на наивния алгоритъм). Ако стигнем края на думата, значи сме намерили нейно срещане (започващо в start). Можем или да върнем този индекс, или да го изпечатаме, без да прекъсваме цикъла (ако искаме да изпечатаме всички срещания). Независимо дали сме стигнали края на думата или сме намерили разлика между следващия ѝ символ и този в текста, казваме, че мачваме един символ по-малко (разбира се, ако не сме мачнали нито един, си оставаме с нула мачнати символа). Придвижваме се до най-близката позиция надясно, която би могла да е валиден префикс на думата, ползвайки таблицата с фейл линковете и ъпдейтваме дължината на този префикс.
Това като код изглежда по следния начин:
int strSearchKMP(const string& text, const string& word) {
// Започваме с първия символ на текста и нула мачнати букви от думата
int start = 0, match = 0;
// Докато думата все още може да се събере в текста, започвайки от start
while (start + (int)word.size() <= (int)text.size()) {
// Пробваме да мачваме символ по символ, сходно с наивния алгоритъм
while (match < (int)word.size() && word[match] == text[start + match])
match++;
// Ако стигнем края на думата, значи сме намерили нейно срещане в текста
// (започващо от start)
if (match == (int)word.size())
return start;
// Ако сме намерили разлика между следващия символ в думата и в текста,
// казваме, че мачваме един символ по-малко
// (разбира се, ако не сме мачнали нито един, оставаме в нула)
match = max(0, match - 1);
// Придвижваме се до най-близката позиция надясно, която би могла да бъде
// валиден префикс на думата, ползвайки таблицата с фейл линковете
start += match - failLinks[match] + 1;
// Ъпдейтваме дължината на текущо-мачнатия префикс
match = failLinks[match];
return -1;
}O(N).Сложност
Видяхме, че се нуждаем отO(M) за да построим фейл линковете и O(N) за да намерим къде в текста се среща думата. Така целият алгоритъм е O(N + M).Откъм памет алгоритъмът е
O(M) (трябва да пазим търсената дума и масива с фейл линкове). Забележете, че не е нужно да пазим самия текст (алгоритъмът е streaming, тоест може да разглеждаме текста символ по символ).Пример
Нека разгледаме процеса на работа на алгоритъма в пример.Ще имаме текста "ЛИЛИЯ ЛИЛИЕВЛИЛИЕВЛИЛАВООБЛЕКЛО" и ще търсим "ЛИЛИЕВЛИЛАВО".
Първо трябва да си построим таблицата с фейл линковете. Както вече показахме, тя ще изглежда по следния начин:
INDEX: 0 1 2 3 4 5 6 7 8 9 10 11
LETTERS: Л И Л И Е В Л И Л А В О
LENGTHS: 0 0 1 2 0 0 1 2 3 0 0 0
Започваме да обхождаме текста, като мачваме първите четири букви, докато срещнем разлика (търсим 'Е', но срещаме 'Я'):
ЛИЛИЯ ЛИЛИЕВЛИЛИЕВЛИЛАВООБЛЕКЛО
ЛИЛИЕВЛИЛАВО
Мачнали сме "ЛИЛИ", като най-дългият префикс на думата, който се среща стриктно след първия символ, и завършва в края на мачнатия стринг, е "ЛИ" (колкото букви показва и фейл линкът на съответната позиция). Тъй като сме мачнали 4 букви, а таблицата с фейл линковете дава числото 2 за 4-тата буква (реално индекс 3 от масива с фейл линковете, тъй като индексираме от 0), се местим 4 - 2 = 2 букви надясно и знаем, че сме мачнали 2 букви.
ЛИЛИЯ ЛИЛИЕВЛИЛИЕВЛИЛАВООБЛЕКЛО
ЛИЛИЕВЛИЛАВО
Отново намираме разлика, но този път фейл линкът на втората буква показва, че най-дългият префикс, който може да пробваме, е с дължина нула. Затова се местим още 2 - 0 = 2 букви надясно и сетваме match = 0 (колкото показва фейл линка).
ЛИЛИЯ ЛИЛИЕВЛИЛИЕВЛИЛАВООБЛЕКЛО
ЛИЛИЕВЛИЛАВО
Намираме директно разлика ('Л' срещу 'Я'), затова продължаваме нататък.
ЛИЛИЯ ЛИЛИЕВЛИЛИЕВЛИЛАВООБЛЕКЛО
ЛИЛИЕВЛИЛАВО
Този път се опитваме да мачнем (неуспешно) 'Л' с шпация, затова отново продължаваме със следващия символ.
ЛИЛИЯ ЛИЛИЕВЛИЛИЕВЛИЛАВООБЛЕКЛО
ЛИЛИЕВЛИЛАВО
Този път успяваме да мачнем цели 9 букви, преди да срещнем разлика ('А' срещу 'И'). Фейл линкът на съответната позиция показва 3, тоест най-дългият префикс, който можем да ползваме, е с дължина 3. Местим се 9 - 3 = 6 символа надясно и почваме сравнението директно от 4-тата буква на търсената дума (match = 3).
ЛИЛИЯ ЛИЛИЕВЛИЛИЕВЛИЛАВООБЛЕКЛО
ЛИЛИЕВЛИЛАВО
Mачвайки останалите букви от търсената дума, този път успешно я намираме:
ЛИЛИЯ ЛИЛИЕВЛИЛИЕВЛИЛАВООБЛЕКЛО
ЛИЛИЕВЛИЛАВО
Забележете, че с горната процедура обходихме общо 6 начални позиции в текста (вместо 13, както би направил наивният алгоритъм), като направихме общо 22 сравнения на символи (вместо 41, както би направил наивният алгоритъм).
Това все пак е относително нормален пример. KMP блесва в по-нестандартни стрингове и текстове. Дори с относително къси такива можем да видим брутално подобрение! Например за текст "AAAAAAAAAAAAAAAAAAAA" (20 'A'-та) и търсена дума "AAAAAAAAAB" (9 'A'-та, следвани от едно 'B'), и алгоритъмът на Кнут-Морис-Прат и наивният разглеждат 11 начални позиции, но докато наивният прави 110 сравнения на символи, KMP се нуждае от едва 19.
Трик само с фейл линкове
Един интересен трик е, че можем да минем само с кода за строене на фейл линкове, за сметка на малко повече памет. Нека имаме символ, който не се среща в азбуката нито на текста, нито на думата (да кажем '#'). В един стринг ще изпишем думата, после този символ, после текста. В примера от по-горе така бихме получили:ЛИЛИЕВЛИЛАВО#ЛИЛИЯ ЛИЛИЕВЛИЛИЕВЛИЛАВООБЛЕКЛО
Нека построим fail link-овете на този стринг:
INDEX: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
LETTERS: Л И Л И Е В Л И Л А В О # Л И
LENGTHS: 0 0 1 2 0 0 1 2 3 0 0 0 0 1 2
INDEX: 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
LETTERS: Л И Я Л И Л И Е В Л И Л И Е
LENGTHS: 3 4 0 0 1 2 3 4 5 0 1 2 3 4 5
INDEX: 30 31 32 33 34 35 36 37 38 39 40 41 42 43
LETTERS: В Л И Л А В О О Б Л Е К Л О
LENGTHS: 6 7 8 9 10 11 12 0 0 1 0 0 1 0
Тъй като символът-разделител не се среща нито в думата, нито в текста, то той със сигурност "реже" префикса най-много на дължина, равна на дължината на думата, която търсим. Нещо повече, ако сме стигнали до него, то сме намерили срещане на думата в текста! Така, за да преброим колко пъти се среща дадена дума в текста, можем просто да създадем таблицата с fail link-овете и да видим колко от тях са равни на дължината на думата (в случая 12).Малко по-прост пример би бил да търсим думата "IT" в текста "WITHOUT IT I'M JUST ESPRIT". Стринга, който създаваме, е "IT#WITHOUT IT I'M JUST ESPRIT", който има следните фейл линкове:
INDEX: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
LETTERS: I T # W I T H O U T I T
LENGTHS: 0 0 0 0 1 2 0 0 0 0 0 1 2 0
INDEX: 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
LETTERS: I ' M J U S T E S P R I T
LENGTHS: 1 0 0 0 0 0 0 0 0 0 0 0 0 1 2
На три места стигаме до фейл линкове с дължина 2 - което е и точно колко пъти "IT" се среща в "WITHOUT IT I'M JUST ESPRIT". Реално, ползвайки таблицата можем и да определим позициите, в които думата се среща в текста.Ползвайки този трик лесно можем да покажем и сложността на алгоритъма. Новосъздаденият стринг е с дължина N + 1 + M. Както казахме, строенето на фейл линковете става със сложност
O(L), където L е дължината на думата. Тоест, сложността да построим фейл линковете (и, съответно, да намерим броя и позициите на срещането на думата в текста) е O(N + M).Много стрингове
Разширение на тази задача е ако искаме да намерим къде се срещат няколко (K на брой) стринга в текст (примерно търсите K гена в ДНК верига). Един вариант е да използваме K пъти алгоритъма на Кнут-Морис-Прат, но това би довело до решение със сложностO(K∙(N + M)). Вместо това, съществува по-сложно решение, което внедрява идеята на Кнут-Морис-Прат за fail link-ове в префиксно дърво (Trie), като така успява да постигне сложност O(N + K∙M) - тоест е съизмеримо с броя символи, които получаваме като вход. Това е алгоритъмът на Ахо-Корасик, който ще разгледаме по-нататък.Задачи
Директна имплементация на алгоритъма в най-чистия му вид можете да пробвате в задачата A Needle in the Haystack (противно на какво казва условието, можете да си прочетете целите стрингове наведнъж, ако ползвате достатъчно големи буфери (примерно около 100 мегабайта)).Можем да решим задачата Charming, като за всяка от дадените думи ползваме KMP за да намерим срещанията ѝ в текста. След като имаме тези "подинтервали", можем да ползваме алчния алгоритъм за най-много непресичащи се интервали за да намерим оптималния отговор. Това решение би работило и за дължина на стринговете до 100,000.
В задачата Gattaca пък можем да ползваме KMP за да хванем малко повече от половината точки. За целта ще направим двоично търсене по отговора, и за всяка фиксирана дължина ще правим KMP търсене на всеки подстринг от S1 с тази дължина в S2.
Допълнителни материали
- String Search (en.wikipedia.org)
- Knuth-Morris-Pratt Algorithm (en.wikipedia.org)
- Boyer-Moore String Search Algorithm (en.wikipedia.org)
- Алгоритъм на Ахо-Корасик (informatika.bg)
За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.
натиснете Enter и изпратете Вашето предложение.
Страницата е посетена 5677 пъти.