Алгоритм Ахо-Корасик — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Шаг 2: Добавляю пример автомата АК)
(Пример автомата Ахо-Корасик: Replace back to tex, to the same style as in the beginning of the article)
 
(не показано 113 промежуточных версий 16 участников)
Строка 1: Строка 1:
== Задача алгоритма ==
+
{{Задача
Найти для каждого образца из заданного множества образцов все его вхождения в текст за время <tex>O(m+n+a)</tex>, где <tex>m</tex> - суммарная длина образцов, <tex>n</tex> - длина текста, <tex>a</tex> - размер ответа (количество пар). В худшем случае <tex>a=nk</tex>, но он случается редко.
+
|definition = Дан набор строк в алфавите размера <tex>k</tex> суммарной длины <tex>m</tex>. Необходимо найти для каждой строки все ее вхождения в текст.
 +
}}
  
== Шаг 1 ==
+
==Алгоритм==
Строим бор из образцов. См. [[Бор]].<br />
+
=== Шаг 1. Построение бора ===
Построение выполняется за время <tex>O(m)</tex>, где <tex>m</tex> - суммарная длина образцов.
+
Строим [[Бор|бор]] из строк.<br />
 +
Построение выполняется за время <tex>O(m)</tex>, где <tex>m</tex> {{---}} суммарная длина строк.
  
=== Пример построенного бора ===
+
====Пример построенного бора====
Бор для набора образцов {he, she, his, hers}:<br />
+
Бор для набора строк <tex> \{ \textbf{he},\ \textbf{she},\ \textbf{his},\ \textbf{hers}\} </tex>:<br />
[[Файл:Aho-corasick1.jpg‎]]
+
[[Файл:Бор.jpg‎]]
  
== Шаг 2 ==
+
=== Шаг 2. Преобразование бора ===
Превращаем бор в автомат.<br />
+
Обозначим за <tex>[u]</tex> слово, приводящее в вершину <tex>u</tex> в боре.<br />
Узлы бора становятся состояниями автомата; корень - начальное состояние.<br />
+
Узлы бора можно понимать как состояния [[Детерминированные_конечные_автоматы | автомата]], а корень как начальное состояние.<br />
Узлы бора, в которых заканчиваются образцы, становятся терминалами.<br /><br />
+
Узлы бора, в которых заканчиваются строки, становятся терминальными.<br />
 
Для переходов по автомату заведём в узлах несколько функций:<br />
 
Для переходов по автомату заведём в узлах несколько функций:<br />
1) <tex>parent(u)</tex> - возвращает родителя вершины <tex>u</tex>;<br />
+
*<tex>\mathrm{parent}(u)</tex> {{---}} возвращает родителя вершины <tex>u</tex>;<br />
2) <tex>\pi(u) = \delta(\pi(parent(u)), c)</tex> - суффиксная ссылка; здесь <tex>u</tex> - сын <tex>parent(u)</tex> по символу <tex>c</tex>;<br />
+
*<tex>\pi(u) = \delta(\pi(\mathrm{parent}(u)), c)</tex> {{---}} '''суффиксная ссылка''', и существует переход из  <tex>\mathrm{parent}(u)</tex> в <tex>u</tex> по символу <tex>c</tex>;<br />
3) <tex>\delta(u, c) =  
+
*<tex>\delta(u, c) =  
 
   \begin{cases}
 
   \begin{cases}
     v\text{, if $v$ is son by symbol $c$ in trie;}\\
+
     v,                &\text{if $v$ is son by symbol $c$ in trie;}\\
     \delta(\pi(u), c)\text{, else.}
+
    root,              &\text{if $u$ is root and $u$ has no child by symbol $c$ in trie}\\
   \end{cases}</tex> - функция перехода.<br /><br />
+
     \delta(\pi(u), c), &\text{else.}
Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> - максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>. Обозначение: <tex>[u]</tex> - слово, приводящее в вершину <tex>u</tex> в боре.<br />
+
   \end{cases}</tex> {{---}} функция перехода.
Функции перехода и суффиксные ссылки можно найти либо алгоритмом обхода в глубину с ленивыми вычислениями, либо с помощью алгоритма обхода в ширину.
+
Мы можем понимать рёбра бора как переходы в автомате по соответствующей букве. Однако одними только рёбрами бора нельзя ограничиваться. Если мы пытаемся выполнить переход по какой-либо букве, а соответствующего ребра в боре нет, то мы тем не менее должны перейти в какое-то состояние. Для этого нам и нужны суффиксные ссылки.
=== Пример автомата Ахо-Корасик ===
+
<br> Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> {{---}} максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>.
[[Файл:Aho-corasick2.jpg]]<br />
+
Функции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]].
 +
 
 +
