Бойер — Мур

В августе 2010 года в рассылке FreeBSD спорили, почему BSD grep медленнее GNU grep. В спор вмешался Майк Хертел, первый автор GNU grep, и объяснил главный приём заглавными буквами: GNU grep быстр, потому что не смотрит на каждый байт входа. Он ищет алгоритмом Бойера — Мура: сначала смотрит на последнюю букву образца и по таблице решает, на сколько можно прыгнуть вперёд. Ниже этот алгоритм ищет имя или фразу в первой части «Войны и мира». Точки над буквами — те, на которые он вообще посмотрел.

«Князь Андрей» в первой части встречается 57 раз. Наивный поиск, который прикладывает образец к каждой позиции, сделал 252 256 сравнений — больше, чем знаков в тексте. Бойер — Мур сделал 27 550: одно сравнение на девять знаков. Шесть прыжков из десяти — на всю длину образца, двенадцать знаков: под последней клеткой окна оказалась буква, которой в «князь Андрей» нет вовсе. Переключите на фразу «Ну, здравствуйте, здравствуйте» из тридцати знаков: сравнений 12 784, одно на девятнадцать знаков. А на «Пьер» из четырёх букв выигрыш скромнее — в 3,6 раза. Посмотрите и на полосу внизу — это вся первая часть: серые столбики — сколько сравнений на букву делает наивный поиск, цветные — выбранный алгоритм. У наивного они доходят до пунктира «одно сравнение на букву» — на каждую букву хотя бы одно, — у Бойера — Мура они в разы ниже, и чем длиннее образец, тем ниже.

Идея

Прикладываем образец к тексту, но сравниваем с правого конца окна. Если буква текста под последней клеткой вообще не встречается в образце, ни одно окно, которое накрывает эту букву, не может совпасть, и образец перепрыгивает её целиком — сразу на m позиций. Если встречается, образец сдвигается так, чтобы под этой буквой встала её ближайшая копия в образце. Сравнения справа налево дают больше знаний о тексте до первой ошибки, а таблицы, построенные заранее по одному образцу, превращают эти знания в длинные прыжки.

Наивный поиск сдвигает образец на одну позицию, что бы ни случилось. Бойер и Мур заметили, что после несовпадения о тексте известно многое, и сдвиг можно вычислить. Чем длиннее образец, тем дальше прыжок: длинный образец ищется быстрее короткого. Это главное, что отличает алгоритм от КМП, который читает каждую букву текста ровно один раз.

Два правила сдвига

Пусть окно сравнивалось справа налево, последние буквы совпали, а на позиции j образца буква текста c не совпала с p[j]. Алгоритм считает два сдвига и берёт больший.

Правило плохой буквы: сдвинуть образец так, чтобы под буквой c встала её самая правая копия в образце (последняя клетка не в счёт). Если c в образце нет, образец перепрыгивает её целиком. Если же самая правая копия стоит правее места несовпадения, правило предлагает сдвиг назад и не годится — тогда решает второе правило. Таблица для этого правила — последнее вхождение каждой буквы алфавита в образец — строится за O(m + σ), где σ — размер алфавита.

Правило хорошего суффикса: совпавший конец образца u — это то, что мы точно знаем о тексте. Сдвинуть образец до ближайшей копии u внутри образца, перед которой стоит другая буква, не p[j]: та же буква перед копией дала бы то же несовпадение. Если такой копии нет, сдвинуть так, чтобы с хвостом u совпало самое длинное начало образца.

Ниже пример из статьи Бойера и Мура 1977 года: образец AT-THAT в строке WHICH-FINALLY-HALTS.--AT-THAT-POINT. На каждом несовпадении сцена рисует оба кандидата: оранжевым — какую букву образца правило плохой буквы ставит под букву текста, синим — где правило хорошего суффикса находит копию совпавшего конца.

Первые три окна решает плохая буква. Под последней клеткой первого окна F — её в образце нет, прыжок на всю длину, 7. Во втором окне «-», которая стоит в образце за четыре буквы до конца: сдвиг 4. В третьем совпала T, а L в образце нет — образец перепрыгивает её, сдвиг 6. В четвёртом окне совпало «AT», а перед ним в тексте «-» вместо H. Плохая буква дала бы только 2: ближайшая «-» в образце совсем рядом. Хороший суффикс даёт 5: «AT» стоит в начале образца, и образец встаёт так, чтобы начало легло на совпавшее «AT». Пятое окно — вхождение. Всего 15 сравнений, у наивного поиска на той же строке — 40.

Переключите на ДНК. В алфавите из четырёх букв почти любая буква текста есть в образце, и плохая буква даёт короткие сдвиги: 1 и 4. В последнем окне совпала одна G, а перед ней в тексте C: плохая буква дала бы 5, хороший суффикс даёт 7: остальные G в образце стоят после той же A, что не совпала, и годится только G в самом начале образца. А на «aaaa…» каждое окно — вхождение, сдвиг всегда 1, и алгоритм сравнивает каждое окно целиком: 52 сравнения. Поставьте галочку «правило Галила» — их станет 16; о нём ниже.

