Mryntu

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

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

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

Зміст

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

2 Опис алгоритму
- 2.1 Псевдокод алгоритму

3 Аналіз

4 Зноски

5 Джерела

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

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

Для простоти припустимо, що алфавіт складається з десяткових цифр Σ = 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-1T[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-10000cdot 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 hequiv d^m-1pmod q$ — значення, що приймає цифра «1» поставлена в старший розряд m-значного текстового рядка.

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

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

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

обчислити число p;

обчислити всі $displaystyle t_s$ ;

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

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

 $displaystyle ;Rabin_Karp_Matcher(T,P,d,q)$ 
 1  $displaystyle nleftarrow length[T]$ 
 2  $displaystyle mleftarrow length[P]$ 
 3  $displaystyle hleftarrow d^m-1mod q$ 
 4  $displaystyle pleftarrow 0$ 
 5  $displaystyle t_0leftarrow 0$ 
 6 for  $displaystyle ileftarrow 1$  to  $displaystyle ;m$  //Попередня обробка
 7 do  $displaystyle pleftarrow (dp+P[i])mod q$ 
 8  $displaystyle t_0leftarrow (dt_0+T[i])mod q$ 
 9 for  $displaystyle sleftarrow 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+1leftarrow (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$ буде тотожним $p$ по модулю $displaystyle q,$ як $displaystyle 1/q.$

Зноски |

↑ 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

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

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

Список алгоритмів

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

搜尋此網誌