Алгоритм Ахо-Корасик: поиск множества образцов в тексте

Алгоритм Ахо-Корасик (Aho-Corasick, 1975) - стандартный способ искать сразу множество образцов $P_1, P_2, \ldots, P_k$ в тексте $T$ за один линейный проход. Время работы - $O(|T| + \sum |P_i| + z)$, где $z$ - суммарное число вхождений всех образцов в текст. Никакой зависимости от $k$ или от длин отдельных паттернов в основном цикле: текст читается строго по одному символу слева направо, и каждое новое чтение стоит амортизированно константу. Опубликовали его Альфред Ахо и Маргарет Корасик в Bell Labs, и именно их статья лежит в основе fgrep, антивирусного сканирования сигнатур и многих фильтров содержимого.

Зачем нужен отдельный алгоритм для множественного поиска

Если паттернов мало, можно запустить KMP или Бойер-Мур $k$ раз - получится $O(k|T| + \sum|P_i|)$. На двух-трёх паттернах это нормально, но антивирус хочет проверить файл против десятков тысяч сигнатур, а почтовый фильтр - против списка из миллиона запрещённых фраз. Множитель $k$ становится неприемлемым.

Главная идея Ахо-Корасик - объединить все паттерны в одну структуру и провести по тексту только один указатель. Бор (trie) образцов даёт компактное представление всех паттернов сразу: общие префиксы хранятся в одной цепочке. Дальше остаётся приделать к бору механизм «куда переходить при несовпадении», аналогичный префикс-функции KMP. Этот механизм называется суффиксная ссылка (suffix link, fail link).

Бор образцов (trie)

Бор - дерево, в котором каждое ребро помечено символом, а корень соответствует пустой строке. Чтобы добавить паттерн $P_i$, спускаемся от корня по символам $P_i$, создавая недостающие узлы. Узел, в котором паттерн заканчивается, помечаем - «здесь принимается $P_i$».

Например, для $P_1 = \text{he}$, $P_2 = \text{she}$, $P_3 = \text{his}$, $P_4 = \text{hers}$ получится бор из 9 узлов: корень $\to h \to e$ (принимающий $\text{he}$) $\to r \to s$ (принимающий $\text{hers}$), отдельная ветка $h \to i \to s$ (принимающий $\text{his}$), отдельная ветка $s \to h \to e$ (принимающий $\text{she}$). Суммарный размер бора - $O(\sum |P_i|)$.

Узел бора однозначно соответствует префиксу одного или нескольких паттернов. Это ключевое свойство: пока мы стоим в узле $v$, путь от корня до $v$ - это последнее, что мы успешно сопоставили с текстом.

Суффиксные ссылки

Когда из узла $v$ нет перехода по очередному символу текста, нам нужно отступить. В KMP мы сдвигались по префикс-функции - на самый длинный собственный префикс, совпадающий с суффиксом. В Ахо-Корасике делаем то же самое, но в боре: суффиксная ссылка $\text{suf}(v)$ ведёт в узел, соответствующий самому длинному собственному суффиксу строки $v$, который сам является префиксом какого-нибудь паттерна (то есть присутствует в боре).

Формально: если $v$ соответствует строке $w$, то $\text{suf}(v)$ - это узел, соответствующий самой длинной строке $w'$ такой, что $w'$ - собственный суффикс $w$ и $w'$ есть в боре. Для корня и его прямых детей $\text{suf}$ равна корню.

В примере выше для узла «$\text{she}$» суффиксная ссылка ведёт в узел «$\text{he}$» - самый длинный собственный суффикс $\text{she}$, присутствующий в боре. Для узла «$\text{his}$» она ведёт в узел «$s$» (если он есть как префикс какого-то паттерна) или в корень.

Это прямой аналог префикс-функции для случая множества строк. Когда паттерн один - Ахо-Корасик вырождается ровно в KMP: бор становится цепочкой, а суффиксные ссылки - массивом $\pi$.

Построение суффиксных ссылок через BFS

Суффиксные ссылки строятся обходом бора в ширину (BFS) с корня. Для каждого узла $v$ с родителем $u$ и ребром-символом $c$ суффиксная ссылка вычисляется так:

1. Берём $w = \text{suf}(u)$ - суффиксную ссылку родителя.
2. Пока из $w$ нет перехода по $c$ и $w$ не корень - поднимаемся: $w \leftarrow \text{suf}(w)$.
3. Если из $w$ есть переход по $c$ и он не равен самому $v$ - это и есть $\text{suf}(v)$. Иначе $\text{suf}(v) =$ корень.

Псевдокод:

queue = [root]
suf[root] = root
for child v of root:
    suf[v] = root
    queue.push(v)
while queue not empty:
    u = queue.pop()
    for each edge (u, c) -> v:
        w = suf[u]
        while w != root and not has_edge(w, c):
            w = suf[w]
        suf[v] = go(w, c) if has_edge(w, c) and go(w, c) != v else root
        queue.push(v)

