Алгоритм Бойера-Мура

Информация, которая может быть получена при неудачном сравнении образца с частью текста может носить различный характер. Иногда использование комбинации, полученной анализом различных признаков, дает хороший эффект. Показательным в этом отношении является алгоритм Бойера-Мура. В этом алгоритме поиск образца в тексте идет слева направо, но сравнение с образцом делается в обратную сторону, справа налево. Как и в описанных ранее алгоритмах поиска по образцу центральным вопросом является вычисление величины допустимого максимального сдвига образца по тексту в случае неудачного завершения поиска в предыдущей позиции. Вся информация, которую алгоритм может почерпнуть из предыдущего сравнения, заключается в двух компонентах:

• в знании совпадающей части текста и образца, которая является некоторым суффиксом образца;
• в символе, который характеризует первое разночтение образца и текста.

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

Выделим первый символ в тексте, в котором наблюдается несовпадение образца с частью текста. Этот символ называется стоп-символом. После неудачного завершения поиска определяется самое правое вхождение стоп-символа в образец и сдвиг образца вправо производится таким образом, что чтобы стоп-символ текста совпал с найденным символом в образце. Если стоп-символ не присутствует в образце, то сдвиг производится на длину образца. Но такой подход неприемлем, если стоп-символ в образце встречается правее стоп-символа в тексте (стоит в совпадающей части образца и текста). В этом случае мы получаем величину отрицательного сдвига (сдвиг образца по тексту влево): этот случай игнорируется алгоритмом, а величина сдвига определяется из других соображений. Заметим, что для каждого символа алфавита самое правое вхождение этого символа в образец можно вычислить один раз на предварительной стадии алгоритма и сохранить в некотором массиве.

Другую информацию, которую можно использовать при определении величины сдвига, составляет совпадающая часть образца с текстом, которая представляет некоторый суффикс образца. Этот суффикс называется безопасным суффиксом. Если найти следующее вхождение безопасного суффикса справа-налево в образце, то при следующей итерации можно сдвинуть образец вправо на соответствующее число позиций, чтобы найденное вхождение безопасного суффикса в образце совпала с соответствующей частью текста. Ниже приводится иллюстрация примера для задачи поиска образца «аbaacbba» в некотором тексте

Для данного примера по стоп-символу алгоритм предлагает сдвинуть образец на 1 позицию, а по безопасному суффиксу на пять. Алгоритм, сравнивая значение двух показателей, выбирает вариант, дающий максимальное значение сдвига. Мы не будем подробно разбирать этот алгоритм, но заметим, что сложность алгоритма в худшем случае составляет , где - мощность алфавита. Однако на практике в среднем именно этот алгоритм является наиболее эффективным по сравнению с алгоритмом Рабина-Карпа[4].

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