Ахо-Корасик: откаты КМП, перенесённые на дерево

Если ты расставишь суффиксные ссылки в боре для ab, abd, bc, объяснишь, почему их считают обходом в ширину, и докажешь оценку 2n, - листай до «Теперь сам».

Как думаешь, от чего зависит цена прохода

Текст - 10 000 символов. Образцов сто, каждый по шесть символов. Самое простое решение - запустить КМП сто раз: около 12 500 сравнений на проход, миллион с четвертью на всё.

Прежде чем читать дальше, ответь себе: должна ли цена прохода по тексту расти вместе с числом образцов? Если образцов станет тысяча - обязан ли поиск стать в десять раз дороже?

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

В уроке про КМП был домофон с одним кодом: он помнит, сколько цифр кода сейчас набрано, и после ошибки падает до самого длинного начала кода, которым кончается набранное.

Теперь представь пульт на сто квартир, у каждой свой код. Поставить сто отдельных слушателей - это сто проходов. Один слушатель справится, если будет помнить не «сколько цифр набрано», а «в каком месте дерева кодов я стою». После ошибки он переходит туда, где записано самое длинное начало ХОТЬ КАКОГО-ТО кода, которым кончается набранное. Коды разные, а слушатель один - потому что все коды лежат в одном дереве и общие начала у них общие.

Механизм: суффиксная ссылка

Образцы - ak, rak, kurs, rakurs. Бор:

(корень)
   ├ a ─ k*                           ak
   ├ r ─ a ─ k* ─ u ─ r ─ s*          rak, rakurs
   └ k ─ u ─ r ─ s*                   kurs

Узел будем называть строкой, которая к нему ведёт: узел raku - это четыре шага от корня.

Суффиксная ссылка узла ведёт в узел, строка которого - самый длинный собственный конец строки этого узла, имеющийся в боре. Собственный - значит короче самой строки. Если такого нет, ссылка ведёт в корень.

узел       концы его строки (от длинного)        ссылка
a          -                                      корень
ak         k                                      k
r          -                                      корень
ra         a                                      a
rak        ak, k                                  ak
raku       aku, ku, u                             ku
rakur      akur, kur, ur, r                       kur
rakurs     akurs, kurs, urs, rs, s                kurs
k          -                                      корень
ku         u                                      корень      (узла u в боре нет)
kur        ur, r                                  r
kurs       urs, rs, s                             корень

Смысл ссылки тот же, что у π[k − 1] в КМП. Стоя в узле raku, мы знаем последние четыре символа текста. Если следующий символ не продолжает путь, самое длинное, что ещё может оказаться началом образца, - конец ku. Туда и идём, не возвращаясь по тексту.

Прогон текста rakursa:

символ    r     a     k      u       r        s         a
узел      r     ra    rak    raku    rakur    rakurs    a
                      ▲                       ▲
                      rak                     rakurs           ▲ - узел помечен, найдено слово

последний символ:   rakurs → kurs → корень → a                 два ухода по ссылке и спуск

На последнем символе у узла rakurs нет ребра a. Ссылка ведёт в kurs - там тоже нет. Ссылка из kurs ведёт в корень, у корня ребро a есть. Семь символов, девять переходов: семь спусков и два ухода по ссылке.

Правило

Суффиксная ссылка сына u узла v по символу c находится так: взять ссылку v, и пока в том узле нет ребра c и это не корень - идти по ссылке дальше; если ребро c нашлось, ссылка u ведёт в его конец, иначе в корень. Ссылки сыновей корня ведут в корень. Узлы обходятся В ШИРИНУ - по уровням, потому что ссылка всегда ведёт на меньшую глубину и должна быть уже посчитана. При поиске число переходов не больше 2n: каждый символ текста опускает на один уровень, а каждый уход по ссылке поднимает хотя бы на один.

Разбор: строим ссылки и ищем

Бор строит функция bor из прошлого урока. Ссылки:

def ssylki(deti):
    ssyl = [0] * len(deti)            # ссылка каждого узла; 0 - корень
    ochered = []
    for c in deti[0]:
        ochered.append(deti[0][c])    # сыновья корня: ссылка в корень уже стоит
    g = 0
    while g < len(ochered):           # обход в ширину
        v = ochered[g]
        g = g + 1
        for c in deti[v]:
            u = deti[v][c]
            k = ssyl[v]
            while k > 0 and c not in deti[k]:
                k = ssyl[k]           # то же, что k = pi[k - 1] в КМП
            if c in deti[k]:
                k = deti[k][c]
            ssyl[u] = k
            ochered.append(u)
    return ssyl

