Алгоритм Кнута — Морріса — Пратта

Алгоритм Кнута — Морріса — Пратта (скорочено алгоритм КМП) — один із алгоритмів пошуку рядка, що шукає входження слова W у рядку S, використовуючи просте спостереження, що коли відбувається невідповідність, то слово містить у собі достатньо інформації для того, щоб визначити, де наступне входження може початися, таким чином пропускаючи кількаразову перевірку попередньо порівняних символів.

Алгоритм, що винайшли Дональд Кнут та Вон Пратт, а також незалежно від них Джеймс Морріс, опубліковано у спільній статті у 1977 році.

Часова асимптотична складність алгоритму становить O(N+M), де N — довжина слова W, M — довжина рядка S.

Теорія

Алгоритм повинен знайти початковий індекс m рядка W[] в рядку S[].

Найпростіший алгоритм пробігає по всьому рядку S[m], де m — індекс. Якщо індекс m досягне кінця рядка, то W[] не знайдено і алгоритм поверне результат «fail». На кожній позиції перевіряється рівність елемента на позиції m з S[] й елемента на першій позиції з W[], тобто S[m] =? W[0]. Якщо вони рівні, то алгоритм перевіряє наступні відповідні елементи в рядках за індексом i. Алгоритм перевіряє всі вирази S[m+i] =? W[i]. Якщо всі елементи з W знайдені, то алгоритм поверне позицію m.

Зазвичай, пробна перевірка швидко відкидає можливість збігу. Якщо рядки складаються з рівномірно розподілених елементів, то шанс, що перші елементи дорівнюють один одному, буде 1 до 26. Отже, в більшості випадків пробна перевірка відкидатиме початкові елементи. Шанс, що перші два елементи будуть рівними, дорівнює 1 до 26² (тобто, 1 до 676). Тобто, якщо елементи рівномірно розподілені, очікувана складність пошуку в рядку S[] довжини k буде порядку k порівнянь або O(k). Якщо S[] має 1.000.000.000 елементів і W[] має 1000 елементів, то пошук рядка займе приблизно 1.000.000.000 порівнянь.

Проте очікувана продуктивність не гарантована. Якщо рядки не випадкові, то на кожному кроці m може знадобитися багато порівнянь. У найгіршому випадку два рядки збігаються майже за всіма літерами. Якщо рядок S[] має 1.000.000.000 елементів, що рівні A і рядок W[] складається з 999 елементів A і останній елемент B. Тоді найпростіший алгоритм на кожному кроці виконуватиме 1000 перевірок, а всіх перевірок буде 1 трильйон. Отже, якщо довжина W[] — n, то в найгіршому випадку складність становитиме O(k⋅n).

Алгоритм КМП має кращий показник швидкодії в найгіршому випадку. КМП витрачає небагато часу (за порядком розміру W[], O(n)) на попереднє обчислення таблиці, і потім використовує таблицю для швидкого пошуку рядка за час O(k).

З іншого боку, на відміну від попередньо розглянутого простого алгоритму, алгоритм КМП використовує відомості про попередні порівняння. У прикладі, що наведений вище, коли КМП зустрічає незбіг на 1000-ному елементі (i = 999), тобто S[m+999] ≠ W[999], КМП знатиме, що 999 позицій вже перевірено. КМП містить ці знання у попередньо обчисленій таблиці і додаткових змінних. Коли КМП знаходить незбіг, з таблиці визначається, наскільки збільшиться змінна m.

Алгоритм КМП

Приклад алгоритму пошуку

Для пояснення подробиць алгоритму опрацюємо (порівняно штучний) перебіг алгоритму. У будь-який момент, алгоритм перебуває в стані визначеному двома цілими:

• m — позиція в S, початок сподіваного збігу для W,
• i — індекс поточного символу у W.

На кожному кроці алгоритм порівнює S[m+i] з W[i] і збільшує i якщо вони однакові. Це можна побачити на початку наступного пошуку

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

Ми рухаємось порівнюючи наступні символи W із відповідними символами з S, просуваючись від поточного до наступного в випадку збігу. Однак, на четвертому кроці, ми отримуємо S[3] як пробіл, а W[3] = 'D', розбіжність. Радше ніж починати знов з S[1], ми зауважимо, що 'A' не зустрічається між позиціями 0 і 3 в S окрім як в 0; відповідно, перевіривши всі ці символи до цього, ми занотували, що неможливо знайти початок збігу, якщо ми пробіжимо їх знов. Отже ми пересуваємось на наступний символ, встановлюючи m = 4 і i = 0. (m напочатку приймає значення 3 бо m + i - T[i] = 0 + 3 - 0 = 3 і тоді стає 4 бо T[0] = -1, де T — це таблиця «часткових збігів»)

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456