Из определений выше можно заметить два следующих факта:
 +
* функция перехода определена через суффиксную ссылку, а суффиксная ссылка {{---}} через функию переходов;
 +
* для построения суффиксных ссылок небходимо знать информацию только выше по бору от текущей вершины до корня.
 +
Это позволяет реализовать функции поиска переходов по символу и суффиксных ссылок ленивым образом при помощи взаимной рекурсии.
 +
 
 +
==== Пример автомата Ахо-Корасик ====
 +
[[Файл:axo.jpg]]<br />
 
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.
 
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.
  
== Шаг 3 ==
+
Суффиксная ссылка для каждой вершины <tex>u</tex> — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине <tex>u</tex>. Единственный особый случай — корень бора: для удобства суффиксную ссылку из него проведём в себя же. Например, для вершины <tex>5</tex> с соответствующей ей строкой <tex>\textbf{she}</tex> максимальным подходящим суффиксом является строка <tex>\textbf{he}</tex>. Видим, что такая строка заканчивается в вершине <tex>2</tex>. Следовательно суффиксной ссылкой вершины для <tex>5</tex> является вершина <tex>2</tex>.
Построение сжатых суффиксных ссылок.<br />
+
 
 +
===Шаг 3. Построение сжатых суффиксных ссылок ===
 +
При построении автомата может возникнуть такая ситуация, что ветвление есть не на каждом символе. Тогда можно маленький бамбук заменить одним ребром. Для этого и используются сжатые суффиксные ссылки.
 +
 
 
<tex>up(u) =  
 
<tex>up(u) =  
 
   \begin{cases}
 
   \begin{cases}
     \pi(u)\text{, if $\pi(u)$ is terminal;}\\
+
     \pi(u),    &\text{if $\pi(u)$ is terminal;}\\
     \emptyset\text{, if $\pi(u)$ is root;}\\
+
     \varnothing,&\text{if $\pi(u)$ is root;}\\
     up(\pi(u))\text{, else.}
+
     up(\pi(u)), &\text{else.}
   \end{cases}</tex> - сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам.<br /><br />
+
   \end{cases}</tex>  
Сжатые суффиксные ссылки могут отыскиваться при помощи ленивой рекурсии.
+
 
 +
где <tex>up</tex> {{---}} сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам. Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут быть найдены при помощи ленивой рекурсии.
  
 
== Использование автомата ==
 
== Использование автомата ==
По очереди просматриваем символы текста. Для очередного символа <tex>c</tex> переходим из текущего состояния <tex>u</tex> в состояние, которое вернёт функция <tex>\delta(u, c)</tex>. Оказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам образцы, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, то соответствующие ему образцы тоже отмечаем.<br />
+
Теперь нужно сказать немного слов о том, как мы будем использовать наш автомат. По очереди просматриваем символы текста. Для очередного символа <tex>c</tex> переходим из текущего состояния <tex>u</tex> в состояние, которое вернёт функция <tex>\delta(u, c)</tex>. Оказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам строки, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, то соответствующие ему строки тоже отмечаем.<br />
''Примечание.'' Если требуется найти только первое вхождение образца в текст, то существенно ускорить работу алгоритма могут пометки о посещённости узла, т.е. если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
+
 
 +
== Пример реализации ==
 +
Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br />
 +
<tex>k</tex> {{---}} размер алфавита.
 +
 
 +
'''Структура вершины:'''
 +
'''struct''' Node:
 +
    '''Node''' son[k]                                <font color=green>// массив сыновей</font>
 +
    '''Node''' go[k]                                  <font color=green>// массив переходов (запоминаем переходы в ленивой рекурсии), используемый для вычисления суффиксных ссылок</font>
 +
    '''Node''' parent                                <font color=green>// вершина родитель</font>
 +
    '''Node''' suffLink                              <font color=green>// суффиксная ссылка (вычисляем в ленивой рекурсии)</font>
 +
    '''Node''' up                                    <font color=green>// сжатая суффиксная ссылка</font>
 +
    '''char''' charToParent                          <font color=green>// символ, ведущий к родителю</font>
 +
    '''bool''' isLeaf                                <font color=green>// флаг, является ли вершина терминалом</font>
 +
    '''vector<int>''' leafPatternNumber              <font color=green>// номера строк, за которые отвечает терминал</font>
 +
 
 +
'''Функция для вычисления суффиксной ссылки:'''
 +
