Алгоритм Рабіна-Карпа — алгоритм пошуку рядка запропонований Рабіном і Карпом. Алгоритм показує високу продуктивність на практиці, а також дозволяє узагальнення на інші споріднені задачі.
Клас | Пошук рядка |
---|---|
Найгірша швидкодія | 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). «». 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.
Див. також
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет