Алгоритм Рабіна-Карпа — алгоритм пошуку рядка запропонований Рабіном і Карпом. Алгоритм показує високу продуктивність на практиці, а також дозволяє узагальнення на інші споріднені задачі.
Клас | Пошук рядка |
---|---|
Найгірша швидкодія | 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, Інтернет
Algoritm Rabina Karpa algoritm poshuku ryadka zaproponovanij Rabinom i Karpom Algoritm pokazuye visoku produktivnist na praktici a takozh dozvolyaye uzagalnennya na inshi sporidneni zadachi Algoritm Rabina KarpaKlasPoshuk ryadkaNajgirsha shvidkodiyaO nm Najkrasha shvidkodiyaO n m Serednya shvidkodiyaO n m Prostorova skladnist u najgirshomu vipadkuO p Ideya algoritmu polyagaye v zamini tekstovih ryadkiv chislami porivnyannya yakih mozhna vikonuvati znachno shvidshe Ideya algoritmuDlya prostoti pripustimo sho alfavit skladayetsya z desyatkovih cifr S 0 1 9 V zagalnomu vipadku mozhna pripustiti sho kozhnij simvol ce cifra v sistemi chislennya z osnovoyu d de d S Pislya cogo ryadok z k simvoliv mozhna rozglyadati yak chislo dovzhini k Tobto simvolnij ryadok 12345 vidpovidaye chislu 12345 Dlya zadanogo zrazka P 1 m poznachimo cherez p vidpovidne jomu desyatkove znachennya Analogichno dlya zadanogo tekstu T 1 n poznachimo cherez t s displaystyle t s desyatkove znachennya pidryadka T s 1 s m dovzhini m pri s 0 1 n m Ochevidno sho t s p displaystyle t s p todi i tilki todi koli T s 1 s m P 1 m takim chinom s dopustimij zsuv todi i tilki todi koli t s p displaystyle t s p Yaksho znachennya p mozhna obchisliti za 8 m a znachennya t s displaystyle t s za sumarnij chas 8 n m 1 to usi dopustimi zsuvi mozhna bulo b znajti za chas 8 m 8 n m 1 8 n shlyahom porivnyannya p z kozhnim z mozhlivih t s displaystyle t s Pokisho do uvagi ne beretsya toj fakt sho velichini p i t s displaystyle t s mozhut viyavitis duzhe velikimi Z dopomogoyu shemi Gornera velichinu p mozhna obchisliti za chas 8 m p P m 10 P m 1 10 P m 2 10 P 2 10 P 1 displaystyle p P m 10 P m 1 10 P m 2 dots 10 P 2 10P 1 dots Znachennya t 0 displaystyle t 0 mozhna obchisliti z masivu T 1 n analogichnim sposobom za chas 8 m V toj zhe chas znayuchi velichinu t s displaystyle t s velichinu t s 1 displaystyle t s 1 mozhna obchisliti za fiksovanij chas t s 1 10 t s 10 m 1 T s 1 T s m 1 displaystyle t s 1 10 t s 10 m 1 T s 1 T s m 1 1 Napriklad yaksho m 5 i t s 31415 displaystyle t s 31415 to potribno vidaliti cifru u starshomu rozryadi T s 1 3 i dodati cifru u molodshij rozryad pripustimo T s 5 1 2 V rezultati otrimuyemo t s 1 10 31415 10000 3 2 14152 displaystyle t s 1 10 31415 10000 cdot 3 2 14152 Otzhe vsi t s displaystyle t s mozhna obchisliti za chas 8 n V cij proceduri poshuku nayavna skladnist pov yazana z tim sho znachennya p i t s displaystyle t s mozhut viyavitis zanadto velikimi i z nimi bude nezruchno pracyuvati Yaksho zrazok P skladayetsya z m cifr to pripushennya pro te sho arifmetichni operaciyi z chislom p do yakogo vhodit m cifr zajmayut fiksovanij chas ne vidpovidaye dijsnosti Cya problema maye proste virishennya obchislennya znachen p i t s displaystyle t s za modulem deyakogo chisla q Oskilki obchislennya provodyatsya rekurentno to znahodzhennya p mozhna vikonati za 8 m a vsih t s displaystyle t s vidpovidno za 8 n Znachennya q zvichajno obirayut takim shob velichina dq ne perevishuvala maksimalnu velichinu komp yuternogo slova Todi spivvidnoshennya 1 prijmaye viglyad t s 1 d t s T s 1 h T s m 1 mod q displaystyle t s 1 d t s T s 1 h T s m 1 mod q 2 de h d m 1 mod q displaystyle h equiv d m 1 pmod q znachennya sho prijmaye cifra 1 postavlena v starshij rozryad m znachnogo tekstovogo ryadka Robota po modulyu q maye svoyi nedoliki oskilki z t s p mod q displaystyle t s equiv p pmod q ne viplivaye sho t s p displaystyle t s p Z inshogo boku yaksho t s p mod q displaystyle t s not equiv p pmod q to obov yazkovo vikonuyetsya spivvidnoshennya t s p displaystyle t s not p i mozhna zrobiti visnovok sho zsuv s nepripustimij Takim chinom spivvidnoshennya t s p mod q displaystyle t s equiv p pmod q mozhna vikoristovuvati yak shvidkij evristichnij test sho dozvolyaye viklyuchiti iz rozglyadu deyaki nepripustimi zsuvi Usi zsuvi dlya yakih spivvidnoshennya vikonuyetsya treba dodatkovo pereviriti Yaksho q dostatno velike to mozhna spodivatisya sho hibni zsuvi budut zustrichatisya dosit ridko i chas dodatkovoyi perevirki bude malim Opis algoritmuAlgoritm polyagaye v nastupnomu obchisliti chislo p obchisliti vsi t s displaystyle t s Dlya tih s dlya yakih t s p displaystyle t s p vikonati perevirku P 1 m T s 1 s m Psevdokod algoritmu R a b i n K a r p M a t c h e r T P d q displaystyle Rabin Karp Matcher T P d q 1 n l e n g t h T displaystyle n leftarrow length T 2 m l e n g t h P displaystyle m leftarrow length P 3 h d m 1 mod q displaystyle h leftarrow d m 1 mod q 4 p 0 displaystyle p leftarrow 0 5 t 0 0 displaystyle t 0 leftarrow 0 6 for i 1 displaystyle i leftarrow 1 to m displaystyle m Poperednya obrobka 7 do p d p P i mod q displaystyle p leftarrow dp P i mod q 8 t 0 d t 0 T i mod q displaystyle t 0 leftarrow dt 0 T i mod q 9 for s 0 displaystyle s leftarrow 0 to n m displaystyle n m Perevirka 10 do if p t s displaystyle p t s 11 then if P 1 m T s 1 s m displaystyle P 1 m T s 1 s m 12 then print Zrazok znajdeno zi zsuvom s 13 if s lt n m displaystyle s lt n m 14 then t s 1 d t s T s 1 h T s m 1 mod q displaystyle t s 1 leftarrow d t s T s 1 h T s m 1 mod q AnalizU proceduri Rabin Karp Matcher na poperednyu obrobku vitrachayetsya chas 8 m displaystyle Theta m a chas poshuku u najgirshomu vipadku dorivnyuye 8 n m 1 m displaystyle Theta n m 1 m Odnak v bagatoh praktichnih zadachah ochikuvana kilkist dopustimih zsuviv ye nevelikoyu todi chas roboti algoritmu koli znajdeno c zsuviv ye O n m 1 c m O n m displaystyle O n m 1 cm O n m plyus chas neobhidnij dlya perevirki hibnih zbigiv Mi mozhemo pobuduvati evristichnij analiz na pripusheni sho vzyattya znachen po modulyu q diye yak vipadkove vidobrazhennya z mnozhini usih dopustimih ryadkiv S displaystyle Sigma u Z q displaystyle mathbb Z q Todi mi mozhemo ochikuvati sho kilkist pomilkovih zbigiv ye O n q displaystyle O n q oskilki mi mozhemo ociniti shans togo sho bud yakij t s displaystyle t s bude totozhnim p displaystyle p po modulyu q displaystyle q yak 1 q displaystyle 1 q ZnoskiRichard M Karp and Michael O Rabin Efficient Randomized Pattern Matching Algorithms Technical Report TR 31 81 Aiken Computation Laboratory Havard University 1981 DzherelaKarp 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 ISBN 0 07 013151 1Div takozhAlgoritm poshuku ryadka Spisok algoritmiv