'''Node''' getSuffLink('''Node''' v):
 +
    '''if''' v.suffLink == ''null''                      <font color=green>// если суффиксная ссылка ещё не вычислена</font>
 +
        '''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''' v.go[c] == ''null''                           <font color=green>// если переход по символу c ещё не вычислен</font>
 +
        '''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''' v.up == ''null''                            <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font>
 +
        '''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''' s, '''int''' patternNumber):
 +
    '''Node''' cur = root
 +
    '''for''' i = 0 '''to''' s.length - 1
 +
        '''char''' c = s[i]
 +
        '''if''' cur.son[c] == 0
 +
            cur.son[c] = Node
 +
            <font color=green>/* здесь также нужно обнулить указатели на переходы и сыновей */</font>
 +
            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.pushBack(patternNumber)
 +
'''Функция для процессинга текста (поиск, встречается строка или нет):'''
 +
'''fun''' processText('''string''' t): 
 +
    '''Node''' cur = root
 +
    '''for''' i = 0 '''to''' t.length - 1
 +
        '''char''' c = t[i] - 'a'
 +
        cur = getLink(cur, c)
 +
        <font color=green>/* В этом месте кода должен выполняться переход по '''сжатой''' суффиксной ссылке getUp(cur). Для вершины,
 +
            обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки
 +
            и так до корня. */</font>
 +
Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет.
 +
 
 +
== Оптимизации ==
 +
Существует несколько оптимизаций данного алгоритма, направленных на случаи, когда нас интересует только первое вхождение образца в текст:
 +
 
 +
# '''Сброс сжатых суффиксных ссылок для посещённых вершин.'''
 +
#: Существенно ускорить работу алгоритма могут пометки о посещённости узла, то есть если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
 +
# '''Сброс пометки терминальной вершины.'''
 +
#: В изначальном множестве образцов могут быть дублирующиеся строки. Мы можем хотеть из различать, если с одинаковыми строками связана разная мета-информация. Тогда при попадании в терминальную вершину можно осуществлять сброс пометки этой терминальной вершины, что сэкономит время на обновлении информации о вхождении образцов в текст. Тривиальным примером, в котором возникает ситуация долгой обработки, служит огромное множество образцов из одинаковых символов и текст только из этих символов.
 +
 
 +
== Поиск шаблонов с масками ==
 +
 
 +
{{Задача
 +
|definition = Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.<BR>
 +
}}
 +
Например, шаблон <tex>ab\varphi\varphi c\varphi</tex>, который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex>7</tex> строки <tex>xabvccababcax</tex>.
 +
 
 +
=== Алгоритм поиска ===
 +
 
 +
Для того чтобы найти все вхождения в текст заданного шаблона с масками <tex>Q</tex>, необходимо обнаружить вхождения в текст всех его безмасочных кусков.<BR>
 +
Пусть <tex>\{Q_1, \dots, Q_k \}</tex> {{---}} набор подстрок
 +
<tex>Q</tex>, разделенных масками, и пусть <tex>\{ l_1, \dots, l_k \}</tex> {{---}} их стартовые позиции в <tex>Q</tex>. Например, шаблон <tex>ab\varphi\varphi c\varphi</tex> содержит две подстроки без масок <tex>ab</tex> и <tex>c</tex> и их стартовые позиции соответственно <tex>1</tex> и <tex>5</tex>. Для алгоритма понадобится массив <tex>C</tex>. <tex>C[i]</tex> {{---}} количество встретившихся в тексте безмасочных подстрок шаблона, который начинается в тексте на позиции <tex>i</tex>. Тогда появление подстроки <tex>Q_i</tex> в тексте на позиции <tex>j</tex> будет означать возможное появление шаблона на позиции <tex>j - l_i + 1</tex>.<BR>
 +
# Используя алгоритм Ахо-Корасик, находим безмасочные подстроки шаблона <tex>Q</tex>: когда находим <tex>Q_i</tex> в тексте <tex>T</tex> на позиции <tex>j</tex>, увеличиваем на единицу <tex>C[j - l_i + 1]</tex>.<BR>
 +
# Каждое <tex>i</tex>, для которого <tex>C[i] = k</tex>, является стартовой позицией появления шаблона <tex>Q</tex> в тексте.<BR>
 +
Рассмотрим подстроку текста <tex>T[i \dots i+n-1]</tex>. Равенство <tex>C[i] = k</tex> будет означать, что подстроки текста <tex> T[i + l_1 \dots i + l_1 + |Q_1| - 1],  T[i + l_2 \dots i + l_2 + |Q_2| - 1]</tex> и так далее будут равны соответственно безмасочным подстрокам шаблона <tex>\{Q_1, \dots , Q_k \}</tex>. Остальная часть шаблона является масками, поэтому шаблон входит в текст на позиции <tex>i</tex>.<BR>
 +