Хорспул: одна таблица

В 1980 году Найджел Хорспул предложил упрощение, которое и стало рабочей лошадкой. Хорошего суффикса нет. Плохая буква берётся всегда одна и та же — буква текста под последней клеткой окна, где бы ни случилось несовпадение. Окно сдвигается так, чтобы под этой буквой встала её самая правая копия среди первых m − 1 букв образца; если копии нет — на m. Таблица одна, сдвиг всегда положительный, код — десяток строк.

На прозе Хорспул почти не уступает полному алгоритму. В первой части романа для «Пьер» и «князь Андрей» оба делают ровно одинаковое число сравнений, для фразы из тридцати знаков разница меньше 5 %. Хороший суффикс срабатывает, только когда совпал длинный конец образца, а в прозе первая же буква справа обычно не совпадает. На ДНК картина другая: на образце из 32 букв Хорспул делает 28 123 сравнения на 100 000 букв, полный Бойер — Мур — 15 675.

Почему сдвиги ничего не пропускают

Таблицу хорошего суффикса удобно строить через Z-функцию. Нужно знать, какой длины общий конец у каждого начала образца и всего образца, — это Z-функция перевёрнутого образца, прочитанная задом наперёд. Так её выводит Дэн Гасфилд в своей книге, и так она построена в листинге ниже.

Код

Таблица плохой буквы — словарь «буква → сдвиг» в Python и map в Go; буквы, которых нет в образце, получают сдвиг m. Обе функции поиска заодно считают сравнения, а в конце — пример 1977 года по шагам и таблица на случайных текстах.

Последняя таблица вывода — короткий справочник по поведению алгоритма. На случайном тексте из 26 букв образец из восьми букв ищется за 14 899 сравнений на 100 000 букв, из 32 букв — за 5148: длиннее образец — быстрее поиск. На случайной ДНК при тех же длинах 47 859 и 15 675. И две строки про текст из одних «a», о них ниже.

Теперь на настоящем тексте. Программа ищет пять образцов в первой части романа — сначала по буквам, потом, в последнем столбце, по байтам UTF-8, как ищет grep:

По байтам выходит хуже. «Пьер» по буквам — 67 545 сравнений, по байтам — 77 197. В UTF-8 каждая русская буква — два байта, и первый из них у всех строчных и прописных букв почти одинаков: D0 или D1. Образец в байтах вдвое длиннее, но под последней клеткой окна часто оказывается байт, который есть в образце много раз, и прыжки короче.

Сколько это стоит

Подготовка — O(m + σ): таблица плохой буквы на весь алфавит и таблица хорошего суффикса за O(m). Память та же. Дальше всё зависит от текста.

В среднем — меньше одного сравнения на букву. Если алфавит большой, а образец в тексте встречается редко, буква под последней клеткой окна чаще всего в образце не стоит или стоит далеко от конца, и окно прыгает почти на m. Окон тогда порядка n/m, и в каждом обычно одно-два сравнения. Это и называют сублинейностью: время меньше длины текста, и тем меньше, чем длиннее образец. Сравните четыре текста — русскую прозу по буквам и по байтам, английскую прозу и ДНК:

При образце в 16 знаков Хорспул делает на русской прозе 0,1 сравнения на букву, на английской — 0,11, на тех же русских буквах в байтах — 0,15. На ДНК — 0,34, и дальше линия почти не опускается: в алфавите из четырёх букв последняя буква окна почти всегда стоит где-то в конце образца, и прыжки короткие, сколько ни удлиняй образец. Переключите на полный Бойер — Мур: хороший суффикс вытягивает ДНК до 0,2 на образце в 64 буквы. Наивный поиск на всех четырёх текстах делает чуть больше одного сравнения на знак.

Время на той же первой части романа: наивный поиск, Хорспул и встроенный поиск языка, образец — кусок самого текста длины m.

Наивный поиск занимает одно и то же время при любой длине образца, а Хорспул с каждым удвоением образца ускоряется почти вдвое: на Python от образца в 2 знака до образца в 64 время упало в 21 раз. При двух знаках Хорспул медленнее наивного: прыжки короткие, а на каждое окно уходит лишний поиск в таблице. Встроенный поиск Python быстрее обоих: он написан на C и сам устроен как смесь Бойера — Мура и Хорспула. Встроенный поиск Go на длинных образцах, наоборот, проигрывает Хорспулу — почему, рассказано в статье о наивном поиске.

Худший случай. Хорспул на тексте из одних «a» с образцом «b» и семью «a» в каждом окне сравнивает все восемь букв, спотыкается на «b» и сдвигается на одну позицию: под последней клеткой снова «a». В выводе листинга это 799 944 сравнения на 100 000 букв — в восемь раз больше, чем у наивного поиска, который начинает сравнение с «b». Полный Бойер — Мур здесь линеен: хороший суффикс видит, что «aaaaaaa» перед «b» в образце нигде больше не стоит, и прыгает на 8.

