Алгоритм Бойера-Мура: почему он ищет подстроку так быстро

Алгоритм Бойера-Мура (Boyer-Moore, 1977) - один из самых быстрых способов искать подстроку длины $m$ в тексте длины $n$ на практике. Наивный поиск делает $O(nm)$ сравнений, алгоритм Кнута-Морриса-Пратта даёт гарантированные $O(n+m)$, а Бойер-Мур в лучшем случае работает сублинейно - за $O(n/m)$, то есть просматривает не весь текст, а только каждую $m$-ю позицию. Именно поэтому он лежит в основе grep, поиска в текстовых редакторах и многих реализаций String.indexOf.

Главная идея - сравнение справа налево

В наивном алгоритме паттерн прикладывают к тексту слева и сравнивают символы по порядку. У Бойера-Мура всё наоборот: паттерн прикладывают к тексту, но сравнивают справа налево. Если последний символ паттерна не совпал с текстом - мы уже за одно сравнение получили полезную информацию о куске текста длины $m$ и можем сдвинуть паттерн больше чем на 1.

Это и есть весь трюк. Все остальные детали - про то, на сколько именно можно сдвинуть. Алгоритм использует две эвристики, для каждого несовпадения считает сдвиг по обеим и берёт максимум.

Эвристика плохого символа (bad character)

Пусть мы сравнили символы справа налево и упёрлись в несовпадение: на позиции $i$ в тексте стоит символ $c$, а в паттерне на той же позиции - что-то другое. Смотрим, где символ $c$ встречается в самом паттерне:

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

Формально сдвиг по плохому символу равен

$\Delta_{\text{bc}} = \max\bigl(1,\ j - \text{last}[c]\bigr),$

где $j$ - текущая позиция несовпадения в паттерне, а $\text{last}[c]$ - позиция самого правого вхождения $c$ в паттерн (или $-1$, если такого нет). Таблица $\text{last}[\cdot]$ строится за $O(m + \sigma)$, где $\sigma$ - размер алфавита.

Эвристика хорошего суффикса (good suffix)

Плохой символ хорошо работает на больших алфавитах (текст на естественном языке), но плохо - на коротких (ДНК с алфавитом $\{A, C, G, T\}$). Поэтому добавляют вторую эвристику.

Если до несовпадения мы уже успели сопоставить непустой суффикс паттерна с текстом, мы знаем не только «плохой» символ, но и кусок текста после него. Идея: найти другое вхождение этого суффикса внутри паттерна или, если его нет, найти максимальный префикс паттерна, совпадающий с собственным суффиксом. Дальше двигаем паттерн так, чтобы это вхождение встало на место уже совпавшего хвоста.

Два случая:

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

Таблица сдвигов по хорошему суффиксу тоже предвычисляется за $O(m)$ - стандартная техника близка к построению префикс-функции, но обходим паттерн справа.

Объединение эвристик

На каждом несовпадении считаем оба сдвига и выбираем больший:

$\Delta = \max\bigl(\Delta_{\text{bc}},\ \Delta_{\text{gs}}\bigr).$

Это даёт корректный сдвиг: каждая эвристика сама по себе никогда не пропустит совпадение, поэтому и максимум - тоже безопасный. Обе таблицы строятся один раз перед началом поиска за $O(m + \sigma)$. После этого основной цикл стоит:

i = 0
while i <= n - m:
    j = m - 1
    while j >= 0 and pattern[j] == text[i + j]:
        j -= 1
    if j < 0:
        report match at i
        i += shift_good_suffix[0]
    else:
        i += max(shift_bad_char(text[i + j], j),
                 shift_good_suffix[j])

Подробный пример

Поищем паттерн $P = \text{ABCDABD}$ ($m = 7$) в тексте $T = \text{ABAAABCDABDEFG}$ ($n = 14$).

Таблица плохого символа (позиция самого правого вхождения каждого символа в $P$):

Шаг 1. $i = 0$, прикладываем паттерн к началу: $T[0..6] = \text{ABAAABC}$ против $P = \text{ABCDABD}$. Сравниваем справа: $P[6] = \text{D}$, $T[6] = \text{C}$ - несовпадение на $j = 6$.

• Плохой символ: $\text{C}$ в паттерне на позиции $2$, сдвиг $\Delta_{\text{bc}} = 6 - 2 = 4$.
• Хороший суффикс: суффикс длины 0 - берём дефолтный сдвиг 1.

Выбираем максимум: $\Delta = 4$. Двигаем паттерн на 4.

Шаг 2. $i = 4$, сравниваем $T[4..10] = \text{ABCDABD}$ против $P = \text{ABCDABD}$. Все 7 символов совпадают справа налево - найдено вхождение на позиции 4. Сдвигаем дальше (на $m = 7$ или по таблице хорошего суффикса, обычно 1-2 позиции).

Шаг 3. $i = 5$. Сравниваем $T[5..11] = \text{BCDABDE}$ против $P = \text{ABCDABD}$. $P[6] = \text{D}$, $T[11] = \text{E}$ - символа $\text{E}$ в паттерне нет, сдвигаем на полный $m = 7$.

После этого $i = 12 > n - m = 7$, цикл заканчивается. Итого: одно вхождение, три сравнения групп символов на 14-символьном тексте - наивный алгоритм сделал бы около $14 \cdot 7 \approx 98$ сравнений.

