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

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

Опис алгоритму

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

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

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

Побудова таблиці

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

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

Приклад

Для шаблону «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. ISBN 5-7940-0065-1