Алгоритм Ахо-Корасик

Задача:

Дан набор строк в алфавите размера [math]k[/math] суммарной длины [math]m[/math]. Необходимо найти для каждой строки все ее вхождения в текст за время [math]O(m)[/math] и [math]O(mk)[/math] памяти.

Алгоритм

Шаг 1. Построение бора

Строим бор из строк.
Построение выполняется за время [math]O(m)[/math], где [math]m[/math] — суммарная длина строк.

Пример построенного бора

Бор для набора строк [math] \{ \textbf{he}, \textbf{she}, \textbf{his}, \textbf{hers}\} [/math]:

Шаг 2. Преобразование бора

Обозначим за [math][u][/math] слово, приводящее в вершину [math]u[/math] в боре.
Узлы бора можно понимать как состояния автомата, а корень как начальное состояние.
Узлы бора, в которых заканчиваются строки, становятся терминальными.
Для переходов по автомату заведём в узлах несколько функций:

• [math]\mathrm{parent}(u)[/math] — возвращает родителя вершины [math]u[/math];
  
• [math]\pi(u) = \delta(\pi(\mathrm{parent}(u)), c)[/math] — суффиксная ссылка, и существует переход из [math]\mathrm{parent}(u)[/math] в [math]u[/math] по символу [math]c[/math];
  
• [math]\delta(u, c) = \begin{cases} v, &\text{if $v$ is son by symbol $c$ in trie;}\\ root, &\text{if $u$ is root and $u$ has no child by symbol $c$ in trie}\\ \delta(\pi(u), c), &\text{else.} \end{cases}[/math] — функция перехода.

Мы можем понимать рёбра бора как переходы в автомате по соответствующей букве. Однако одними только рёбрами бора нельзя ограничиваться. Если мы пытаемся выполнить переход по какой-либо букве, а соответствующего ребра в боре нет, то мы тем не менее должны перейти в какое-то состояние. Для этого нам и нужны суффиксные ссылки.
Суффиксная ссылка [math]\pi(u) = v[/math], если [math][v][/math] — максимальный суффикс [math][u][/math], [math][v]\neq[u][/math]. Функции перехода и суффиксные ссылки можно найти либо алгоритмом обхода в глубину с ленивыми вычислениями, либо с помощью алгоритма обхода в ширину.

Пример автомата Ахо-Корасик

Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.

Суффиксная ссылка для каждой вершины [math]u[/math] — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине [math]u[/math]. Единственный особый случай — корень бора; для удобства суффиксную ссылку из него проведём в себя же. Например, для вершины [math]5[/math] с соответствующей ей строкой [math]"she"[/math] максимальным суффиксом является строка [math]"she"[/math], но такой строки больше в нашем автомате нет. Возьмем второй по длине суффикс [math]"he"[/math]. Видим, что такая строка заканчивается в вершине [math]2[/math]. Следовательно суффиксной ссылкой вершины для [math]5[/math] является вершина [math]2[/math] .

Шаг 3. Построение сжатых суффиксных ссылок

[math]up(u) = \begin{cases} \pi(u), &\text{if $\pi(u)$ is terminal;}\\ \varnothing,&\text{if $\pi(u)$ is root;}\\ up(\pi(u)), &\text{else.} \end{cases}[/math] — сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам.

Сжатые суффиксные ссылки могут отыскиваться при помощи ленивой рекурсии.

Использование автомата

Теперь нужно сказать немного слов о том, как мы будем использовать наш автомат. По очереди просматриваем символы текста. Для очередного символа [math]c[/math] переходим из текущего состояния [math]u[/math] в состояние, которое вернёт функция [math]\delta(u, c)[/math]. Оказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам строки, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, то соответствующие ему строки тоже отмечаем.

Пример реализации

Ниже представлена реализация некоторых функций (используется ленивая рекурсия).

Структура вершины:

struct Node:
    Node son[k]                                 // массив сыновей; k — это размер алфавита
    Node go[k]                                  // массив переходов (запоминаем переходы в ленивой рекурсии)
    Node parent                                 // вершина родитель
    Node suffLink                               // суффиксная ссылка (вычисляем в ленивой рекурсии)
    Node up                                     // сжатая суффиксная ссылка
    char charToParent                           // символ, ведущий к родителю
    bool isLeaf                                 // флаг, является ли вершина терминалом
    vector<int> leafPatternNumber               // номера строк, за которые отвечает терминал

Функция, для вычисления суффиксной ссылки:

Node getSuffLink(Node v):
    if not v.suffLink                           // если суффиксная ссылка ещё не вычислена
       if v == root or v.parent == root
            v.suffLink = root
       else
            v.suffLink = getLink(getSuffLink(v.parent), v.charToParent)
    return v.suffLink

Функция, для вычисления перехода:

Node getLink(Node v, char c): 
   if not v.go[c]                               // если переход по символу c ещё не вычислен
        if v.son[c]
            v.go[c] = v.son[c]
        else if v == root 
            v.go[c] = root 
        else 
            v.go[c] = getLink(getSuffLink(v), c)
    return v.go[c]

