Алгоритм Бойєра — Мура — Хорспула
Алгоритм Бойєра — Мура — Хорспула — алгоритм пошуку рядка — спрощений варіант алгоритму Бойера — Мура. АБМХ працює краще алгоритму Бояра — Мура на випадкових текстах. До того ж, вимагає багатьох попередніх обчислень евристика збіглася суфікса опускається.
Опис алгоритму
Спочатку будується таблиця зміщень для шуканого шаблону. Поєднується початок тексту (рядки) і шаблона, перевірка починається з останнього символу шаблону.
Якщо останній символ шаблону і відповідний йому при накладенні символ рядка не збігаються, то зразок зрушується щодо рядка на величину, отриману з таблиці зміщень. Причому символ береться з рядка (а не з шаблону), відповідний зсув знаходиться в таблиці. Проводиться зрушення і знову починається перевірка з останнього символу.
Якщо ж символи збігаються, проводиться порівняння передостаннього символу шаблону і т. д. Якщо всі символи шаблону збіглися з накладеними символами рядки, значить, підрядок знайдена, і пошук закінчено. Якщо ж якийсь (не останній) символ шаблону не збігається з відповідним символом рядка, шаблон зсувається на один символ вправо, і перевірка знову починається з останнього символу. Весь алгоритм виконується до тих пір, поки або не буде знайдено входження шуканого зразка, або не буде досягнуто кінець рядка.
Побудова таблиці
У таблиці зберігається величина зсуву для кожного символу в шаблоні. Величина зрушення визначається з тих міркувань, що він повинен бути максимально можливим, але таким, щоб не пропустити входження шуканого шаблону.
Таблиця містить список всіх символів в шаблоні. У відповідність кожному символу ставиться його порядковий номер, рахуючи з кінця рядка. Якщо символ зустрічається кілька разів, то використовується саме праве входження.
Приклад
Для шаблону «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