Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Алгоритм Бойєра — Мура — Хорспула — алгоритм пошуку рядка — спрощений варіант алгоритму Бойера — Мура. АБМХ працює краще алгоритму Бояра — Мура на випадкових текстах. До того ж, вимагає багатьох попередніх обчислень евристика збіглася суфікса опускається.
Опис алгоритму
Спочатку будується таблиця зміщень для шуканого шаблону. Поєднується початок тексту (рядки) і шаблона, перевірка починається з останнього символу шаблону.
Якщо останній символ шаблону і відповідний йому при накладенні символ рядка не збігаються, то зразок зрушується щодо рядка на величину, отриману з таблиці зміщень. Причому символ береться з рядка (а не з шаблону), відповідний зсув знаходиться в таблиці. Проводиться зрушення і знову починається перевірка з останнього символу.
Якщо ж символи збігаються, проводиться порівняння передостаннього символу шаблону і т. д. Якщо всі символи шаблону збіглися з накладеними символами рядки, значить, підрядок знайдена, і пошук закінчено. Якщо ж якийсь (не останній) символ шаблону не збігається з відповідним символом рядка, шаблон зсувається на один символ вправо, і перевірка знову починається з останнього символу. Весь алгоритм виконується до тих пір, поки або не буде знайдено входження шуканого зразка, або не буде досягнуто кінець рядка.
Побудова таблиці
У таблиці зберігається величина зсуву для кожного символу в шаблоні. Величина зрушення визначається з тих міркувань, що він повинен бути максимально можливим, але таким, щоб не пропустити входження шуканого шаблону.
Таблиця містить список всіх символів в шаблоні. У відповідність кожному символу ставиться його порядковий номер, рахуючи з кінця рядка. Якщо символ зустрічається кілька разів, то використовується саме праве входження.
Приклад
Для шаблону «abbad» таблиця має такий вигляд.
| a | b | d |
|---|---|---|
| 1 | 2 | 5 |
Примітки
Позиція останнього символу шаблону в алгоритмі не розглядається, тобто значення зміщення для символу 'd' дорівнюватиме довжині шаблону — 5. У таблиці відповідності символ — зміщення, для всіх символів, що не увійшли до шаблону, величина зсуву встановлюється рівною довжині шаблону — 5.
Приклад роботи алгоритму
Бажаємий шаблон — «abbad» (таблиця для цього шаблону побудована вище).
abeccacbadbabbad abbad
Накладаємо зразок на рядок. Останній символ заданої стрічки "з"не міститься у зразку. Зрушуємо зразок вправо на 5 позицій згідно зі значенням зсуву для «с»:
abeccacbadbabbad abbad
Три символу зразка збіглися, а четвертий — ні. Зсуваємо зразок вправо на 1:
abeccacbadbabbad abbad
Останній символ рядка b не збігається з символом шаблона. Зсуваємо зразок вправо на 2:
abeccacbadbabbad abbad
І знову останній символ рядка b не збігається з символом шаблона. Зсуваємо на 2 позиції:
abeccacbadbabbad abbad
Останній символ заданої стрічки «a» знову не збігається з символом шаблону. Відповідно до таблиці зміщень зрушуємо зразок на 1 позицію і отримуємо шукане входження зразка:
abeccacbadbabbad abbad
Приклад
Процедура отримує посилання на три змінні: haystack і needle строкового типу і result цілого типу, причому перші дві для процедури є константами і не можуть бути змінені. У haystack повинна міститися рядок, в якій буде здійснено пошук, а needle повинна містити підрядок, яку треба знайти. В результаті виконання процедури мінлива result буде містити номер позиції, починаючи з якого підрядок needle входить в рядок haystack, або 0, якщо входження немає.
procedure boyer_moore(const haystack: string; const needle: string; var result: integer); var i, j, k : integer; needle_len : integer; haystack_len : integer; needle_table : array[char] of byte; begin needle_len := length(needle); haystack_len := length(haystack); if needle_len < haystack_len then begin for i := 0 to 255 do needle_table[chr(i)] := needle_len; for i := 1 to needle_len-1 do needle_table[needle[i]] := needle_len-i; i := needle_len; j := i; while (j > 0) and (i <= haystack_len) do begin j := needle_len; k := i; while (j > 0) and (haystack[k] = needle[j]) do begin dec(k); dec(j); end; i := i + needle_table[haystack[i]]; end; if k > haystack_len - needle_len then result := 0 else result := k + 1; end else result := 0; end; Література
- Ніклаус Вірт Алгоритми і структури даних. — М.: Невський Діалект, 2006. С. 352.
 | Це незавершена стаття про алгоритми. Ви можете проєкту, виправивши або дописавши її. |
