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

Алгоритм Бойера — Мура — это алгоритм поиска подстроки (образца) в строке, разработанный Робертом Бойером и Джеем Муром в 1977 году. Относится к классу суб-линейных алгоритмов, так как в среднем случае позволяет находить образец, не просматривая каждый символ текста. Алгоритм основан на двух эвристиках: эвристике «стоп-символа» и эвристике «совпавшего суффикса», которые позволяют сдвигать образец на большее количество позиций, чем один символ, при несовпадении.

¶История

Алгоритм был опубликован Робертом Бойером и Джеем Муром в статье «A Fast String Searching Algorithm» в журнале Communications of the ACM в 1977 году. Он стал одним из первых алгоритмов поиска, демонстрирующих эффективность на практике, особенно для больших алфавитов (например, для текстов на естественных языках). До появления алгоритма Бойера — Мура доминировал наивный алгоритм, который в худшем случае требовал O(nm) операций, где n — длина текста, m — длина образца. Алгоритм Бойера — Мура в худшем случае имеет сложность O(nm), но на практике, особенно при поиске в длинных текстах, его средняя сложность близка к O(n/m).

¶Принцип работы

Алгоритм просматривает текст слева направо, но сравнение символов образца с текстом производится справа налево (от последнего символа образца к первому). При обнаружении несовпадения алгоритм использует одну из двух эвристик для вычисления величины сдвига образца вправо. Выбирается максимальное значение сдвига из двух эвристик.

¶Эвристика стоп-символа

Эвристика стоп-символа (или эвристика плохого символа) основана на символе текста, который вызвал несовпадение (стоп-символ). Если стоп-символ не встречается в образце, образец можно сдвинуть полностью за этот символ (на m позиций). Если стоп-символ встречается в образце, образец сдвигается так, чтобы последнее вхождение этого символа в образце совпало со стоп-символом в тексте.

Для реализации этой эвристики предварительно строится таблица смещений для каждого символа алфавита. Значение смещения для символа c вычисляется как:

• Если c не входит в образец: смещение = m.
• Если c входит в образец: смещение = m - 1 - index, где index — индекс последнего вхождения c в образце (индексация от 0).

¶Эвристика совпавшего суффикса

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

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

¶Сложность

• Худший случай: O(n*m) — например, при поиске образца «aaaaa» в тексте «aaaaab». В этом случае обе эвристики дают сдвиг на 1, и алгоритм работает как наивный.
• Средний случай: O(n/m) — для случайных текстов и образцов, особенно при большом алфавите. Это делает алгоритм одним из самых быстрых на практике.
• Предварительная обработка: O(m + |Σ|), где |Σ| — размер алфавита. Время построения таблиц смещений.

¶Пример работы

Рассмотрим поиск образца «EXAMPLE» в тексте «HERE IS A SIMPLE EXAMPLE».

1. Образец выравнивается по началу текста. Сравнение начинается с последнего символа образца (E) и символа текста (R). Несовпадение. Стоп-символ — R. R не входит в образец, сдвиг по стоп-символу = 7 (длина образца). Сдвиг по совпавшему суффиксу = 0 (нет совпавшего суффикса). Сдвиг = 7.
2. Образец сдвигается на 7 позиций. Сравнение последнего символа образца (E) с символом текста (S). Несовпадение. Стоп-символ — S. S не входит в образец, сдвиг = 7.
3. Образец сдвигается ещё на 7. Сравнение последнего символа (E) с символом текста (P). Несовпадение. Стоп-символ — P. P входит в образец на позиции 5 (индекс 5, если считать с 0). Сдвиг по стоп-символу = 7 - 1 - 5 = 1. Сдвиг = 1.
4. Образец сдвигается на 1. Сравнение: символы совпадают (E с E, L с L, P с P, M с M, A с A, X с X, E с E). Образец найден.

¶Применение

Алгоритм Бойера — Мура широко применяется в программном обеспечении, где требуется быстрый поиск подстрок:

• Текстовые редакторы: функция «Найти и заменить».
• Поисковые системы: поиск по индексу.
• Антивирусное программное обеспечение: поиск сигнатур вирусов.
• Сетевые системы: фильтрация пакетов, поиск шаблонов в трафике.
• Биоинформатика: поиск последовательностей ДНК и белков.

¶Модификации

Существует несколько модификаций алгоритма, направленных на улучшение его производительности или адаптацию к специфическим условиям:

• Алгоритм Бойера — Мура — Хорспула: упрощённая версия, использующая только эвристику стоп-символа. Обычно быстрее для коротких образцов и малых алфавитов.
• Алгоритм Бойера — Мура — Санди: модификация, улучшающая производительность на некоторых типах данных.
• Алгоритм Зондерса: использует только эвристику совпавшего суффикса.

¶Сравнение с другими алгоритмами

• Наивный алгоритм: O(n*m) в худшем случае, на практике медленнее.
• Алгоритм Кнута — Морриса — Пратта (КМП): O(n+m) в худшем случае, но на практике часто медленнее Бойера — Мура, особенно для больших алфавитов.
• Алгоритм Рабина — Карпа: O(n+m) в среднем, O(n*m) в худшем. Использует хеширование. Эффективен для поиска нескольких образцов одновременно.

¶Интересные факты

• Алгоритм был назван одним из «десяти алгоритмов, оказавших наибольшее влияние на развитие науки и техники XX века» по версии журнала Computing in Science & Engineering.
• В оригинальной статье Бойера и Мура эвристика стоп-символа была описана как «эвристика плохого символа», а эвристика совпавшего суффикса — как «эвристика хорошего суффикса».
• Алгоритм является основой для многих современных библиотек поиска строк, включая реализацию в стандартной библиотеке языка C++ (функция std::search с использованием алгоритма Бойера — Мура в некоторых реализациях).

¶Источники

• Boyer, R. S., & Moore, J. S. (1977). A fast string searching algorithm. Communications of the ACM, 20(10), 762–772.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Knuth, D. E., Morris, J. H., & Pratt, V. R. (1977). Fast pattern matching in strings. SIAM Journal on Computing, 6(2), 323–350.