Поиск автоматом: одно обращение к таблице на символ

Если ты построишь таблицу переходов для aab, объяснишь, чем автомат отличается от КМП по цене одного символа, и скажешь, когда таблица не помещается в память, - листай до «Теперь сам».

Как думаешь, сколько может стоить один символ

КМП гарантирует 2n сравнений на весь текст. Про отдельный символ он не гарантирует ничего. Образец - девять букв a и буква b. В тексте совпало девять a, и приходит символ c.

Прежде чем читать дальше, посчитай, сколько сравнений потратит КМП на этот один символ. А теперь представь устройство, которое разбирает сетевой поток и обязано тратить на каждый байт одинаковое время. Можно ли сделать поиск, в котором любой символ стоит ровно одно действие?

На что это похоже

Представь настольную игру-ходилку. Фишка стоит на клетке с номером. На каждой клетке напечатана табличка: «выпала a - иди на клетку 3, выпала b - иди на клетку 0». Ты не рассуждаешь и ничего не сравниваешь: читаешь букву, смотришь в табличку, переставляешь фишку.

Вся сообразительность потрачена заранее - тем, кто печатал таблички. Игроку остаётся одно движение на ход, всегда одно. Номер клетки - единственное, что надо помнить о всей прошлой игре.

Механизм: состояния и таблица переходов

Конечный автомат - это конечный набор состояний, одно из которых начальное, и таблица переходов: для каждой пары «состояние и символ» записано следующее состояние. Больше у автомата ничего нет: ни памяти о прошлом, ни счётчиков.

Для поиска образца состояний m + 1, и у каждого прямой смысл: состояние q означает «последние q прочитанных символов текста - это первые q символов образца, и больше совпасть не могло». Состояние m означает вхождение.

Образец abab, алфавит из двух букв:

состояние    что совпало         по a    по b
    0        ничего                1       0
    1        a                     1       2
    2        ab                    3       0
    3        aba                   1       4
    4        abab - вхождение      3       0

Прогон текста abaababab. Под каждым символом - состояние после него:

текст        a  b  a  a  b  a  b  a  b
состояние    1  2  3  1  2  3  4  3  4
                               ▲     ▲   вхождения кончаются в позициях 6 и 8

На четвёртом символе видно, что делает таблица. Совпало aba, пришла a: получилось abaa, образцом это не продолжается. Но последняя a - начало образца, поэтому автомат уходит не в ноль, а в состояние 1. КМП пришёл бы туда же тремя сравнениями: с p[3], после отката до единицы - с p[1], после отката до нуля - с p[0]. Автомат знает ответ заранее.

Правило

Переход d[q][c] равен длине самого длинного начала образца, которым заканчивается строка «первые q символов образца плюс символ c». Если c совпал с p[q], это q + 1. Иначе в состоянии 0 это ноль, а в любом другом состоянии ответ тот же, что у автомата в состоянии π[q − 1] на том же символе, - и он уже посчитан, потому что π[q − 1] < q. Таблица строится за (m + 1) · k действий, поиск делает ровно n обращений к ней, и цена одного символа текста не зависит ни от образца, ни от данных.

Разбор: строим таблицу через префикс-функцию

def avtomat(p, alf):
    m = len(p)
    pi = prefiks(p)                             # из прошлой главы
    d = []
    q = 0
    while q <= m:
        stroka = {}
        for c in alf:
            if q < m and c == p[q]:
                stroka[c] = q + 1               # символ продолжил совпадение
            elif q == 0:
                stroka[c] = 0                   # откатываться некуда
            else:
                stroka[c] = d[pi[q - 1]][c]     # как после отката - а это уже известно
        d.append(stroka)
        q = q + 1
    return d

def poisk(t, d, m):
    q = 0
    nashli = 0
    for c in t:
        q = d[q][c]                             # вся работа с символом
        if q == m:
            nashli = nashli + 1
    return nashli

Проверим две клетки таблицы для abab. Префикс-функция образца - 0 0 1 2.

Состояние 3, символ a. Совпало aba, а p[3] = b, значит символ не продолжил. Откат: π[2] = 1. Берём готовую клетку d[1]["a"] - там 1. Проверка по определению: строка abaa кончается на a, это начало образца длины 1; на ab, aba или abab она не кончается. Сходится.

Состояние 4, символ a - что делать после найденного вхождения. Условие q < m ложно, откат: π[3] = 2, клетка d[2]["a"] = 3. По определению: ababa кончается на aba. Поэтому в тексте abababababab автомат находит все пять перекрывающихся вхождений - строка таблицы для состояния m делает то же, что откат после найденного вхождения в КМП.

Разбор: цена символа и цена таблицы

Ответ на вопрос из начала урока. Образец aaaaaaaaab, совпало девять a, пришла c. КМП сравнивает c с p[9], откатывается до 8, сравнивает с p[8], откатывается до 7 - и так до нуля. Десять сравнений на один символ. Автомат, построенный над алфавитом abc, делает одно обращение: d[9]["c"] = 0.