| Ця стаття потребує додаткових для поліпшення її . (травень 2016) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm Bojyera Mura Horspula algoritm poshuku ryadka sproshenij variant algoritmu Bojera Mura ABMH pracyuye krashe algoritmu Boyara Mura na vipadkovih tekstah Do togo zh vimagaye bagatoh poperednih obchislen evristika zbiglasya sufiksa opuskayetsya Opis algoritmuSpochatku buduyetsya tablicya zmishen dlya shukanogo shablonu Poyednuyetsya pochatok tekstu ryadki i shablona perevirka pochinayetsya z ostannogo simvolu shablonu Yaksho ostannij simvol shablonu i vidpovidnij jomu pri nakladenni simvol ryadka ne zbigayutsya to zrazok zrushuyetsya shodo ryadka na velichinu otrimanu z tablici zmishen Prichomu simvol beretsya z ryadka a ne z shablonu vidpovidnij zsuv znahoditsya v tablici Provoditsya zrushennya i znovu pochinayetsya perevirka z ostannogo simvolu Yaksho zh simvoli zbigayutsya provoditsya porivnyannya peredostannogo simvolu shablonu i t d Yaksho vsi simvoli shablonu zbiglisya z nakladenimi simvolami ryadki znachit pidryadok znajdena i poshuk zakincheno Yaksho zh yakijs ne ostannij simvol shablonu ne zbigayetsya z vidpovidnim simvolom ryadka shablon zsuvayetsya na odin simvol vpravo i perevirka znovu pochinayetsya z ostannogo simvolu Ves algoritm vikonuyetsya do tih pir poki abo ne bude znajdeno vhodzhennya shukanogo zrazka abo ne bude dosyagnuto kinec ryadka Pobudova tabliciU tablici zberigayetsya velichina zsuvu dlya kozhnogo simvolu v shabloni Velichina zrushennya viznachayetsya z tih mirkuvan sho vin povinen buti maksimalno mozhlivim ale takim shob ne propustiti vhodzhennya shukanogo shablonu Tablicya mistit spisok vsih simvoliv v shabloni U vidpovidnist kozhnomu simvolu stavitsya jogo poryadkovij nomer rahuyuchi z kincya ryadka Yaksho simvol zustrichayetsya kilka raziv to vikoristovuyetsya same prave vhodzhennya Priklad Dlya shablonu abbad tablicya maye takij viglyad a b d 1 2 5PrimitkiPoziciya ostannogo simvolu shablonu v algoritmi ne rozglyadayetsya tobto znachennya zmishennya dlya simvolu d dorivnyuvatime dovzhini shablonu 5 U tablici vidpovidnosti simvol zmishennya dlya vsih simvoliv sho ne uvijshli do shablonu velichina zsuvu vstanovlyuyetsya rivnoyu dovzhini shablonu 5 Priklad roboti algoritmu Bazhayemij shablon abbad tablicya dlya cogo shablonu pobudovana vishe abeccacbadbabbad abbad Nakladayemo zrazok na ryadok Ostannij simvol zadanoyi strichki z ne mistitsya u zrazku Zrushuyemo zrazok vpravo na 5 pozicij zgidno zi znachennyam zsuvu dlya s abeccacbadbabbad abbad Tri simvolu zrazka zbiglisya a chetvertij ni Zsuvayemo zrazok vpravo na 1 abeccacbadbabbad abbad Ostannij simvol ryadka b ne zbigayetsya z simvolom shablona Zsuvayemo zrazok vpravo na 2 abeccacbadbabbad abbad I znovu ostannij simvol ryadka b ne zbigayetsya z simvolom shablona Zsuvayemo na 2 poziciyi abeccacbadbabbad abbad Ostannij simvol zadanoyi strichki a znovu ne zbigayetsya z simvolom shablonu Vidpovidno do tablici zmishen zrushuyemo zrazok na 1 poziciyu i otrimuyemo shukane vhodzhennya zrazka abeccacbadbabbad abbadPrikladPaskal Procedura otrimuye posilannya na tri zminni haystack i needle strokovogo tipu i result cilogo tipu prichomu pershi dvi dlya proceduri ye konstantami i ne mozhut buti zmineni U haystack povinna mistitisya ryadok v yakij bude zdijsneno poshuk a needle povinna mistiti pidryadok yaku treba znajti V rezultati vikonannya proceduri minliva result bude mistiti nomer poziciyi pochinayuchi z yakogo pidryadok needle vhodit v ryadok haystack abo 0 yaksho vhodzhennya nemaye procedure boyer moore const haystack string const needle string var result integer var i j k integer needle len integer haystack len integer needle table array char of byte begin needle len length needle haystack len length haystack if needle len lt haystack len then begin for i 0 to 255 do needle table chr i needle len for i 1 to needle len 1 do needle table needle i needle len i i needle len j i while j gt 0 and i lt haystack len do begin j needle len k i while j gt 0 and haystack k needle j do begin dec k dec j end i i needle table haystack i end if k gt haystack len needle len then result 0 else result k 1 end else result 0 end LiteraturaNiklaus Virt Algoritmi i strukturi danih M Nevskij Dialekt 2006 S 352 ISBN 5 7940 0065 1 Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno traven 2016