Функция, для вычисления сжатой суффиксной ссылки:

Node getUp(Node v):
    if not v.up                                 // если сжатая суффиксная ссылка ещё не вычислена
        if getSuffLink(v).isLeaf
            v.up = getSuffLink(v)
        else if getSuffLink(v) == root
            v.up = root
        else 
            v.up = getUp(getSuffLink(v))
    return v.up

Функция, для добавление строки в бор:

fun addString(string const& s, int patternNumber):
    Node cur = root
    for i = 0 to s.length - 1
        char c = s[i] - 'a'
        if cur.son[c] == 0
            cur.son[c] = Node
            /* здесь также нужно обнулить указатели на переходы и сыновей */
            cur.son[c].suffLink = 0
            cur.son[c].up = 0
            cur.son[c].parent = cur
            cur.son[c].charToParent = c
            cur.son[c].isLeaf = false
        cur = cur.son[c]
    cur.isLeaf = true
    cur.leafPatternNumber.push_back(patternNumber)

Функция, для процессинга текста (поиск, встречается строка или нет):

fun processText(string const& t, vector<bool>& found):   // found - это вектор, длина которого равна количеству строк
    found.assign(w, false)                               // w - количество строк
    Node cur = root
    for i = 0 to t.length - 1 
        char c = t[i] - 'a'
        cur = getLink(cur, c)
        for j = 0 to cur.leafPatternNumber.size - 1
            found[cur.leafPatternNumber[j]] = true
        /* В этом месте кода должен выполняться переход по сжатой суффиксной ссылке getUp(cur). Для вершины,
           обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки
           и так до корня. Хорошо ускорит программу сброс сжатых суффиксных ссылок для посещённых вершин. */

Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет.

Оптимизации

Если требуется найти только первое вхождение строки в текст, то существенно ускорить работу алгоритма могут пометки о посещённости узла, т.е. если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.

Поиск шаблонов с масками

Задача:

Пусть [math]\varphi[/math] — маска, обозначающая любой одиночный символ. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.

Например, шаблон [math]ab\varphi\varphi c\varphi[/math], который содержит в себе три маски, встречается на позициях [math]2[/math] и [math]8[/math] строки [math]xabvccababcax[/math].

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

Для того чтобы найти все вхождения в текст заданного шаблона с масками [math]Q[/math], необходимо обнаружить вхождения в текст всех его безмасочных кусков.
Пусть [math]\{Q_1, \dots, Q_k \}[/math] — набор подстрок [math]Q[/math], разделенных масками, и пусть [math]\{ l_1, \dots, l_k \}[/math] — их стартовые позиции в [math]Q[/math]. Например, шаблон [math]ab\varphi\varphi c\varphi[/math] содержит две подстроки без масок [math]ab[/math] и [math]c[/math] и их стартовые позиции соответственно [math]1[/math] и [math]5[/math]. Для алгоритма понадобится массив [math]C[/math]. [math]C[i][/math] — количество встретившихся в тексте безмасочных подстрок шаблона, который начинается в тексте на позиции [math]i[/math]. Тогда появление подстроки [math]Q_i[/math] в тексте на позиции [math]j[/math] будет означать возможное появление шаблона на позиции [math]j - l_i + 1[/math].

1. Используя алгоритм Ахо-Корасик, находим безмасочные подстроки шаблона [math]Q[/math]: когда находим [math]Q_i[/math] в тексте [math]T[/math] на позиции [math]j[/math], увеличиваем на единицу [math]C[j - l_i + 1][/math].
   
2. Каждое [math]i[/math], для которого [math]C[i] = k[/math], является стартовой позицией появления шаблона [math]Q[/math] в тексте.
   

Рассмотрим подстроку текста [math]T[i \dots i+n-1][/math]. Равенство [math]C[i] = k[/math] будет означать, что подстроки текста [math] T[i + l_1 \dots i + l_1 + |Q_1| - 1], T[i + l_2 \dots i + l_2 + |Q_2| - 1][/math] и так далее будут равны соответственно безмасочным подстрокам шаблона [math]\{Q_1, \dots , Q_k \}[/math]. Остальная часть шаблона является масками, поэтому шаблон входит в текст на позиции [math]i[/math].
Поиск подстрок заданного шаблона с помощью алгоритма Ахо-Корасик выполняется за время [math]O(m+n+a)[/math], где [math]n[/math] — суммарная длина подстрок, то есть длина шаблона, [math]m[/math] — длина текста, [math]a[/math] — количество появлений подстрок шаблона. Далее просто надо пробежаться по массиву [math]C[/math] и просмотреть значения ячеек за время [math]O (m)[/math].

См. также

• Алгоритм Бойера-Мура
• Алгоритм Кнута-Морриса-Пратта

Источники информации

• MAXimal :: algo :: Алгоритм Ахо-Корасик
• Сопоставление множеств и алгоритм Ахо-Корасик
• Codeforces :: Алгоритм Ахо-Корасик
• Habr :: Алгоритм Ахо-Корасик
• Wiki :: Алгоритм Ахо-Корасик