На весь текст счёт такой, n = 1000, образец "a" * 9 + "b":

наивный поиск       9 910 сравнений
КМП                 1 991 сравнение
автомат             1 000 обращений к таблице, сравнений символов нет

Сумма у КМП и автомата одного порядка. Разница в распределении: у автомата каждый символ стоит ровно единицу, у КМП - от одного до m. Теперь плата:

образец m     алфавит k                  клеток (m + 1) · k
    10        2 (биты)                            22
    10        26 (латиница)                      286
  1000        256 (байты)                    256 256
  1000        1 114 112 (Юникод)       больше миллиарда

Последняя строка - причина, по которой полный автомат не строят для текста в Юникоде. Выход - хранить в строке таблицы только символы, которые есть в образце, а для остальных отвечать нулём: q = d[q].get(c, 0). Символ, которого нет в образце, не может продолжить никакое его начало.

Разбор: тот же приём в методе четырёх русских

Автомат - частный случай общей идеи: если кусок работы зависит от небольшого числа возможных входов, ответы для ВСЕХ входов считают заранее и потом только читают из таблицы.

Метод четырёх русских назван по авторам статьи 1970 года - Арлазарову, Диницу, Кронроду и Фараджеву; они ускоряли так умножение таблиц из нулей и единиц. К таблицам динамического программирования для строк приём перенесли Масек и Патерсон в 1980 году. Возьми таблицу наибольшей общей подпоследовательности из раздела про динамику для двух строк длины N: N × N клеток, соседние клетки отличаются не больше чем на единицу. Значит, границу квадрата можно записать не числами, а разностями - нулями и единицами. Разрежем таблицу на квадраты со стороной в r клеток. Всё, что квадрат выдаёт на нижней и правой границе, определяется его входом: r разностей сверху, r слева и два куска строк по r символов.

Разных входов конечное число, и если взять r равным небольшой доле log N (какой именно - зависит от размера алфавита), их окажется меньше N. Ответы для всех считаются один раз. После этого таблица проходится квадратами: квадратов (N / r)², на каждый - одно обращение и r выходных значений. Итог - порядка N² / log N вместо N². На практике выигрыш скромный - в несколько раз даже на строках в миллион символов, - и его перекрывают битовые приёмы, которые обрабатывают 64 клетки одной машинной командой. Но сама идея «таблица для всех малых входов» встречается в алгоритмах постоянно.

Что ломается без этого

Первое: символ, которого нет в таблице. Автомат построен для алфавита ab, а в тексте встретилась c: d[q]["c"] - ошибка KeyError. Либо алфавит таблицы покрывает все символы текста, либо обращение идёт через get с нулём по умолчанию.

Второе: таблица без строки для состояния m. Цикл построения написан как q < m - и строки для вхождения нет. Первый же символ после найденного образца роняет программу с IndexError. Если вместо этого сбрасывать q в ноль, потеряются перекрывающиеся вхождения.

Третье: построение по определению. Для каждой клетки перебрать все длины начала и сравнить срезами - это m длин по m символов на каждую из m · k клеток, порядка m³ · k. Для образца в тысячу символов над байтами - сотни миллиардов действий вместо четверти миллиона.

Четвёртое: автомат там, где хватило бы КМП. Образец ищется один раз в коротком тексте, а подготовка таблицы стоит (m + 1) · k. При m = 1000 над байтами это 256 256 записей ради прохода по тексту, который может быть короче. Автомат окупается, когда текста много или когда важна цена каждого символа.

Зачем это в работе

Первый сюжет - регулярные выраженияРазбирается в разделе 21, глава «Конечные автоматы и регулярные языки»: Регулярные выражения: три операции, автомат и возвраты, которые не кончаются. Инструменты с гарантией линейного времени (утилита grep, библиотека RE2) превращают выражение в такой же автомат: состояния, таблица, одно обращение на символ. Поиск фиксированной строки - простейший случай; про общий будет раздел о вычислимости.

Второй - железо и поток. Сетевой фильтр, антивирус на шлюзе, разбор протокола в микросхеме: байты идут с постоянной скоростью, и обработчик обязан успевать на КАЖДЫЙ. Амортизированная оценка тут не годится - нужна гарантия на символ, и её даёт только таблица.

Третий - разбор текста программ. Первая стадия любого компилятора режет исходник на слова автоматом: по символу за шаг, без возвратов.

Теперь сам

Построй таблицу переходов для образца aab над алфавитом из букв a и b. Затем прогони по ней текст aaabaab и назови позиции, в которых кончаются вхождения.

состояние    что совпало        по a    по b
    0        ничего               1       0
    1        a                    2       0
    2        aa                   2       3
    3        aab - вхождение      1       0

текст        a  a  a  b  a  a  b
состояние    1  2  2  3  1  2  3