BFS гарантирует, что суффиксная ссылка родителя уже известна к моменту, когда обрабатывается ребёнок. Амортизированно построение стоит $O(\sum |P_i|)$ - тот же аргумент про сумму подъёмов по $\text{suf}$ и спусков по $c$, что и в анализе KMP.

В индустриальных реализациях бор сразу превращают в полный автомат: для каждого узла $v$ и каждого символа $c$ кэшируют $\text{go}(v, c)$ - куда переходить из $v$ по $c$ с учётом суффиксных ссылок. Тогда переход стоит ровно одну операцию, без while. Памяти уходит больше - $O(|\text{бор}| \cdot \sigma)$, но скорость поиска становится максимальной.

Финальные ссылки (dict-link)

Одна суффиксная ссылка отвечает на вопрос «куда упасть при несовпадении». Но есть и другой вопрос: какие паттерны заканчиваются в текущем узле или в одном из его суффиксных предков. Если узел $v$ принимающий - заканчивается паттерн в самом $v$; но если $\text{suf}(v)$ или $\text{suf}(\text{suf}(v))$ - тоже принимающие, в позиции, соответствующей $v$, заканчиваются и они.

Чтобы не ходить по цепочке $\text{suf}$ на каждом шаге поиска, заводят финальную ссылку (dict-link, output link) $\text{out}(v)$ - ближайший принимающий узел в цепочке суффиксных ссылок, не считая самого $v$. Если такого нет - $\text{out}(v) =$ корень (или null).

Финальные ссылки строятся тем же BFS-проходом:

$\text{out}(v) = \begin{cases} \text{suf}(v), & \text{если } \text{suf}(v) \text{ принимающий}, \\ \text{out}(\text{suf}(v)), & \text{иначе}. \end{cases}$

При посещении узла $v$ в поиске мы выводим паттерн в $v$ (если принимающий) и потом идём по $\text{out}$, пока не упрёмся в корень. Это даёт ровно $z$ операций суммарно за весь поиск - за это и отвечает слагаемое $z$ в сложности.

Алгоритм поиска

Имея автомат, текст обрабатывается одним указателем $v$ - текущий узел:

v = root
for i in 0..n-1:
    while v != root and not has_edge(v, T[i]):
        v = suf[v]
    if has_edge(v, T[i]):
        v = go(v, T[i])
    # вывод вхождений, заканчивающихся в этой позиции
    u = v
    while u != root:
        if u is accepting:
            report match of pattern(u) ending at i
        u = out[u]

При полном автомате (с кэшированными $\text{go}$) внутренний while исчезает: переход становится одним обращением к таблице. Внешний цикл по тексту - $|T|$ итераций. Сумма всех итераций цикла «вывод вхождений» - ровно $z$. Итого $O(|T| + z)$ для самого поиска, плюс $O(\sum |P_i|)$ на построение. Если бор хранится компактно (с переходами по хешу или массиву), память тоже $O(\sum |P_i|)$.

Подробный пример

Образцы $P_1 = \text{he}$, $P_2 = \text{she}$, $P_3 = \text{his}$, $P_4 = \text{hers}$. Текст $T = \text{ushers}$.

Бор и суффиксные ссылки:

• $h \to h e$ (приём $\text{he}$) $\to her \to hers$ (приём $\text{hers}$).
• $h \to hi \to his$ (приём $\text{his}$).
• $s \to sh \to she$ (приём $\text{she}$), $\text{suf}(she) = he$.

Шаг $i = 0$, $T[0] = u$. Из корня нет перехода по $u$, остаёмся в корне.

Шаг $i = 1$, $T[1] = s$. Из корня переход по $s$ есть, идём в узел $s$.

Шаг $i = 2$, $T[2] = h$. Из $s$ переход по $h$ - в узел $sh$.

Шаг $i = 3$, $T[3] = e$. Из $sh$ переход по $e$ - в узел $she$. Узел принимающий → вхождение $\text{she}$, заканчивается в позиции 3. Идём по $\text{out}(she) = he$ - тоже принимающий → вхождение $\text{he}$, заканчивается в позиции 3.

Шаг $i = 4$, $T[4] = r$. Из $she$ перехода по $r$ нет. Идём по $\text{suf}(she) = he$. Из $he$ переход по $r$ - в узел $her$. Узел не принимающий, $\text{out}(her) =$ корень.

Шаг $i = 5$, $T[5] = s$. Из $her$ переход по $s$ - в узел $hers$. Принимающий → вхождение $\text{hers}$, заканчивается в позиции 5.

Итого три вхождения за один линейный проход по тексту длины 6.

Связь с KMP и Бойером-Муром