Поиск подстрок заданного шаблона с помощью алгоритма Ахо-Корасик выполняется за время <tex>O(m+n+a)</tex>, где <tex>n</tex> {{---}} суммарная длина подстрок, то есть длина шаблона, <tex>m</tex> {{---}} длина текста, <tex>a</tex> {{---}} количество появлений подстрок шаблона. Далее просто надо пробежаться по массиву <tex>C</tex> и просмотреть значения ячеек за время <tex>O (m)</tex>.
 +
 
 +
==См. также==
 +
* [[Алгоритм Бойера-Мура]]
 +
* [[Алгоритм Кнута-Морриса-Пратта]]
 +
 
 +
== Источники информации ==
 +
*[http://e-maxx.ru/algo/aho_corasick MAXimal :: algo :: Алгоритм Ахо-Корасик]
 +
*[http://aho-corasick.narod.ru Сопоставление множеств и алгоритм Ахо-Корасик]
 +
*[http://codeforces.com/blog/entry/14854?locale=ru Codeforces :: Алгоритм Ахо-Корасик]
 +
*[https://habrahabr.ru/post/198682/ Habr :: Алгоритм Ахо-Корасик]
 +
*[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%90%D1%85%D0%BE_%E2%80%94_%D0%9A%D0%BE%D1%80%D0%B0%D1%81%D0%B8%D0%BA Wiki :: Алгоритм Ахо-Корасик]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Поиск подстроки в строке]]
 +
[[Категория: Точный поиск]]

Текущая версия на 19:42, 19 января 2020

Задача:
Дан набор строк в алфавите размера [math]k[/math] суммарной длины [math]m[/math]. Необходимо найти для каждой строки все ее вхождения в текст.


Алгоритм[править]

Шаг 1. Построение бора[править]

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

Пример построенного бора[править]

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

Шаг 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]. Функции перехода и суффиксные ссылки можно найти либо алгоритмом обхода в глубину с ленивыми вычислениями, либо с помощью алгоритма обхода в ширину.

Из определений выше можно заметить два следующих факта:

  • функция перехода определена через суффиксную ссылку, а суффиксная ссылка — через функию переходов;
  • для построения суффиксных ссылок небходимо знать информацию только выше по бору от текущей вершины до корня.

Это позволяет реализовать функции поиска переходов по символу и суффиксных ссылок ленивым образом при помощи взаимной рекурсии.

Пример автомата Ахо-Корасик[править]

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

Суффиксная ссылка для каждой вершины [math]u[/math] — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине [math]u[/math]. Единственный особый случай — корень бора: для удобства суффиксную ссылку из него проведём в себя же. Например, для вершины [math]5[/math] с соответствующей ей строкой [math]\textbf{she}[/math] максимальным подходящим суффиксом является строка [math]\textbf{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]up[/math] — сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам. Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут быть найдены при помощи ленивой рекурсии.

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

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

Пример реализации[править]

Ниже представлена реализация некоторых функций (используется ленивая рекурсия).
[math]k[/math] — размер алфавита.

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

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

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

Node getSuffLink(Node v):
    if v.suffLink == null                       // если суффиксная ссылка ещё не вычислена
       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 v.go[c] == null                           // если переход по символу 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 v.up == null                             // если сжатая суффиксная ссылка ещё не вычислена
        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 s, int patternNumber):
    Node cur = root
    for i = 0 to s.length - 1
        char c = s[i]
        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.pushBack(patternNumber)

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

fun processText(string t):   
    Node cur = root
    for i = 0 to t.length - 1 
        char c = t[i] - 'a'
        cur = getLink(cur, c)
        /* В этом месте кода должен выполняться переход по сжатой суффиксной ссылке getUp(cur). Для вершины,
           обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки
           и так до корня. */

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

Оптимизации[править]

Существует несколько оптимизаций данного алгоритма, направленных на случаи, когда нас интересует только первое вхождение образца в текст:

  1. Сброс сжатых суффиксных ссылок для посещённых вершин.
    Существенно ускорить работу алгоритма могут пометки о посещённости узла, то есть если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
  2. Сброс пометки терминальной вершины.
    В изначальном множестве образцов могут быть дублирующиеся строки. Мы можем хотеть из различать, если с одинаковыми строками связана разная мета-информация. Тогда при попадании в терминальную вершину можно осуществлять сброс пометки этой терминальной вершины, что сэкономит время на обновлении информации о вхождении образцов в текст. Тривиальным примером, в котором возникает ситуация долгой обработки, служит огромное множество образцов из одинаковых символов и текст только из этих символов.

Поиск шаблонов с масками[править]

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

Например, шаблон [math]ab\varphi\varphi c\varphi[/math], который содержит в себе три маски, встречается на позициях [math]2[/math] и [math]7[/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].

См. также[править]

Источники информации[править]