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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм Бойера — Мура — Хорспула — алгоритм поиска подстроки в строке, упрощённый вариант алгоритма Бойера — Мура. АБМХ работает лучше алгоритма Бойера — Мура на случайных текстах, оценка в среднем от \frac{1}{|\Sigma|} до \frac{2}{|\Sigma|+1} на один символ текста[1]. К тому же, требующая многих предварительных вычислений эвристика совпавшего суффикса опускается.

Впрочем, оценка (в худшем случае на непериодических шаблонах) у АБМХ составляет |needle|·|haystack| (вместо 3|haystack| у Бойера-Мура).

Описание алгоритма[править | править вики-текст]

Алгоритм является модификацией алгоритма Бойера-Мура. Идея алгоритма такова.

1. Сканирование слева направо, сравнение в режиме «чёрного ящика». Как и в примитивном алгоритме, совмещается начало текста и шаблона, проводится сравнение обычной процедурой «сравнить участки памяти». Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.

Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на несколько символов вправо. Эти «несколько» выбираются в соответствии с такой эвристикой.

2. Изменённая эвристика стоп-символа. Берём символ текста, оказавшийся над последним символом шаблона (независимо от того, где случилось несовпадение!). На рисунке это «b».

                             ↓ стоп-символ
Текст                a b a d b * * * *
Шаблон               a b b a d
Следующая проверка       a b b a d

Сдвигаем шаблон так, чтобы под стоп-символом оказалась буква «b» шаблона. Это реализуется с помощью таблицы смещений: для каждого символа алфавита храним максимально возможный сдвиг, не пропускающий стоп-символ. То есть (при нумерации строк с 1): shift(c) = |needle|−lastpos(c, needle[1..|needle|−1]), где lastpos — последнее вхождение символа в строку, needle[a..b] — операция взятия подстроки.

Для шаблона «abbad» таблица имеет следующий вид.

Символ a b (все остальные)
Смещение 1 2 5

Для символов, не вошедших в шаблон, величина смещения устанавливается равной длине шаблона — 5. Последний символ шаблона при вычислении таблицы смещений не рассматривается (чревато зацикливанием).

Таблицу удобнее рассчитывать, проходя по всем символам шаблона:

 for c=MIN_CHAR..MAX_CHAR
   shift[c] = |needle|

 for i=1..|needle|-1
   shift[needle[i]] = |needle|-i

Пример работы алгоритма[править | править вики-текст]

Искомый шаблон — «abbad» (таблица для этого шаблона построена выше).

abeccacbadbabbad
abbad

Накладываем образец на строку. Последний символ исходной строки «с» не содержится в образце. Сдвигаем образец вправо на 5 позиций в соответствии со значением смещения для «с»:

abeccacbadbabbad
     abbad

Три символа образца совпали, а четвертый — нет. Сдвигаем образец вправо на 5 позиций в соответствии со значением смещения для «d»:

abeccacbadbabbad
          abbad

Последний символ строки «a» не совпадает с символом шаблона. Сдвигаем образец вправо на 1 в соответствии со значением смещения для «a» и получаем искомое вхождение образца:

abeccacbadbabbad
           abbad

Варианты[править | править вики-текст]

Алгоритм Санди[править | править вики-текст]

За стоп-символ берём символ, следующий за needle.

Алгоритм Райты[править | править вики-текст]

Эмпирический алгоритм, оптимизированный под английские тексты. Сравнивает последний символ, потом первый, потом средний, потом все остальные; при несовпадении — сдвиг по Хорспулу.

Достоинства[править | править вики-текст]

Очень быстр в среднем. Прост в реализации. Использует стандартную функцию сравнения участков памяти, как правило, оптимизированную на ассемблерном уровне под конкретный процессор.

Недостатки[править | править вики-текст]

Как и другие алгоритмы семейства Бойера-Мура, не модифицируется на приблизительный поиск, одновременный поиск нескольких строк.

Регрессия на «плохих» данных случается несколько чаще, чем в алгоритме Бойера — Мура. Чем разнообразнее символы в исходном тексте, тем лучше ведёт себя АБМХ.

Литература[править | править вики-текст]

  • Никлаус Вирт Алгоритмы и структуры данных. — М.: Невский Диалект, 2006. С. 352. ISBN 5-7940-0065-1

Примечания[править | править вики-текст]

Ссылки[править | править вики-текст]