Проверим одну строку таблицы. Узел rakur - сын узла raku по символу r. Ссылка raku ведёт в ku. У ku есть ребро r, оно ведёт в kur. Значит, ссылка rakur - узел kur. И вторая: kur - сын ku по r. Ссылка ku ведёт в корень, у корня есть ребро r. Ссылка kur - узел r.

Поиск. Пока сообщаем слово, только когда пришли в помеченный узел:

def poisk(t, deti, konec, ssyl):
    v = 0
    nashli = []
    perehodov = 0
    i = 0
    while i < len(t):
        c = t[i]
        while v > 0 and c not in deti[v]:
            v = ssyl[v]                           # ребра нет - уходим по ссылке
            perehodov = perehodov + 1
        if c in deti[v]:
            v = deti[v][c]
        perehodov = perehodov + 1
        if konec[v] >= 0:
            nashli.append([i, konec[v]])          # слово кончается в позиции i
        i = i + 1
    return [nashli, perehodov]

На тексте rakursa эта программа находит rak в позиции 2 и rakurs в позиции 5. Но в тексте есть ещё ak и kurs - и они пропущены. Это не ошибка ссылок, а недосказанность самого поиска; её закрывает следующий урок.

Разбор: замер против ста проходов

Текст tekst(10000, k, 1). Образцы - куски текста по шесть символов, взятые с позиций 13, 74, 135 и дальше с шагом 61; кусок, который уже есть в наборе, пропускается, и позиции перебираются, пока не наберётся нужное число разных.

алфавит    образцов    узлов в боре    проходы КМП, сравнений    Ахо-Корасик, переходов
   4            1             6                12 455                   12 456
   4           10            50               124 217                   18 583
   4          100           348             1 244 537                   18 140
  26          100           519             1 038 306                   19 193

Ответ на вопрос из начала урока: цена прохода по тексту вместе с числом образцов не растёт. Столбец КМП растёт в сто раз, столбец Ахо-Корасика остаётся под потолком 2n = 20 000, и потолок этот от числа образцов не зависит. От числа образцов зависит только подготовка - размер бора, - а она стоит порядка суммы длин образцов и делается один раз.

Откуда потолок. Глубина текущего узла растёт не больше чем на единицу за символ текста - всего не больше n раз. Уход по ссылке уменьшает глубину хотя бы на единицу. Уменьшить нельзя больше, чем увеличили. Это дословно доказательство для КМП, в котором «число совпавших символов» заменено на «глубину узла».

Обрати внимание на строку с одним образцом: 12 456 переходов против 12 455 сравнений. Алгоритм Ахо-Корасика на одном образце и есть КМП - бор вырождается в цепочку, ссылки в префикс-функцию. Разница в единицу - счёт после найденного вхождения: КМП заменяет k на π[m − 1] без сравнения, а здесь тот же шаг - уход по ссылке, и он посчитан как переход.

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

Первое: ссылки обходом в глубину. Ссылка узла вычисляется через ссылки узлов уровнем выше - в том числе из СОСЕДНИХ веток. При обходе в глубину до соседней ветки ещё не дошли, там стоят нули, и ссылки выходят короче правильных. Программа работает, но пропускает вхождения.

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

Третье: условие v > 0 забыто. В корне без подходящего ребра идти некуда: символ просто пропускается, поиск остаётся в корне. Без проверки цикл ухода по ссылке не кончится.

Четвёртое: сообщать только слово своего узла. На rakursa найдено два слова из четырёх. Так теряется каждое слово, которое является концом другого слова или его начала.

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

Первый сюжет - список слов и большой текст. Команда grep -F -f slova.txt journal.log печатает строки журнала, в которых встретилось хотя бы одно слово из файла slova.txt: ключ -f велит взять образцы из файла, ключ -F - искать их как есть, без регулярных выраженийРазбирается в разделе 21, глава «Конечные автоматы и регулярные языки»: Регулярные выражения: три операции, автомат и возвраты, которые не кончаются. Для набора фиксированных строк GNU grep строит именно этот автомат: проход по журналу один, сколько бы слов ни было в файле.

Второй - сигнатуры. Антивирус сверяет файл с сотнями тысяч известных последовательностей байтов, система обнаружения вторжений - сетевой поток с тысячами правил. Запускать поиск по разу на правило невозможно; все сигнатуры лежат в одном боре, и на байт данных в среднем уходит не больше двух переходов.

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

Теперь сам

Образцы - ab, abd, bc. Расставь суффиксные ссылки во всех узлах бора. Затем прогони текст abc: в каких узлах побывает поиск и сколько сделает переходов?

узел     концы его строки     ссылка
a        -                     корень
ab       b                     b
abd      bd, d                 корень
b        -                     корень
bc       c                     корень