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

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

Клас	Пошук рядка
Найгірша швидкодія	O(nm)
Найкраща швидкодія	O(n+m)
Середня швидкодія	O(n+m)
Просторова складність у найгіршому випадку	O(p)

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

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

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

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

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

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

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

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

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

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

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

Отже, всі ${\displaystyle t_{s}}$ можна обчислити за час Θ(n).

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

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

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

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

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

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

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

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

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

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

Аналіз

У процедурі Rabin_Karp_Matcher на попередню обробку витрачається час ${\displaystyle \Theta (m),}$ а час пошуку у найгіршому випадку дорівнює ${\displaystyle \Theta ((n-m+1)m).}$ Однак, в багатьох практичних задачах очікувана кількість допустимих зсувів є невеликою, тоді час роботи алгоритму коли знайдено c зсувів є ${\displaystyle O((n-m+1)+cm)=O(n+m),}$ плюс час необхідний для перевірки хибних збігів. Ми можемо побудувати евристичний аналіз на припущені, що взяття значень по модулю q діє як випадкове відображення з множини усіх допустимих рядків ${\displaystyle \Sigma ^{*}}$ у ${\displaystyle \mathbb {Z} _{q}.}$ Тоді ми можемо очікувати, що кількість помилкових збігів є ${\displaystyle O(n/q),}$ оскільки ми можемо оцінити шанс того, що будь-який ${\displaystyle t_{s}}$ буде тотожним ${\displaystyle p}$ по модулю ${\displaystyle q,}$ як ${\displaystyle 1/q.}$

Зноски

1. Richard M. Karp and Michael O. Rabin. Efficient Randomized Pattern-Matching Algorithms. Technical Report TR-31-81, Aiken Computation Laboratory, Havard University, 1981.

Джерела

• 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

Див. також

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