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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Алгоритм КМП[ред.ред. код]

Приклад алгоритму пошуку[ред.ред. код]

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

             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)

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

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

Посилання[ред.ред. код]

Література[ред.ред. код]