Ми швидко отримуємо майже повний збіг "ABCDAB", аж як у W[6] (S[10]), знов маємо невідповідність. Однак, лиш саме перед завершенням поточного часткового збігу, ми проминули "AB", що може бути початком нового збігу, отже маємо взяти це до уваги. Раз ми вже знаємо, що ці два символи те, що нам потрібно, ми не маємо перевіряти їх знов; ми просто встановлюємо m = 8, i = 2 і продовжуємо перевіряти поточний символ. Таким чином, ми не тільки опустили символи з S, що попередньо збіглись, але й символи з W.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456

Цей пошук зазнає невдачі одразу, бо наш зразок не містить пробілу, як і за першої спроби, ми повертаємось до початку W і починаємо пошук на наступному символі S: m = 11, встановивши i = 0.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

І знов ми відразу ж наштовхуємось на відповідність "ABCDAB", але наступний символ, 'C', не збігається з кінцевим символом 'D' слова W. Як і раніше, ми встановлюємо m = 15, щоб почати з двосимвольного рядку "AB", що веде до поточної позиції, встановлюємо i = 2, і продовжуємо зіставляння з поточної позиції.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456

Цього разу ми можемо завершити зіставляння, першим символом якого є S[15].

Опис і псевдокод для алгоритму пошуку

Наведений вище приклад показує всі елементи алгоритму. Наразі, припустимо наявність таблиці «часткових збігів» T, описаної нижче, яка показує де ми маємо почати нове зіставлення в разі невдачі поточного. Записи T утворені так, що якщо маємо збіг від S[m], що зазнав невдачі при порівнянні S[m + i] з W[i], тоді наступний можливий збіг почнеться з індексу m + i - T[i] в S (T[i] це кількість повернень, які ми маємо зробити після невдачі). Це має два наслідки: перший, T[0] = -1, показує, що якщо W[0] це не збіг, ми не можемо повернутись і повинні просто перевірити наступний символ; і другий, хоча наступний можливий збіг почнеться з індексу m + i - T[i], як у прикладі вище, ми не маємо насправді перевіряти будь-який з символів T[i] після цього, так що ми продовжуємо пошук з W[T[i]]. Далі наводиться приклад псевдокоду алгоритму пошуку КМП.

алгоритм пошук_кмп:
    вхід:
        масив символів, S (текст пошуку)
        масив символів, W (шукане слово)
    вихід:
        ціле число (базована на нулі позиція в S, в якій знайдено W)

    визначаємо змінні:
        ціле число, m ← 0 (початок поточного збігу в S)
        ціле число, i ← 0 (позиція поточного символу в W)
        масив цілих чисел, T (таблиця обчислена деінде)

    доки m+i менша за довжину S, виконувати:
        якщо W[i] = S[m + i],
            якщо i дорівнює (довжина W)-1,
                повернути m
            нехай i ← i + 1
        інакше,
            нехай m ← m + i - T[i],
            якщо T[i] більша ніж -1,
                нехай i ← T[i]
            інакше
                нехай i ← 0
            
    (якщо ми потрапили сюди, пошук в S завершився невдачею)
    повернути довжина S

Швидкодія алгоритму пошуку

Припускаючи існування таблиці T, пошукова складова алгоритму КМП має складність O(k), де k це довжина S. За винятком сталих витрат на виклик функції всі обчислення виконуються циклом while, ми вирахуємо граничну кількість ітерацій циклу; для цього ми спочатку зробимо спостереження про природу T. За визначенням вона побудована так, що якщо частковий збіг, що почався в S[m], провалився під час порівняння S[m + i] з W[i], тоді наступний можливий збіг має початись в S[m + (i - T[i])]. Наступний можливий збіг може трапитись лише на більшому індексі ніж m, з цього випливає, щоT[i] < i.