Сложность по среднему и худшему случаям

• Лучший случай - $O(n/m)$. Достигается, когда плохой символ часто не встречается в паттерне и мы сдвигаемся на $m$ за раз. На английском тексте с паттерном длины 10-20 это типичное поведение.
• Средний случай на естественных текстах эмпирически близок к $O(n/m)$, что подтверждено многочисленными бенчмарками grep.
• Худший случай - $O(nm)$. Возникает, когда паттерн и текст устроены так, что обе эвристики дают сдвиг 1 (классический пример: паттерн $\text{aaab}$ в тексте $\text{aaaaaaab}$). Без модификаций алгоритм здесь не лучше наивного.
• Модификация Galil (1979) добавляет правило перехода после успешного совпадения: запоминается уже сопоставленный префикс, чтобы не сравнивать его повторно. Это даёт гарантированную оценку $O(n)$ при сохранении быстрого среднего случая.

Для сравнения: КМП всегда $O(n + m)$, но без сублинейного выигрыша - он смотрит каждый символ текста, тогда как Бойер-Мур многие символы вообще не читает.

Где используется в реальной жизни

• GNU grep и git grep - основной поиск построен на Бойере-Муре с эвристикой плохого символа, для коротких паттернов добавляется SIMD-ускорение. Именно благодаря этому grep обгоняет find -name | xargs cat | match на порядок.
• Текстовые редакторы - поиск в Vim (/pattern), Emacs (isearch), VS Code, Sublime Text для длинных паттернов использует Бойера-Мура или его упрощённые варианты.
• String.indexOf в некоторых JVM (HotSpot для длинных паттернов), memmem в glibc, Boost.Algorithm - стандартные библиотечные реализации.
• Boyer-Moore-Horspool (1980) - упрощённая версия только с эвристикой плохого символа и сдвигом, ориентированным на крайний правый символ паттерна. Проще кодировать, чуть медленнее в худшем случае, но быстрее на практике для коротких паттернов. Используется, например, в полнотекстовом поиске SQL Server и во многих антивирусных сканерах.
• Биоинформатика - поиск мотивов в геноме, хотя на алфавите $\{A, C, G, T\}$ выигрыш по сравнению с КМП меньше, и часто предпочитают индексные структуры (суффиксные массивы, FM-индекс).

Частые ошибки

• Сравнивают слева направо. Тогда вся идея ломается - эвристика плохого символа теряет смысл, потому что мы не знаем «хвост» текста.
• Забывают $\max(1, \dots)$ в формуле сдвига. Если $\text{last}[c] > j$, разность отрицательная - без отсечения снизу алгоритм будет двигаться назад и зацикливаться.
• Считают, что Бойер-Мур всегда быстрее КМП. Не всегда: на алфавите из 2-4 символов и при паттерне с большим самоналожением КМП может выиграть, особенно с учётом меньших констант.
• Используют только bad character и удивляются худшему случаю $O(nm)$. Это и есть Horspool - да, он медленнее в патологических случаях; если нужна гарантия - берите полный Бойер-Мур с модификацией Galil.
• Пишут таблицу плохого символа по всему Юникоду. При $\sigma = 10^6$ предобработка дороже самого поиска. Реализации хранят таблицу в виде хеш-таблицы или ограничиваются ASCII с fallback.

FAQ

Чем алгоритм Бойера-Мура отличается от КМП? КМП сравнивает символы слева направо и использует префикс-функцию, чтобы при несовпадении не возвращаться по тексту - гарантированно $O(n+m)$. Бойер-Мур сравнивает справа налево и за счёт эвристик пропускает целые блоки текста - в среднем $O(n/m)$, но без модификации Galil - $O(nm)$ в худшем. На больших алфавитах Бойер-Мур обычно быстрее, на малых - КМП.

Что такое Boyer-Moore-Horspool и когда брать его вместо полного? Horspool - упрощённый вариант, где остался только сдвиг по плохому символу, причём выровнённый по самому правому символу паттерна. Кодируется в 15 строк, быстрее полного на коротких паттернах из-за меньших констант. Берите его, когда нужна простая реализация и не страшен теоретический $O(nm)$ - на реальных текстах он почти не встречается.

Почему Бойер-Мур может быть быстрее линейного алгоритма? Потому что «линейный» - это $O(n)$ по числу прочитанных символов текста, а Бойер-Мур многие символы вообще не читает. На самом деле для гарантированного нижнего предела $\Omega(n/m)$ сравнений теоремы существуют, и Бойер-Мур с правильными эвристиками этот предел достигает.

Коротко

Алгоритм Бойера-Мура ищет подстроку длины $m$ в тексте длины $n$, сравнивая паттерн справа налево и сдвигая его на большие шаги по двум эвристикам - плохого символа и хорошего суффикса. Таблицы строятся за $O(m + \sigma)$, основной цикл - $O(n/m)$ в лучшем случае, $O(nm)$ в худшем (модификация Galil даёт гарантированное $O(n)$). Стоит в основе grep, поиска в редакторах и многих библиотечных реализаций indexOf. Упрощённый вариант - Boyer-Moore-Horspool с одной эвристикой плохого символа.