Конспект: Бойер-Мур и поиск конечным автоматом

Понятия

Конечный автомат - конечный набор состояний и таблица «состояние и символ → следующее состояние». Для поиска образца состояний m + 1: состояние q значит «совпало q символов образца».

Таблица переходов - d[q][c] равно длине самого длинного начала образца, которым кончается строка «первые q символов образца плюс c».

Плохой символ - символ текста, по которому считается сдвиг окна. В варианте Хорспула это символ под последней позицией окна.

Хороший суффикс - хвост образца, совпавший с текстом до расхождения.

Правило Галила - не перепроверять часть окна, которая гарантированно совпадает после сдвига на период.

Двусторонний алгоритм - поиск с линейной гарантией и постоянной дополнительной памятью; стоит в большинстве стандартных библиотек.

Что унести

АВТОМАТ: построение через префикс-функцию
d[q][c] = q + 1                  если q < m и c = p[q]
d[q][c] = 0                      если q = 0
d[q][c] = d[π[q − 1]][c]         иначе - как после отката, а это уже посчитано

поиск:  q = d[q][c] на каждый символ;  q = m - вхождение
цена:   ровно n обращений, память (m + 1) · k

ХОРСПУЛ
таблица: для символа образца (кроме последней позиции) - расстояние от самого правого
         вхождения до конца образца; для остальных символов - m
окно сравнивается СПРАВА НАЛЕВО; сдвиг - по символу текста под концом окна

kolobok:   k → 6,  o → 1,  l → 4,  b → 2,  остальные → 7

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

ХОРОШИЙ СУФФИКС: сдвиг на наименьшее s ≥ 1, при котором
1) под совпавшим хвостом встали такие же символы образца
2) под местом расхождения встал символ, отличный от не подошедшего   ← сильное правило

abcab:   расхождение в 4, 3, 2, 1, 0  →  сдвиги 1, 5, 3, 3, 3;   после вхождения 3
итоговый сдвиг Бойера-Мура = МАКСИМУМ из двух правил, не сумма

КТО ЧТО ГАРАНТИРУЕТ
автомат              n обращений всегда; единица на КАЖДЫЙ символ; память (m + 1) · k
КМП                  2n сравнений всегда; память m; работает с потоком
Хорспул              от n / m до n · m; память - таблица по алфавиту образца
Бойер-Мур + Галил    от n / m до порядка n; подготовка сложнее всего
двусторонний         порядка n всегда; дополнительной памяти нет

Метод четырёх русских - тот же приём, что у автомата: ответы для всех малых входов считаются заранее. Таблица динамики режется на квадраты со стороной порядка логарифма длины; время падает с квадрата до квадрата, делённого на логарифм.

Ловушки джокера

Таблица без строки для состояния m. После первого же вхождения - IndexError или потерянные перекрытия.

Символ текста, которого нет в таблице. KeyError. Обращаться через get с нулём.

Автомат над огромным алфавитом. Память растёт вместе с k. Хранить только символы образца.

Последняя позиция образца в таблице Хорспула. Её сдвиг - ноль, окно перестаёт двигаться.

Сдвиг по символу расхождения без страховки. В оригинальном правиле он бывает отрицательным; у Хорспула сдвиг всегда не меньше единицы.

Хорспул на двоичных данных. 14 962 сравнения против 13 435 у КМП. Нужен хороший суффикс или другой алгоритм.

Сумма двух сдвигов. Может перескочить вхождение. Берётся больший.

Слабое правило хорошего суффикса. Ответ верный, скорость потеряна.

Все вхождения без правила Галила. Текст и образец из одной буквы - снова n · m.

Бойер-Мур на потоке. Ему нужен буфер длиной с образец: он заглядывает вперёд и ходит по окну назад.

Куда это ведёт

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