Знаючи цей факт, покажемо, що цикл може виконатись не більше 2k разів. Для кожної ітерації, виконується одна з двох гілок тіла циклу. У першій гілці безумовно збільшується i і не змінюється m, так що m + i індекс символу S, що ми розглядаємо збільшується. Друга гілка додає i - T[i] до m, і як ми бачили це завжди додатне число. Отже, збільшується початок поточного збігу m. Тепер, цикл завершується якщо m + i = k; з того що кожна гілка циклу може бути відвідана не більш ніж k разів, бо вони збільшують відповідно або m + i або m, і m ≤ m + i: якщо m = k, тоді напевно m + i ≥ k, з того що воно збільшується щонайбільше на одиницю кожного разу, ми мали мати m + i = k в якийсь момент у минулому, яким би способом ми не просувались.

Так як цикл виконується не більше ніж 2k разів, ми показали, що складність алгоритму пошуку O(k).

Ось інший спосіб розгляду часу виконання: Скажімо ми починаємо зіставляти W і S в позиціях i та p, якщо W існує як підрядок S в p, тоді W[0 до m] == S[p до p+m]. За умови успіху (W[i] == S[p+i]), ми збільшуємо i на 1 (i++). При невдачі (W[i] != S[p+i]), вказівник у тексті не змінюється, а вказівник в шуканому слові відкочується на певну кількість символів (i = T[i], де T це таблиця переходів). І ми намагаємося зіставити W[T[i]] з S[p+i]. Найбільший відкіт обмежений i, тобто, для будь-якого незбігу, ми можемо відкотитись щонайбільше на наш поступ до невдачі. Звідси й випливає час 2k.

Таблиця «часткових збігів» (також відома як «функція невдачі»)

Ціль цієї функції дозволити алгоритму уникнути перевірки кожного символу S більш ніж один раз. Головним спостереженням про природу лінійного пошуку, що дозволяє цьому бути це те, що в перевіреному відтинку головного рядку щодо початкового відтинка зразка, ми точно знаємо в яких місцях новий потенційний збіг, що міг би продовжитись до поточної позиції, міг би починатись перед поточною позицією. Інакше кажучи, ми робимо «перед-пошук» зразка і збираємо список усіх можливих позицій відступу, відтинки від яких до поточної позиції утворюють часткові збіги. T[i] це довжина найдовшого можливого вірного початкового сегменту W, який також є відтинком підрядка, що завершується в W[i - 1]. Ми використовуємо домовленість, що порожній рядок має довжину 0. Через те, що незбіг на самому початку алгоритму — це особливий випадок (не існує можливості відступу), ми встановлюємо T[0] = -1, як показано вище.

Приклад роботи алгоритму побудови таблиці

Спочатку ми розглянемо приклад W = "ABCDABD". Ми побачимо, що він подібний до головного пошуку й ефективний з тих самих причин. Встановлюємо T[0] = -1. Для знаходження T[1], ми маємо виявити суфікс "A", який також є префіксом для W. Але такого суфіксу не існує, отже T[1] = 0. Так само, T[2] = 0.

Продовжуючи з T[3], ми зауважуємо наявність короткого шляху перевірки всіх суфіксів: припустимо ми знайшли суфікс, що є префіксом і завершується в W[2] з довжиною 2 (найбільша можлива); тоді його перший символ є префіксом префіксу W, тобто префіксом сам по собі, і завершується в W[1], а ми в випадку T[2] вже визначили, що це неможливо. Отже на кожному кроці, треба перевіряти суфікси довжини m+1 лише якщо було знайдено суфікс довжини m на попередньому кроці(тобто T[x]=m).

Звідси ми навіть не повинні розглядати підрядки довжини 2, і як і на попередньому кроці єдина спроба з довжиною 1 зазнає невдачі, тому T[3] = 0.

Ми переходимо до наступного W[4], 'A'. Та сама логіка показує, що найдовший підрядок на який треба зважати має довжину 1, і хоча тут 'A' спрацьовує, згадуємо, що ми шукаємо на сегмент, що завершується до поточного символу; звідси T[4] = 0 також.

Просуваємось до W[5], який є 'B', ми застосовуємо наступну логіку: якщо ми перед цим знайшли підзразок, що починається перед попереднім символом W[4], що триває до поточного W[5], тоді зокрема він мав би мати вірний початковий відтинок, що завершується в W[4], що заперечується фактом, що ми вже виявили 'A' як єдиний вірний відтинок, що завершується в W[4]. З цього випливає, що ми не маємо дивитись до W[4]. Отже T[5] = 1.

