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

Алгоритм Бойера-Мура-Хорспула (Boyer-Moore-Horspool, BMH) - упрощённая модификация классического Бойера-Мура, предложенная Найджелом Хорспулом в 1980 году в заметке «Practical fast searching in strings». Хорспул заметил, что для большинства реальных задач полная схема BM с двумя эвристиками избыточна: достаточно одной эвристики «плохого символа», но привязанной не к месту несовпадения, а к символу текста, стоящему под последним символом окна. Получился короткий, кешевой-дружелюбный код, который на естественных текстах работает почти так же быстро, как полный BM, а иногда и быстрее за счёт меньших констант.

Почему понадобилось упрощать BM

Полный алгоритм Бойера-Мура использует две эвристики: «плохой символ» и «хороший суффикс». Каждая требует своей таблицы; good suffix строится нетривиально, через аналог префикс-функции справа налево. На коротких паттернах накладные расходы на вычисление двух сдвигов и взятие максимума съедают выигрыш по числу прочитанных символов.

Хорспул предложил радикальное упрощение. Вместо «на сколько подвинуть, если несовпадение случилось на позиции $j$», задаём вопрос «на сколько подвинуть, исходя из того, какой символ стоит под последней позицией окна». Этот символ известен независимо от того, где именно паттерн рассыпался при сравнении. Хороший суффикс вообще не считается; bad character - всегда по последнему символу окна.

Сама идея - сдвиг по последнему символу окна

Пусть мы прикладываем образец $P$ длины $m$ к тексту $T$ длины $n$ так, что левая граница окна - позиция $i$, правая - позиция $i + m - 1$. Сравниваем символы справа налево. Если все $m$ символов совпали - нашли вхождение. Если на каком-то шаге не совпало - Хорспул смотрит на символ $c = T[i + m - 1]$, тот самый, что стоит под последней позицией окна, и сдвигает окно вправо так, чтобы самое правое строгое вхождение $c$ в $P[0..m-2]$ оказалось выровнено под этим $c$ в тексте.

«Строгое» - потому что само $P[m-1]$ при построении таблицы не учитывается: если бы оно учитывалось, при $c = P[m-1]$ получалось бы $\text{shift}[c] = 0$, и окно не двигалось бы вообще. Если $c$ в $P[0..m-2]$ нет - окно сдвигается сразу на $m$, целиком за пределы текущей позиции.

Построение shift-таблицы

Таблица сдвигов $\text{shift}[\cdot]$ индексируется символами алфавита и заполняется одним проходом по $P[0..m-2]$:

for c in alphabet:
    shift[c] = m
for k in 0..m-2:
    shift[P[k]] = m - 1 - k

То есть для каждого символа, встречающегося в первых $m-1$ позициях паттерна, мы храним расстояние от его последнего вхождения до конца паттерна. Для всех остальных символов - $m$. Время построения - $O(m + \sigma)$, где $\sigma$ - размер алфавита; памяти - $O(\sigma)$.

Пример. Для $P = \text{EXAMPLE}$ ($m = 7$):

Обратите внимание: для буквы $\text{E}$ значение $6$, а не $0$, хотя последнее вхождение $\text{E}$ - это сам $P[6]$. Дело в том, что $P[6]$ при построении мы игнорируем, и берётся вхождение из $P[0] = \text{E}$, дающее $\text{shift}[\text{E}] = 7 - 1 - 0 = 6$.

Основной цикл поиска

i = 0
while i <= n - m:
    j = m - 1
    while j >= 0 and P[j] == T[i + j]:
        j -= 1
    if j < 0:
        report match at i
    i += shift[T[i + m - 1]]

Главное отличие от полного BM: сдвиг считается по символу $T[i + m - 1]$, причём независимо от того, на каком $j$ случилось несовпадение и нашли ли мы вообще вхождение. Никакого взятия максимума с good-suffix - таблица одна, формула одна. Это и есть весь алгоритм.

Пошаговый пример

Поищем $P = \text{EXAMPLE}$ в $T = \text{HERE IS A SIMPLE EXAMPLE}$ ($n = 24$).

Шаг 1. $i = 0$, $T[6] = \text{S}$ против $P[6] = \text{E}$ - несовпадение. $\text{shift}[\text{S}] = 7$, $i = 7$.

Шаг 2. $i = 7$. $T[13] = \text{L}$, $\text{shift}[\text{L}] = 1$. $i = 8$.

Шаг 3. $i = 8$. Совпало $\text{EPLEMS}$ справа налево до $T[10] = \text{I}$ против $P[2] = \text{A}$. $\text{shift}[T[14]] = \text{shift}[\text{E}] = 6$, $i = 14$.

Шаг 4. $i = 14$. $T[14..20] = \text{EXAMPLE}$ - все 7 символов совпадают, найдено вхождение на позиции 14. Двигаем по концу окна: $i = 20$.

Шаг 5. $i = 20$, окно выходит за границу. Конец. Итого четыре сдвига, около 12 сравнений.