Но и у полного алгоритма есть слабое место — много вхождений. Образец из восьми «a» в тексте из одних «a» встречается почти в каждой позиции. После вхождения образец сдвигается на свой период, на одну букву, и следующее окно снова сравнивается целиком: опять 799 944 сравнения. Цви Галил в 1979 году предложил помнить, что после сдвига на период первые m − период букв окна уже совпали, и не сравнивать их снова. С правилом Галила — ровно 100 000 сравнений, по одному на букву.

Что на самом деле стоит в grep и memmem

Учебная версия с двумя таблицами в чистом виде почти нигде не работает. В программах стоят её потомки, и каждый подогнан под процессор.

GNU grep. В версии 3.12 (2025) одну фиксированную строку ищет файл src/kwset.c, который Майк Хертел написал в августе 1989 года. Комментарий в коде прямо говорит: Бойер — Мур, если образец один, Ахо — Корасик, если их несколько. Таблица плохой буквы смотрит, как у Хорспула, на последний байт окна, и цикл прыжков развёрнут: окно прыгает несколько раз подряд, пока под последней клеткой не окажется последний байт образца. Когда прыжки выходят короткими, grep переключается на поиск этого байта функциями вроде memchr, которые проверяют сразу целое машинное слово. После совпадения последних байтов в ход идёт таблица хорошего суффикса. Для регулярного выражения grep выделяет строки, которые обязаны встретиться в любом совпадении, и ищет сначала их тем же кодом, а простой образец без спецсимволов сразу переводит в режим -F. В документации grep так и написано: где возможно, для одной фиксированной строки используется Бойер — Мур, для нескольких — Ахо — Корасик.

glibc. В стандартной библиотеке C для Linux, версия 2.44 (2026), memmem и strstr устроены так. Образцы из одного-двух байтов (в strstr — до трёх) ищутся отдельным простым циклом. Образцы до 256 байт — «новым модифицированным алгоритмом Хорспула», как сказано в исходнике: таблица сдвигов строится не по одной букве, а по паре соседних байтов, свёрнутой хешем в номер ячейки, и главный цикл останавливается, только когда пара байтов на конце окна совпала с концом образца по хешу. Ограничение в 256 байт держит каждый сдвиг в одном байте, а таблицу — в 256 байтах, и заодно гарантирует линейное время. Образцы длиннее ищет двусторонний алгоритм Крошмора — Перрена. Этот вариант Хорспула написал в 2019 году Уилко Дейкстра. На x86-64 strstr сначала пробует свою векторную версию на SSE2, и та в части случаев передаёт работу этой общей функции.

Другие языки. Python в str.find для коротких образцов использует, по словам исходников, смесь Бойера — Мура и Хорспула, а для длинных — тот же двусторонний алгоритм; подробности — в статье о наивном поиске. В C++ начиная с C++17 в std::search можно передать std::boyer_moore_searcher или std::boyer_moore_horspool_searcher. В Go strings.Index Бойера — Мура не использует, зато внутри пакета strings он есть: им ищет strings.NewReplacer, когда заменяемая строка одна и длиннее одного байта.

Где он слабее

• Маленький алфавит. На ДНК почти каждая буква текста стоит в образце, и плохая буква даёт короткие сдвиги. Для ДНК и двоичных данных лучше подходят алгоритмы, которые смотрят на несколько букв сразу, как glibc на пары байтов, или на целые машинные слова.
• Короткие образцы. При m = 2–3 прыгать почти некуда, и выигрывает простой цикл с векторной проверкой первой буквы — так и делают библиотеки.
• Поток. Бойеру — Муру нужно окно текста целиком, а в потоке, где буквы приходят по одной и назад дороги нет, работает КМП.
• Образцы с «любой буквой». Таблицы выводят из равенства букв равенство других букв, и подстановочные знаки ломают их. Здесь проще наивный поиск или автомат.

История

Роберт Бойер и Джей Стротер Мур, по воспоминаниям Мура, придумали алгоритм около 1975 года. Статья «A fast string searching algorithm» вышла в Communications of the ACM в октябре 1977-го. В том же году Кнут, Моррис и Пратт в своей статье о КМП разобрали и алгоритм Бойера — Мура и доказали его линейность для случая, когда образца в тексте нет. Цви Галил в 1979 году сделал алгоритм линейным всегда, Найджел Хорспул в 1980-м упростил его до одной таблицы, а Ричард Коул в 1991-м нашёл точную оценку числа сравнений. Файл с Бойером — Муром в GNU grep написан в 1989 году; с тех пор его переписывали много раз, но идея осталась прежней: не смотреть на каждый байт.

Задачи

В первой задаче надо честно посчитать, сколько работы Хорспул делает на настоящих текстах, — и не ошибиться в таблице. Во второй — построить таблицу хорошего суффикса для образца в сто тысяч знаков за линейное время.