Нарешті, ми розглядаємо наступний символ у відтинку з початком у W[4] = 'A', це буде 'B', він збігається з W[5]. Далі більше, ті ж доводи, що й раніше кажуть, що ми не повинні дивитись перед W[4] для знаходження відтинку для W[6], і ми встановлюємо T[6] = 2.

Отже ми укладаємо таку таблицю:

i	0	1	2	3	4	5	6
W[i]	A	B	C	D	A	B	D
T[i]	−1	0	0	0	0	1	2

Інший приклад, цікавіший і складніший:

i	0	1	2	3	4	5	6	7	8	9	0	1	2	3	4	5	6	7	8	9	0	1	2	3
W[i]	P	A	R	T	I	C	I	P	A	T	E		I	N		P	A	R	A	C	H	U	T	E
T[i]	−1	0	0	0	0	0	0	0	1	2	0	0	0	0	0	0	1	2	3	0	0	0	0	0

Опис і псевдокод алгоритму побудови таблиці

Приклад вище, показує загальну техніку утворення таблиці з найменшими витратами. Загальний принцип пошуку: більша частина роботи виконується до поточного кроку, отже дуже мало треба робити для переходу на наступний. Маленьким ускладненням є те, що логіка вірна в усьому рядку дає невірний результат на початку. Це вимагає деякого початкового коду.

алгоритм таблиця_кмп:
    вхід:
        масив символів, W (слово до розбору)
        масив цілих, T (таблиця до наповнення)
    вихід:
        нічого (але під час дії наповнюється таблиця)

    визначення змінних:
        ціле, pos ← 2 (поточна позиція в T)
        ціле, cnd ← 0 (базований на нулі індекс у W наступного 
символу в поточному підрядку кандидаті)

    (перші кілька значень фіксовані, і відрізняються від запропонованих алгоритмом)
    нехай T[0] ← -1, T[1] ← 0

    доки pos менше ніж довжина W, виконувати:
        (перший варіант: підрядок продовжується)
        якщо W[pos - 1] = W[cnd], 

          нехай cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1

        (другий випадок: не продовжується, але ми можемо відступити)
        інакше, якщо cnd > 0, нехай cnd ← T[cnd]

        (третій випадок: ми вичерпали всіх кандидатів.  Зауважимо cnd = 0)
        інакше, нехай T[pos] ← 0, pos ← pos + 1

Швидкодія алгоритму побудови таблиці

Складність табличного алгоритму дорівнює O(n), де n — це довжина W. За винятком початкового налаштування вся робота виконується в циклі while, отже достатньо показати, що цей цикл виконується за час O(n), чого ми досягнемо через схожі вивчення значень pos і pos - cnd. В першій гілці, pos - cnd зберігається, бо pos і cnd збільшуються одночасно, але звісно, pos збільшилась. В другій гілці, cnd заміняється на T[cnd], як ми бачили вище завжди суворо менша ніж cnd, отже збільшується pos - cnd. В третій гілці, pos збільшується, а cnd ні, отже pos і pos - cnd збільшуються. З того, що pos ≥ pos - cnd, отримуємо, що на кожному кроці збільшується або pos або нижня межа для pos; отже з того, що алгоритм завершується за умови pos = n, він має завершитись не пізніше 2n ітерацій циклу, бо pos - cnd починається з 1. Значить складність табличного алгоритму становить O(n).

Швидкодія алгоритму КМП

Через те, що дві складові алгоритму мають складності, відповідно, O(k) і O(n), складність всього алгоритму становить O(n + k).

Складності залишаються незмінними, попри те скільки зразків, що повторюються в W або S.

Втілення алгоритму

s = 0;
for (i = 1; i <= m; i++) {
  while (s > 0 && a[i] != b[s+1]) s = f(s); // f - функція невдачі (failure function)
  if (a[i] == b[s+l]) s = s + 1;
  if (s == n) return "yes";
}
return "no";

Посилання

• An explanation of the algorithm [Архівовано 16 січня 2021 у Wayback Machine.]
• Knuth-Morris-Pratt algorithm [Архівовано 25 січня 2021 у Wayback Machine.]

Література

• Donald Knuth; James H. Morris, Jr, Vaughan Pratt (1977). Fast pattern matching in strings. SIAM Journal on Computing. 6 (2): 323—350. Архів оригіналу за 4 січня 2010. Процитовано 15 жовтня 2006.