Сложность

• Средний случай - $O(n/m)$ для случайного текста на алфавите $\sigma \gg m$: с высокой вероятностью под концом окна стоит символ, которого в $P[0..m-2]$ нет, поэтому средний сдвиг близок к $m$.
• Худший случай - $O(nm)$. Контрпример: $P = \text{aaaab}$, $T = \text{aaaa...aaaa}$ - таблица даёт $\text{shift}[\text{a}] = 1$, окно ползёт по одному символу, и на каждом окне сравнивается весь паттерн.
• Предобработка - $O(m + \sigma)$ время, $O(\sigma)$ память.

В отличие от полного BM, у Хорспула нет простой модификации, дающей гарантированное $O(n)$ - на adversarial-данных его не используют без дополнительных проверок.

Сравнение с BM, KMP и Sunday

• Vs полный Boyer-Moore. BMH имеет ту же асимптотику в среднем, но меньшие константы. На больших алфавитах часто обгоняет полный BM на 10-20%; на малых (ДНК) и adversarial-входах полный BM с good suffix лучше.
• Vs KMP. KMP даёт гарантированное $O(n + m)$, но читает каждый символ текста. BMH в среднем читает $n/m$ символов - быстрее в среднем, но без гарантии в худшем. В потоковом чтении KMP удобнее.
• Vs Sunday (1990). Sunday сдвигает по символу $T[i + m]$ - за пределами окна. Это позволяет двигаться до $m + 1$ за шаг. Чуть быстрее BMH на длинных паттернах, но требует лишнего символа справа.

BMH:    i += shift[T[i + m - 1]]      // символ под концом окна
Sunday: i += shift[T[i + m]]          // символ сразу за окном

Где используется

• редакторы кода и текстовые редакторы (поиск в Vim, Emacs isearch для длинных паттернов);
• антивирусные сканеры - поиск сигнатур вредоносного кода в файлах, скорость на длинных паттернах решает всё;
• реализации String.indexOf в стандартных библиотеках (HotSpot JVM для длинных образцов);
• утилиты вроде grep - как один из fallback-методов наряду с BM и SIMD-ускоренными вариантами.

Типовые учебные задачи

1. Построить shift-таблицу для заданного $P$ и объяснить, почему последний символ паттерна не учитывается.
2. Прогнать поиск пошагово, указав сравнения, сдвиги и число операций.
3. Построить $P$ и $T$, на которых BMH деградирует до $O(nm)$.
4. Сравнить число сравнений для одного и того же $(P, T)$ алгоритмами BMH, BM, KMP и наивным.

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

• Учитывают $P[m-1]$ при построении shift. Тогда $\text{shift}[P[m-1]] = 0$, окно зависает, поиск зацикливается.
• Берут сдвиг по символу несовпадения, как в полном BM. В BMH сдвиг - всегда по $T[i + m - 1]$, под концом окна.
• Не сдвигают окно после успешного матча. В BMH после вхождения тоже двигаются по таблице - на $\text{shift}[T[i + m - 1]]$.
• Хранят таблицу как hash-map на больших алфавитах. Для ASCII массив на 256 элементов быстрее любого hash-доступа.
• Удивляются, что BMH медленнее BM в худшем случае. У Хорспула слабее эвристика; если нужна гарантия - используйте полный BM с модификацией Galil или KMP.

FAQ

В чём принципиальное отличие BMH от полного Бойера-Мура? В BMH нет эвристики хорошего суффикса, а bad character упрощён: сдвиг считается всегда по символу $T[i + m - 1]$ под концом окна, а не по позиции несовпадения. Одна таблица размером $O(\sigma)$ вместо двух, более короткий код и в большинстве задач - та же или лучшая скорость, чем у полного BM, за счёт меньших констант.

Когда Horspool явно проигрывает? На коротком алфавите (ДНК, бинарные данные) - там полный BM с good suffix или KMP лучше. На adversarial-данных BMH деградирует до $O(nm)$, а KMP остаётся $O(n + m)$.

Чем Horspool отличается от Sunday? Sunday (1990) сдвигает окно по символу $T[i + m]$ - за окном, а не под его концом. Это позволяет двигаться до $m + 1$ за шаг и даёт 5-15% выигрыша на длинных паттернах, но требует лишнего символа справа от окна.

Коротко

Алгоритм Бойера-Мура-Хорспула - полный Бойер-Мур, упрощённый до одной таблицы сдвигов по последнему символу окна. $\text{shift}[c] = m - 1 - k$, где $k$ - позиция самого правого вхождения $c$ в $P[0..m-2]$, или $m$, если вхождения нет. Среднее время - $O(n/m)$, худший случай - $O(nm)$, предобработка - $O(m + \sigma)$. Несмотря на отсутствие гарантии линейности, BMH часто быстрее полного BM на естественных текстах за счёт меньших констант и стоит в основе поиска в редакторах, антивирусных сканерах и многих библиотечных indexOf.