Алгоритм Рабіна — Карпа
Алгоритм Рабіна-Карпа — алгоритм пошуку рядка запропонований Рабіном і Карпом[1]. Алгоритм показує високу продуктивність на практиці, а також дозволяє узагальнення на інші споріднені задачі.
Клас | Пошук рядка |
---|---|
Найгірша швидкодія | O(nm) |
Найкраща швидкодія | O(n+m) |
Середня швидкодія | O(n+m) |
Просторова складність у найгіршому випадку | O(p) |
Ідея алгоритму полягає в заміні текстових рядків числами, порівняння яких можна виконувати значно швидше.
Ідея алгоритму
Для простоти припустимо, що алфавіт складається з десяткових цифр Σ = {0,1,…,9}. (В загальному випадку можна припустити, що кожний символ — це цифра в системі числення з основою d, де d = |Σ|.) Після цього, рядок з k символів, можна розглядати як число довжини k. Тобто символьний рядок «12345» відповідає числу 12345.
Для заданого зразка P[1..m] позначимо через p відповідне йому десяткове значення. Аналогічно, для заданого тексту T[1..n] позначимо через десяткове значення підрядка T[s+1..s+m] довжини m при s = 0,1,…,n-m. Очевидно, що тоді і тільки тоді, коли T[s+1..s+m]=P[1..m]; таким чином, s — допустимий зсув тоді і тільки тоді, коли .
Якщо значення p можна обчислити за Θ(m) а значення за сумарний час Θ(n-m+1), то усі допустимі зсуви можна було б знайти за час Θ(m) + Θ(n-m+1) = Θ(n) шляхом порівняння p з кожним з можливих . (Покищо до уваги не береться той факт, що величини p і можуть виявитись дуже великими.)
З допомогою схеми Горнера величину p можна обчислити за час Θ(m):
Значення можна обчислити з масиву T[1..n] аналогічним способом за час Θ(m). В той же час, знаючи величину величину можна обчислити за фіксований час:
(1)
Наприклад, якщо m = 5 і , то потрібно видалити цифру у старшому розряді T[s+1] = 3 і додати цифру у молодший розряд (припустимо, T[s+5+1]=2). В результаті отримуємо .
Отже, всі можна обчислити за час Θ(n).
В цій процедурі пошуку наявна складність, пов'язана з тим, що значення p і можуть виявитись занадто великими і з ними буде незручно працювати. Якщо зразок P складається з m цифр, то припущення про те, що арифметичні операції з числом p (до якого входить m цифр) займають «фіксований час», не відповідає дійсності. Ця проблема має просте вирішення: обчислення значень p і за модулем деякого числа q. Оскільки обчислення проводяться рекурентно, то знаходження p можна виконати за Θ(m) а всіх відповідно за Θ(n). Значення q звичайно обирають таким, щоб величина dq не перевищувала максимальну величину комп'ютерного слова.
Тоді, співвідношення (1) приймає вигляд:
(2)
де — значення, що приймає цифра «1» поставлена в старший розряд m-значного текстового рядка.
Робота по модулю q має свої недоліки, оскільки з не випливає, що . З іншого боку, якщо , то обов'язково виконується співвідношення і можна зробити висновок, що зсув s неприпустимий. Таким чином, співвідношення можна використовувати як швидкий евристичний тест, що дозволяє виключити із розгляду деякі неприпустимі зсуви. Усі зсуви, для яких співвідношення виконується, треба додатково перевірити. Якщо q достатньо велике, то можна сподіватися, що хибні зсуви будуть зустрічатися досить рідко і час додаткової перевірки буде малим.
Опис алгоритму
Алгоритм полягає в наступному:
- обчислити число p;
- обчислити всі ;
- Для тих s для яких , виконати перевірку P[1..m] = T[s+1..s+m].
Псевдокод алгоритму
1 2 3 4 5 6 for to //Попередня обробка 7 do 8 9 for to //Перевірка 10 do if 11 then if 12 then print «Зразок знайдено зі зсувом» s 13 if 14 then
Аналіз
У процедурі Rabin_Karp_Matcher на попередню обробку витрачається час а час пошуку у найгіршому випадку дорівнює Однак, в багатьох практичних задачах очікувана кількість допустимих зсувів є невеликою, тоді час роботи алгоритму коли знайдено c зсувів є плюс час необхідний для перевірки хибних збігів. Ми можемо побудувати евристичний аналіз на припущені, що взяття значень по модулю 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