Ахо-Корасик - это KMP, обобщённый на множество паттернов. При $k = 1$ бор вырождается в цепочку из $|P_1|$ узлов, суффиксные ссылки совпадают с массивом префикс-функции $\pi$, и алгоритм работает буква в букву как KMP. С Бойером-Муром аналогия слабее: его сравнение справа налево плохо обобщается на паттерны разной длины. Существует алгоритм Commentz-Walter (1979) с эвристиками плохого символа и хорошего суффикса на боре - быстрее в среднем на больших алфавитах, но сложнее и теряет линейность в худшем случае. Поэтому в fgrep GNU и большинстве библиотек по умолчанию стоит именно Ахо-Корасик.

Применения

• Антивирусные сканеры. ClamAV, Avast, ESET и большинство сканеров используют Ахо-Корасик для проверки файла против базы из десятков тысяч сигнатур за один проход. Без него антивирус был бы медленнее на порядки.
• grep -f и fgrep. Когда grep получает файл паттернов через -f или работает в режиме фиксированных строк (fgrep = grep -F), строится автомат Ахо-Корасика. fgrep -f huge_list.txt big_file остаётся линейным даже на миллионе шаблонов.
• Веб-фильтры и DLP. Корпоративные шлюзы проверяют трафик против списков запрещённых терминов, ключей и кодов проектов - сотни тысяч паттернов за один проход.
• Биоинформатика. Множественный поиск мотивов промоторов, сайтов связывания транскрипционных факторов и рестриктаз в геноме: все мотивы - в бор, геном - через автомат.

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

• Считают, что суффиксная ссылка ведёт в родителя. Нет: суффиксная ссылка ведёт по строке-суффиксу, а не по узлу-родителю. Эти направления почти всегда разные.
• Забывают про финальные ссылки. Без $\text{out}$ при поиске нужно на каждом шаге проходить вверх по всей цепочке $\text{suf}$, проверяя принимающие узлы. Это даёт лишний множитель и может довести до $O(|T| \cdot \text{глубина})$ в патологических случаях.
• Строят суффиксные ссылки в DFS, а не в BFS. В DFS суффиксная ссылка родителя ещё не вычислена, когда обрабатывается ребёнок. Алгоритм перестаёт работать без явных дополнительных проходов.
• Не учитывают паттерны-префиксы друг друга. Если $P_1 = \text{he}$ и $P_2 = \text{hello}$, в узле «$he$» заканчивается $P_1$, но не $P_2$. Финальная ссылка из узла «$hello$» должна указать на «$he$», иначе при поиске «$hello$» в тексте вхождение «$he$» потеряется.
• Применяют Ахо-Корасик там, где достаточно одного KMP. На одиночном паттерне накладные расходы построения и навигации по бору не оправданы - KMP с массивом $\pi$ проще и быстрее по константам.

FAQ

Чем алгоритм Ахо-Корасик отличается от KMP? KMP ищет один паттерн через префикс-функцию массива $\pi$. Ахо-Корасик ищет сразу множество паттернов: все они укладываются в бор, поверх строятся суффиксные ссылки (аналог $\pi$) и финальные ссылки (для перехода между вложенными вхождениями). За один проход по тексту находятся все вхождения всех паттернов. При $k = 1$ Ахо-Корасик буквально вырождается в KMP.

Зачем нужна отдельная финальная ссылка, если есть суффиксная? Суффиксная отвечает «куда идти при несовпадении». Финальная отвечает «какие паттерны заканчиваются в этой позиции, кроме паттерна в текущем узле». Без неё пришлось бы при каждом шаге поиска проходить вверх по цепочке $\text{suf}$ и проверять каждый узел на принимаемость. Финальная ссылка перепрыгивает сразу на ближайший принимающий узел в этой цепочке, что даёт корректную оценку $O(|T| + z)$.

Как Ахо-Корасик масштабируется на миллион паттернов? Время и память построения линейны по сумме длин паттернов: $O(\sum |P_i|)$. На миллионе коротких паттернов это умеренные мегабайты бора, и сам поиск остаётся линейным по тексту. На практике именно поэтому он стоит в антивирусах и DLP-системах, где число сигнатур постоянно растёт.

Коротко

Алгоритм Ахо-Корасик ищет все вхождения множества образцов $P_1, \ldots, P_k$ в тексте $T$ за $O(|T| + \sum |P_i| + z)$, где $z$ - общее число вхождений. Структура: бор всех паттернов плюс суффиксные ссылки (аналог префикс-функции KMP - указывают на самый длинный собственный суффикс, присутствующий в боре) и финальные ссылки (на ближайший принимающий узел в цепочке суффиксов). Построение - BFS по бору, поиск - один проход по тексту с переходами по бору и суффиксным ссылкам при несовпадении. При $k = 1$ алгоритм вырождается в KMP. Стандартный инструмент в антивирусах (сигнатуры), fgrep со списком шаблонов, веб-фильтрах и поиске мотивов в биоинформатике.