Алгоритм Кнута-Морріса-Пратта
Алгоритм Кнута-Морріса-Пратта (КМП) отримує на вхід слово X = x [1] x [2] ... x [n] і переглядає його зліва направо буква за буквою, заповнюючи при цьому масив натуральних чисел l [1] ... l [n], де l [i] = довжина слова l (x [1] ... x [i]) (функція l визначена в попередньому пункті). Словами: l [i] є довжина найбільшого початку слова x [1] ... x [i], який одночасно є його кінцем.
Яке відношення все це має до пошуку подслова?
Іншими словами, як використовувати алгоритм КМП для визначення того, чи є слово A подсловом слова B?
Рішення. Застосуємо алгоритм КМП до слова A # B, де # - спеціальна буква, не зустрічається ні в A, ні в B. Слово A є подсловом слова B тоді й тільки тоді, коли серед чисел в масиві l буде число, рівне довжині слова A.
Описати алгоритм заповнення таблиці l [1] ... l [n].
Рішення. Припустимо, що перші i значень l [1] ... l [i] вже знайдені. Ми читаємо чергову букву слова (тобто x [i +1]) і повинні обчислити l [i +1].
Іншими словами, нас цікавлять початку Z слова x [1] ... x [i +1, що одночасно є його кінцями-з них нам треба брати найдовше. Звідки беруться ці початку? Кожне з них (не рахуючи порожнього) виходить з деякого слова Z 'приписуванням літери x [i +1]. Слово Z 'є початком і кінцем слова x [1] ... x [i]. Однак не будь-яке слово, що є початком і кінцем слова x [1] ... x [i], годиться - треба, щоб за ним слідувала буква x [i +1].
Отримуємо такий рецепт відшукання слова Z. Розглянемо все початку слова x [1] ... x [i], що є одночасно його кінцями. З них виберемо відповідні - ті, за якими йде буква x [i +1]. З відповідних виберемо найдовше. Приписавши в його кінець х [i +1], отримаємо шукане слово Z. Тепер пора скористатися зробленими нами приготуваннями і згадати, що всі слова, що є одночасно початками і кінцями даного слова, можна отримати повторними застосуваннями до нього функції l з попереднього розділу.
Ось що виходить:
i: = 1; 1 [1]: = 0;
{Таблиця l [1] .. l [i] заповнена правильно}
while i <> n do begin
len: = l [i]
{Len - довжина початку слова x [1] .. x [i], яка є
його кінцем; усе більш довгі початку виявилися
невідповідними}
while (x [len +1] <> х [i +1]) and (len> 0) do begin
{Початок не підходить, застосовуємо до нього функцію l}
len: = l [len];
end;
{Знайшли відповідне або переконалися у відсутності}
if x [len +1] = x [i +1] do begin
{Х [1] .. x [len] - найдовше підходяще початок}
l [i +1]: = len +1;
end else begin
{Підходящих немає}
l [i +1]: = 0;
end;
i: = i +1;
end;
Довести, що число дій в наведеному щойно алгоритмі не перевершує Cn для деякої константи C.
Рішення. Це не цілком очевидно: обробка кожної чергової букви може зажадати багатьох ітерацій у внутрішньому циклі. Проте кожна така ітерація зменшує len принаймні на 1, і в цьому випадку l [i +1] виявиться помітно менше l [i]. З іншого боку, при збільшенні i на одиницю величина l [i] може зрости не більше ніж на 1, так що часто і сильно убувати вона не може - інакше спадання не буде скомпенсировано зростанням.
Більш точно, можна записати нерівність
l [i +1] <l [i] - (число ітерацій на i-му кроці) +1
або
(Число ітерацій на i-му кроці) <= l [i]-l [i +1] +1
Залишається скласти ці нерівності по всіх i і отримати оцінку зверху для загального числа ітерацій.
Будемо використовувати цей алгоритм, щоб з'ясувати, чи є слово X довжини n подсловом слова Y довжини m. (Як це робити за допомогою спеціального роздільника #, описано вище.) При цьому число дій буде не більше C (n + m}, і використовувана пам'ять теж. Придумати, як обійтися пам'яттю не більше Cn (що може бути істотно менше, якщо шуканий зразок короткий, а слово, в якому його шукають - довге).
Рішення. Застосовуємо алгоритм КМП до слова А # В. При цьому: обчислення значень l [1 ],..., l [n] проводимо для слова X довжини n і запам'ятовуємо ці значення. Далі ми пам'ятаємо тільки значення l [i] для поточного i - окрім нього і крім таблиці
l [1] ... l [n], нам для обчислень нічого не потрібно.
На практиці слова X і Y можуть не перебувати поспіль, тому перегляд слова X і потім слова Y зручно оформити у вигляді різних циклів. Це рятує також від клопоту з роздільником.
Написати відповідний алгоритм (перевіряючий, чи є слово X = x [1] ... x [n] подсловом слова Y = y [1] ... y [m]
Рішення. Спочатку обчислюємо таблицю l [1] ... l [n] як раніше. Потім пишемо таку програму:
j: = 0; len: = 0;
{Len - довжина максимального хитала слова X, одночасно
є кінцем слова y [1] .. j [j]}
while (len <> n) and (j <> m) do begin
while (x [len +1] <> у [j +1]) and (len> 0) do begin
{Початок не підходить, застосовуємо до нього функцію l}
len: = l [len];
end;
{Знайшли відповідне або переконалися у відсутності}
if x [len +1] = y [j +1] do begin
{X [1] .. x [len] - найдовше підходяще початок}
len: = len +1;
end else begin
{Підходящих немає}
len: = 0;
end;
j: = j +1;
end;
{Якщо len = n, слово X зустрілося; інакше ми дійшли до кінця
слова Y, так і не зустрівши X}
Алгоритм Бойєра - Мура
Цей алгоритм робить те, що на перший погляд здається неможливим: у типовій ситуації він читає лише невелику частину всіх літер слова, в якому шукається заданий зразок. Як так може бути? Ідея проста. Нехай, наприклад, ми шукаємо зразок abcd. Подивимося на четверту букву слова: якщо, приміром, це буква e, то немає ніякої необхідності читати перші три букви. (Справді, у зразку букви e немає, тому він може розпочатися не раніше п'ятий літери.)
Ми наведемо найпростіший варіант цього алгоритму, який не гарантує швидкої роботи у всіх випадках. Нехай x [1] ... x [n] - зразок, який треба шукати. Для кожного символу s знайдемо саме праве його входження в слово X, тобто найбільшу k, при якому х [k] = s. Ці відомості будемо зберігати в масиві pos [s]; якщо символ s зовсім не зустрічається, то нам буде зручно покласти pos [s] = 0 (ми побачимо далі, чому).
Як заповнити масив pos?
Рішення.
покласти всі pos [s] рівними 0
for i: = 1 to n do begin
pos [x [i]]: = i;
end;
У процесі пошуку ми будемо зберігати у змінній last номер букви в слові, проти якої стоїть остання буква зразка. Спочатку last = n (довжина зразка), потім last поступово збільшується.
last: = n;
{Всі попередні положення зразка вже перевірені}
while last <= m do begin {слово не скінчилося}
if x [m] <> y [last] then begin {останні букви різні}
last: = last + (n-pos [y [last]]);
{N - pos [y [last]] - це мінімальний зсув зразка,
при якому навпроти y [last] постане така ж
буква в зразку. Якщо такої літери немає взагалі,
то зрушуємо на всю довжину зразка}
end else begin
якщо нинішній стан підходить, тобто якщо
x [i] .. x [n] = y [last-n +1] .. y [last],
щось повідомити про збіг;
last: = last +1;
end;
end;
Знавці рекомендують перевірку збігу проводити справа наліво, тобто починаючи з останньої букви зразка (в якій збіг завідомо є). Можна також трохи заощадити, зробивши віднімання заздалегідь і зберігати не pos [s], а n-pos [s],
тобто кількість літер у зразку праворуч від останнього входження букви Можливі різні модифікації цього алгоритму. Наприклад, можна рядок
last: = last + i
замінити на
last: = last + (nu),
де u - координата другий праворуч входження букви x [n] у зразок.
Як простіше за все врахувати це у програмі
Рішення. При побудові таблиці pos написати
for i: = 1 to n-1 do ...
(Далі як раніше), а в основній програмі замість
last: = last +1
написати
last: = last + n-pos [y [last]];
Наведений спрощений варіант алгоритму Бойєра-Мура в деяких випадках вимагає істотно більше n дій (число дій порядку mn), програючи алгоритмом Кнута-Морріса-Пратта.
Приклад ситуації, в якій зразок не входить у слово, але алгоритму потрібно близько mn дій, щоб це встановити.
Рішення. Нехай зразок має вигляд baaa ... aa, а саме слово складається тільки з букв а. Тоді на кожному кроці невідповідність з'ясовується лише в останній момент.
Справжній (не спрощена) алгоритм Бойєра-Мура гарантує, що кількість дій не перевершує C (m + n) в гіршому випадку. Він використовує ідеї, близькі до ідей алгоритму Кнута-Морріса-Пратта. Уявімо собі, що ми порівнювали зразок зі вхідним словом, йдучи справа наліво. При цьому деякий шматок Z (який є кінцем зразка) співпав, а потім виявилося відмінність: перед Z у зразку варто не те, що у вхідному слові. Що можна сказати в цей момент про вхідному слові? У ньому виявлено фрагмент, рівний Z, а перед ним стоїть не та буква, що в зразку. Ця інформація може дозволити зрушити зразок на декілька позицій праворуч без ризику пропустити його входження. Ці зрушення слід обчислювати заздалегідь для кожного кінця Z нашого зразка. Як кажуть знавці, все це (обчислення таблиці зрушень і її використання) можна укласти в C (m + n) дій.
Алгоритм Рабіна
Цей алгоритм заснований на простій ідеї. Уявімо собі, що в слові довжини m ми шукаємо зразок довжини n. Виріжемо віконечко розміру n і будемо рухати його з вхідного слова. Нас цікавить, не збігається слово у віконечку з заданим зразком. Порівнювати по буквах довго. Замість цього фіксуємо деяку функцію, визначену на словах довжини n. Якщо значення цієї функції на слові у віконечку та на зразку різні, то збігу немає. Тільки якщо значення однакові, потрібно перевіряти збіг по буквах.
У чому виграш при такому підході. Здавалося б, нічого - адже щоб обчислити значення функції на слові у віконечку, все одно потрібно прочитати всі букви цього слова. Так вже краще їх одразу порівняти зі зразком. Тим не менш виграш можливий, і ось за рахунок чого. При зсуві віконечка слово не міняється повністю, а лише додається літера в кінці і забирається на початку. Добре б, щоб за цими даними можна було розрахувати, як змінюється функція.
Привести приклад зручною для обчислення функції.
Рішення. Замінимо всі букви в слові і зразку їх номерами, що представляють собою цілі числа. Тоді зручною функцією є сума цифр. (При зсуві віконечка потрібно додати нове число і відняти зникле.)
Для кожної функції існують слова, до яких застосовується ця погано. Зате інша функція в цьому випадку може працювати добре. Виникає ідея: треба купити заздалегідь багато функцій і на початку роботи алгоритму вибирати з них випадкову. (Тоді ворог, який хоче напаскудити нашому алгоритмом, не буде знати, з якою саме функцією йому боротися.)
Привести приклад сімейства зручних функцій.
Рішення. Виберемо деякий число p (бажано просте, дивись далі) і деякий вирахування x за модулем p. Кожне слово довжини n будемо розглядати як послідовність цілих чисел (замінивши літери кодами). Ці числа будемо розглядати як коефіцієнти многочлена ступеня n-1 і обчислимо значення цього многочлена з модулю p в точці x. Це і буде одна з функцій сімейства (для кожної пари p і x виходить, таким чином, своя функція). Зрушення віконця на 1 відповідає вирахуванню старшого члена (хn-1 слід обчислювати заздалегідь), множенню на x і додаванню вільного члена.
Наступне міркування говорить на користь того, що збігу не дуже вірогідні. Нехай число p фіксоване і до того ж просте, а X і Y - два різних слова довжини n. Тоді їм відповідають різні многочлени (ми припускаємо, що коди всіх букв різні - це можливо, якщо p більше числа літер алфавіту). Збіг значень функції означає, що в точці x ці два різних многочлена збігаються, тобто їх різниця звертається до 0. Різниця є многочлен ступеня n-1 і має не більше n-1 коренів. Таким чином, якщо і багато менше p, то випадковим x мало шансів потрапити в невдалу крапку.
Алгоритм Кнута-Морріса-Пратта (КМП) отримує на вхід слово X = x [1] x [2] ... x [n] і переглядає його зліва направо буква за буквою, заповнюючи при цьому масив натуральних чисел l [1] ... l [n], де l [i] = довжина слова l (x [1] ... x [i]) (функція l визначена в попередньому пункті). Словами: l [i] є довжина найбільшого початку слова x [1] ... x [i], який одночасно є його кінцем.
Яке відношення все це має до пошуку подслова?
Іншими словами, як використовувати алгоритм КМП для визначення того, чи є слово A подсловом слова B?
Рішення. Застосуємо алгоритм КМП до слова A # B, де # - спеціальна буква, не зустрічається ні в A, ні в B. Слово A є подсловом слова B тоді й тільки тоді, коли серед чисел в масиві l буде число, рівне довжині слова A.
Описати алгоритм заповнення таблиці l [1] ... l [n].
Рішення. Припустимо, що перші i значень l [1] ... l [i] вже знайдені. Ми читаємо чергову букву слова (тобто x [i +1]) і повинні обчислити l [i +1].
Іншими словами, нас цікавлять початку Z слова x [1] ... x [i +1, що одночасно є його кінцями-з них нам треба брати найдовше. Звідки беруться ці початку? Кожне з них (не рахуючи порожнього) виходить з деякого слова Z 'приписуванням літери x [i +1]. Слово Z 'є початком і кінцем слова x [1] ... x [i]. Однак не будь-яке слово, що є початком і кінцем слова x [1] ... x [i], годиться - треба, щоб за ним слідувала буква x [i +1].
Отримуємо такий рецепт відшукання слова Z. Розглянемо все початку слова x [1] ... x [i], що є одночасно його кінцями. З них виберемо відповідні - ті, за якими йде буква x [i +1]. З відповідних виберемо найдовше. Приписавши в його кінець х [i +1], отримаємо шукане слово Z. Тепер пора скористатися зробленими нами приготуваннями і згадати, що всі слова, що є одночасно початками і кінцями даного слова, можна отримати повторними застосуваннями до нього функції l з попереднього розділу.
Ось що виходить:
i: = 1; 1 [1]: = 0;
{Таблиця l [1] .. l [i] заповнена правильно}
while i <> n do begin
len: = l [i]
{Len - довжина початку слова x [1] .. x [i], яка є
його кінцем; усе більш довгі початку виявилися
невідповідними}
while (x [len +1] <> х [i +1]) and (len> 0) do begin
{Початок не підходить, застосовуємо до нього функцію l}
len: = l [len];
end;
{Знайшли відповідне або переконалися у відсутності}
if x [len +1] = x [i +1] do begin
{Х [1] .. x [len] - найдовше підходяще початок}
l [i +1]: = len +1;
end else begin
{Підходящих немає}
l [i +1]: = 0;
end;
i: = i +1;
end;
Довести, що число дій в наведеному щойно алгоритмі не перевершує Cn для деякої константи C.
Рішення. Це не цілком очевидно: обробка кожної чергової букви може зажадати багатьох ітерацій у внутрішньому циклі. Проте кожна така ітерація зменшує len принаймні на 1, і в цьому випадку l [i +1] виявиться помітно менше l [i]. З іншого боку, при збільшенні i на одиницю величина l [i] може зрости не більше ніж на 1, так що часто і сильно убувати вона не може - інакше спадання не буде скомпенсировано зростанням.
Більш точно, можна записати нерівність
l [i +1] <l [i] - (число ітерацій на i-му кроці) +1
або
(Число ітерацій на i-му кроці) <= l [i]-l [i +1] +1
Залишається скласти ці нерівності по всіх i і отримати оцінку зверху для загального числа ітерацій.
Будемо використовувати цей алгоритм, щоб з'ясувати, чи є слово X довжини n подсловом слова Y довжини m. (Як це робити за допомогою спеціального роздільника #, описано вище.) При цьому число дій буде не більше C (n + m}, і використовувана пам'ять теж. Придумати, як обійтися пам'яттю не більше Cn (що може бути істотно менше, якщо шуканий зразок короткий, а слово, в якому його шукають - довге).
Рішення. Застосовуємо алгоритм КМП до слова А # В. При цьому: обчислення значень l [1 ],..., l [n] проводимо для слова X довжини n і запам'ятовуємо ці значення. Далі ми пам'ятаємо тільки значення l [i] для поточного i - окрім нього і крім таблиці
l [1] ... l [n], нам для обчислень нічого не потрібно.
На практиці слова X і Y можуть не перебувати поспіль, тому перегляд слова X і потім слова Y зручно оформити у вигляді різних циклів. Це рятує також від клопоту з роздільником.
Написати відповідний алгоритм (перевіряючий, чи є слово X = x [1] ... x [n] подсловом слова Y = y [1] ... y [m]
Рішення. Спочатку обчислюємо таблицю l [1] ... l [n] як раніше. Потім пишемо таку програму:
j: = 0; len: = 0;
{Len - довжина максимального хитала слова X, одночасно
є кінцем слова y [1] .. j [j]}
while (len <> n) and (j <> m) do begin
while (x [len +1] <> у [j +1]) and (len> 0) do begin
{Початок не підходить, застосовуємо до нього функцію l}
len: = l [len];
end;
{Знайшли відповідне або переконалися у відсутності}
if x [len +1] = y [j +1] do begin
{X [1] .. x [len] - найдовше підходяще початок}
len: = len +1;
end else begin
{Підходящих немає}
len: = 0;
end;
j: = j +1;
end;
{Якщо len = n, слово X зустрілося; інакше ми дійшли до кінця
слова Y, так і не зустрівши X}
Алгоритм Бойєра - Мура
Цей алгоритм робить те, що на перший погляд здається неможливим: у типовій ситуації він читає лише невелику частину всіх літер слова, в якому шукається заданий зразок. Як так може бути? Ідея проста. Нехай, наприклад, ми шукаємо зразок abcd. Подивимося на четверту букву слова: якщо, приміром, це буква e, то немає ніякої необхідності читати перші три букви. (Справді, у зразку букви e немає, тому він може розпочатися не раніше п'ятий літери.)
Ми наведемо найпростіший варіант цього алгоритму, який не гарантує швидкої роботи у всіх випадках. Нехай x [1] ... x [n] - зразок, який треба шукати. Для кожного символу s знайдемо саме праве його входження в слово X, тобто найбільшу k, при якому х [k] = s. Ці відомості будемо зберігати в масиві pos [s]; якщо символ s зовсім не зустрічається, то нам буде зручно покласти pos [s] = 0 (ми побачимо далі, чому).
Як заповнити масив pos?
Рішення.
покласти всі pos [s] рівними 0
for i: = 1 to n do begin
pos [x [i]]: = i;
end;
У процесі пошуку ми будемо зберігати у змінній last номер букви в слові, проти якої стоїть остання буква зразка. Спочатку last = n (довжина зразка), потім last поступово збільшується.
last: = n;
{Всі попередні положення зразка вже перевірені}
while last <= m do begin {слово не скінчилося}
if x [m] <> y [last] then begin {останні букви різні}
last: = last + (n-pos [y [last]]);
{N - pos [y [last]] - це мінімальний зсув зразка,
при якому навпроти y [last] постане така ж
буква в зразку. Якщо такої літери немає взагалі,
то зрушуємо на всю довжину зразка}
end else begin
якщо нинішній стан підходить, тобто якщо
x [i] .. x [n] = y [last-n +1] .. y [last],
щось повідомити про збіг;
last: = last +1;
end;
end;
Знавці рекомендують перевірку збігу проводити справа наліво, тобто починаючи з останньої букви зразка (в якій збіг завідомо є). Можна також трохи заощадити, зробивши віднімання заздалегідь і зберігати не pos [s], а n-pos [s],
тобто кількість літер у зразку праворуч від останнього входження букви Можливі різні модифікації цього алгоритму. Наприклад, можна рядок
last: = last + i
замінити на
last: = last + (nu),
де u - координата другий праворуч входження букви x [n] у зразок.
Як простіше за все врахувати це у програмі
Рішення. При побудові таблиці pos написати
for i: = 1 to n-1 do ...
(Далі як раніше), а в основній програмі замість
last: = last +1
написати
last: = last + n-pos [y [last]];
Наведений спрощений варіант алгоритму Бойєра-Мура в деяких випадках вимагає істотно більше n дій (число дій порядку mn), програючи алгоритмом Кнута-Морріса-Пратта.
Приклад ситуації, в якій зразок не входить у слово, але алгоритму потрібно близько mn дій, щоб це встановити.
Рішення. Нехай зразок має вигляд baaa ... aa, а саме слово складається тільки з букв а. Тоді на кожному кроці невідповідність з'ясовується лише в останній момент.
Справжній (не спрощена) алгоритм Бойєра-Мура гарантує, що кількість дій не перевершує C (m + n) в гіршому випадку. Він використовує ідеї, близькі до ідей алгоритму Кнута-Морріса-Пратта. Уявімо собі, що ми порівнювали зразок зі вхідним словом, йдучи справа наліво. При цьому деякий шматок Z (який є кінцем зразка) співпав, а потім виявилося відмінність: перед Z у зразку варто не те, що у вхідному слові. Що можна сказати в цей момент про вхідному слові? У ньому виявлено фрагмент, рівний Z, а перед ним стоїть не та буква, що в зразку. Ця інформація може дозволити зрушити зразок на декілька позицій праворуч без ризику пропустити його входження. Ці зрушення слід обчислювати заздалегідь для кожного кінця Z нашого зразка. Як кажуть знавці, все це (обчислення таблиці зрушень і її використання) можна укласти в C (m + n) дій.
Алгоритм Рабіна
Цей алгоритм заснований на простій ідеї. Уявімо собі, що в слові довжини m ми шукаємо зразок довжини n. Виріжемо віконечко розміру n і будемо рухати його з вхідного слова. Нас цікавить, не збігається слово у віконечку з заданим зразком. Порівнювати по буквах довго. Замість цього фіксуємо деяку функцію, визначену на словах довжини n. Якщо значення цієї функції на слові у віконечку та на зразку різні, то збігу немає. Тільки якщо значення однакові, потрібно перевіряти збіг по буквах.
У чому виграш при такому підході. Здавалося б, нічого - адже щоб обчислити значення функції на слові у віконечку, все одно потрібно прочитати всі букви цього слова. Так вже краще їх одразу порівняти зі зразком. Тим не менш виграш можливий, і ось за рахунок чого. При зсуві віконечка слово не міняється повністю, а лише додається літера в кінці і забирається на початку. Добре б, щоб за цими даними можна було розрахувати, як змінюється функція.
Привести приклад зручною для обчислення функції.
Рішення. Замінимо всі букви в слові і зразку їх номерами, що представляють собою цілі числа. Тоді зручною функцією є сума цифр. (При зсуві віконечка потрібно додати нове число і відняти зникле.)
Для кожної функції існують слова, до яких застосовується ця погано. Зате інша функція в цьому випадку може працювати добре. Виникає ідея: треба купити заздалегідь багато функцій і на початку роботи алгоритму вибирати з них випадкову. (Тоді ворог, який хоче напаскудити нашому алгоритмом, не буде знати, з якою саме функцією йому боротися.)
Привести приклад сімейства зручних функцій.
Рішення. Виберемо деякий число p (бажано просте, дивись далі) і деякий вирахування x за модулем p. Кожне слово довжини n будемо розглядати як послідовність цілих чисел (замінивши літери кодами). Ці числа будемо розглядати як коефіцієнти многочлена ступеня n-1 і обчислимо значення цього многочлена з модулю p в точці x. Це і буде одна з функцій сімейства (для кожної пари p і x виходить, таким чином, своя функція). Зрушення віконця на 1 відповідає вирахуванню старшого члена (хn-1 слід обчислювати заздалегідь), множенню на x і додаванню вільного члена.
Наступне міркування говорить на користь того, що збігу не дуже вірогідні. Нехай число p фіксоване і до того ж просте, а X і Y - два різних слова довжини n. Тоді їм відповідають різні многочлени (ми припускаємо, що коди всіх букв різні - це можливо, якщо p більше числа літер алфавіту). Збіг значень функції означає, що в точці x ці два різних многочлена збігаються, тобто їх різниця звертається до 0. Різниця є многочлен ступеня n-1 і має не більше n-1 коренів. Таким чином, якщо і багато менше p, то випадковим x мало шансів потрапити в невдалу крапку.