Алгоритм Бойєра — Мура — Хорспула

Алгоритм Бойєра — Мура — Хорспула — алгоритм пошуку рядка — спрощений варіант алгоритму Бойера — Мура. АБМХ працює краще алгоритму Бояра — Мура на випадкових текстах. До того ж, вимагає багатьох попередніх обчислень евристика збіглася суфікса опускається.

Спочатку будується таблиця зміщень для шуканого шаблону. Поєднується початок тексту (рядки) і шаблона, перевірка починається з останнього символу шаблону.

Якщо останній символ шаблону і відповідний йому при накладенні символ рядка не збігаються, то зразок зрушується щодо рядка на величину, отриману з таблиці зміщень. Причому символ береться з рядка (а не з шаблону), відповідний зсув знаходиться в таблиці. Проводиться зрушення і знову починається перевірка з останнього символу.

Якщо ж символи збігаються, проводиться порівняння передостаннього символу шаблону і т. д. Якщо всі символи шаблону збіглися з накладеними символами рядки, значить, підрядок знайдена, і пошук закінчено. Якщо ж якийсь (не останній) символ шаблону не збігається з відповідним символом рядка, шаблон зсувається на один символ вправо, і перевірка знову починається з останнього символу. Весь алгоритм виконується до тих пір, поки або не буде знайдено входження шуканого зразка, або не буде досягнуто кінець рядка.

У таблиці зберігається величина зсуву для кожного символу в шаблоні. Величина зрушення визначається з тих міркувань, що він повинен бути максимально можливим, але таким, щоб не пропустити входження шуканого шаблону.

Таблиця містить список всіх символів в шаблоні. У відповідність кожному символу ставиться його порядковий номер, рахуючи з кінця рядка. Якщо символ зустрічається кілька разів, то використовується саме праве входження.

Для шаблону «abbad» таблиця має такий вигляд.

Позиція останнього символу шаблону в алгоритмі не розглядається, тобто значення зміщення для символу '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. ISBN 5-7940-0065-1

Це незавершена стаття про алгоритми. Ви можете допомогти проєкту, виправивши або дописавши її.

Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. Будь ласка, допоможіть удосконалити цю статтю, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки. Матеріал без джерел може бути піддано сумніву та вилучено. (травень 2016)