Алгоритм Рабіна-Карпа

Алгоритм Рабіна-Карпа — алгоритм пошуку рядка запропонований Рабіном і Карпом. Алгоритм показує високу продуктивність на практиці, а також дозволяє узагальнення на інші споріднені задачі.

Ідея алгоритму полягає в заміні текстових рядків числами, порівняння яких можна виконувати значно швидше.

Ідея алгоритму

Для простоти припустимо, що алфавіт складається з десяткових цифр Σ = {0,1,…,9}. (В загальному випадку можна припустити, що кожний символ — це цифра в системі лічення з основою d, де d = |Σ|.) Після цього, рядок з k символів, можна розглядати як число довжини k. Тобто символьний рядок «12345» відповідає числу 12345.

Для заданого зразка P[1..m] позначимо через p відповідне йому десяткове значення. Аналогічно, для заданого текста T[1..n] позначемо через $t_s$ десяткове значення підрядка T[s+1..s+m] довжини m при s = 0,1,…,n-m. Очевидно, що $t_s = p$ тоді і тільки тоді, коли T[s+1..s+m]=P[1..m]; таким чином, s — допустимий зсув тоді і тільки тоді, коли $t_s = p$.

Якщо значення p можна обчислити за Θ(m) а значення $t_s$ за сумарний час Θ(n-m+1), то усі допустимі зсуви можна було б знайти за час Θ(m) + Θ(n-m+1) = Θ(n) шляхом порівняння p з кожним з можливих $t_s$. (Покищо до уваги не приймається той факт, що величини p і $t_s$ можуть виявитись дуже великими.)

З допомогою схеми Горнера величину p можна обчислити за час Θ(m):

$\;p=P[m]+10(P[m-1] +10(P[m-2] + \dots + 10(P[2]+10P[1]))\dots)).$

Значення $t_0$ можна обчислити з масиву T[1..n] аналогічним способом за час Θ(m). В той же час, знаючи величину $t_s$ величину $t_{s+1}$ можна обчислити за фіксований час:

$\;t_{s+1} = 10(t_s-10^{m-1}T[s+1])+T[s+m+1].$    (1)

Наприклад, якщо m = 5 і $t_s = 31415$, то потрібно видалити цифру у старшому розряді T[s+1] = 3 і додати цифру у молодший розряд (припустимо, T[s+5+1]=2). В результаті отримуємо $t_{s+1}=10(31415-10000\cdot 3)+2 = 14152$.

Отже, всі $t_s$ можна обчислити за час Θ(n).

В цій процедурі пошуку наявна складність, пов'язана з тим, що значення p і $t_s$ можуть виявитись занадто великими і з ними буде незручно працювати. Якщо зразок P складається з m цифр, то припущення про те, що арефметичні операції з числом p (до якого входить m цифр) займають «фіксований час», не відповідає дійсності. Ця проблема має просте вирішення: обчислення значень p і $t_s$ за модулем деякого числа q. Оскільки обчислення проводяться рекурентно, то знаходження p можна виконати за Θ(m) а всіх $t_s$ відповідно за Θ(n). Значення q звичайно оберають таким, щоб величина dq не перевищувала максимальну величину комп'ютерного слова.

Тоді, співвідношення (1) приймає вигляд:

$\;t_{s+1} = (d(t_s-T[s+1]h)+T[s+m+1]) \mod q,$    (2)

де $h \equiv d^{m-1} \pmod{q}$ — значення, що приймає цифра «1» поставлена в старший розряд m-значного тектового рядка.

Робота по модулю q має свої недоліки, оскільки з $t_s \equiv p\pmod{q}$ не випливає, що $\;t_s = p$. З іншого боку, якщо $t_s \not\equiv p\pmod{q}$, то обов'язково виконується співвідношення $\;t_s \not = p$ і можна зробити висновок, що зсув s неприпустимий. Таким чином, співвідношення $t_s \equiv p\pmod{q}$ можна використовувати в якості швидкого евристичного теста, що дозволяє виключити із розгляду деякі неприпустимі зсуви. Усі зсуви, для яких співвідношення виконується, треба додатково перевірити. Якщо q достатньо велике, то можна сподіватися, що хибні зсуви будуть зустрічатися досить рідко і час додаткової перевірки буде малим.

Опис алгоритму

Алгоритм полягає в наступному:

1. обчислити число p;
2. обчислити всі $t_s$;
3. Для тих s для яких $t_s = p$, виконати перевірку P[1..m] = T[s+1..s+m].

Псевдокод алгоритму

$\;Rabin\_Karp\_Matcher(T,P,d,q)$
 1 $n\leftarrow length[T]$
 2 $m\leftarrow length[P]$
 3 $h\leftarrow d^{m-1} \mod q$
 4 $p\leftarrow 0$
 5 $t_0\leftarrow 0$
 6 for $i\leftarrow 1$ to $\;m$ //Попередня обробка
 7     do $p\leftarrow (dp+P[i])\mod q$
 8        $t_0\leftarrow (dt_0+T[i])\mod q$
 9 for $s\leftarrow 0$ to $\;n-m$ //Перевірка
10     do if $\;p=t_s$
11           then if $\;P[1..m]=T[s+1..s+m]$
12                   then print «Зразок знайдено зі зсувом» s
13        if $\;s<n-m$
14           then $t_{s+1} \leftarrow(d(t_s-T[s+1]h)+T[s+m+1)\mod q$

Аналіз

У процедурі Rabin_Karp_Matcher на попередню обробку витрачається час Θ(m), а час пошуку у найгіршому випадку дорівнює Θ((n-m+1)m). Однак, в багатьох практичних задачах очікувана кількість допустимих зсувів є невеликою, тоді час роботи алгоритму є O(n+m).

Джерела

• Karp and Rabin's original paper: Karp, Richard M.; Rabin, Michael O. (March 1987). «Efficient randomized pattern-matching algorithms». IBM Journal of Research and Development 31 (2), 249-260.
• Thimas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1

Дивіться також

• Алгоритм пошуку рядка
• Список алгоритмів