Редактирование: Алгоритм Ахо-Корасик

Перейти к: навигация, поиск

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
{{Задача
+
== Задача алгоритма ==
|definition = Дан набор строк в алфавите размера <tex>k</tex> суммарной длины <tex>m</tex>. Необходимо найти для каждой строки все ее вхождения в текст.
+
Найти для каждого образца из заданного множества образцов все его вхождения в текст за время <tex>O(m+n+a)</tex>, где <tex>m</tex> - суммарная длина образцов, <tex>n</tex> - длина текста, <tex>a</tex> - размер ответа (количество пар). В худшем случае <tex>a=nk</tex>, но он случается редко.
}}
 
  
==Алгоритм==
+
== Шаг 1 ==
=== Шаг 1. Построение бора ===
+
Строим бор из образцов. См. [[Бор]].<br/>
Строим [[Бор|бор]] из строк.<br />
+
Построение выполняется за время <tex>O(m)</tex>, где <tex>m</tex> - суммарная длина образцов.
Построение выполняется за время <tex>O(m)</tex>, где <tex>m</tex> {{---}} суммарная длина строк.
 
  
====Пример построенного бора====
+
== Шаг 2 ==
Бор для набора строк <tex> \{ \textbf{he},\ \textbf{she},\ \textbf{his},\ \textbf{hers}\} </tex>:<br />
+
Превращаем бор в автомат.<br />
[[Файл:Бор.jpg‎]]
+
Узлы бора становятся состояниями автомата; корень - начальное состояние.<br />
 
+
Узлы бора, в которых заканчиваются образцы, становятся терминалами.<br /><br />
=== Шаг 2. Преобразование бора ===
 
Обозначим за <tex>[u]</tex> слово, приводящее в вершину <tex>u</tex> в боре.<br />
 
Узлы бора можно понимать как состояния [[Детерминированные_конечные_автоматы | автомата]], а корень как начальное состояние.<br />
 
Узлы бора, в которых заканчиваются строки, становятся терминальными.<br />
 
 
Для переходов по автомату заведём в узлах несколько функций:<br />
 
Для переходов по автомату заведём в узлах несколько функций:<br />
*<tex>\mathrm{parent}(u)</tex> {{---}} возвращает родителя вершины <tex>u</tex>;<br />
+
1) <tex>parent(u)</tex> - возвращает родителя вершины <tex>u</tex>;<br />
*<tex>\pi(u) = \delta(\pi(\mathrm{parent}(u)), c)</tex> {{---}} '''суффиксная ссылка''', и существует переход из  <tex>\mathrm{parent}(u)</tex> в <tex>u</tex> по символу <tex>c</tex>;<br />
+
2) <tex>\pi(u) = \delta(\pi(parent(u)), c)</tex> - суффиксная ссылка; здесь <tex>u</tex> - сын <tex>parent(u)</tex> по символу <tex>c</tex>;<br />
*<tex>\delta(u, c) =  
+
3) <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;}\\
    root,              &\text{if $u$ is root and $u$ has no child by symbol $c$ in trie}\\
+
     \delta(\pi(u), c)\text{, else.}
     \delta(\pi(u), c), &\text{else.}
+
   \end{cases}</tex> - функция перехода.<br /><br />
   \end{cases}</tex> {{---}} функция перехода.
+
Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> - максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>. Обозначение: <tex>[u]</tex> - слово, приводящее в вершину <tex>u</tex> в боре.<br />
Мы можем понимать рёбра бора как переходы в автомате по соответствующей букве. Однако одними только рёбрами бора нельзя ограничиваться. Если мы пытаемся выполнить переход по какой-либо букве, а соответствующего ребра в боре нет, то мы тем не менее должны перейти в какое-то состояние. Для этого нам и нужны суффиксные ссылки.
+
Функции перехода и суффиксные ссылки можно найти либо алгоритмом обхода в глубину с ленивыми вычислениями, либо с помощью алгоритма обхода в ширину.
<br> Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> {{---}} максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>.
 
Функции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]].
 
 
 
Из определений выше можно заметить два следующих факта:
 
* функция перехода определена через суффиксную ссылку, а суффиксная ссылка {{---}} через функию переходов;
 
* для построения суффиксных ссылок небходимо знать информацию только выше по бору от текущей вершины до корня.
 
Это позволяет реализовать функции поиска переходов по символу и суффиксных ссылок ленивым образом при помощи взаимной рекурсии.
 
 
 
==== Пример автомата Ахо-Корасик ====
 
[[Файл:axo.jpg]]<br />
 
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.
 
 
 
Суффиксная ссылка для каждой вершины <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>.
 
 
 
===Шаг 3. Построение сжатых суффиксных ссылок ===
 
При построении автомата может возникнуть такая ситуация, что ветвление есть не на каждом символе. Тогда можно маленький бамбук заменить одним ребром. Для этого и используются сжатые суффиксные ссылки.
 
  
 +
== Шаг 3 ==
 +
Построение сжатых суффиксных ссылок.<br />
 
<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;}\\
     \varnothing,&\text{if $\pi(u)$ is root;}\\
+
     \emptyset\text{, if $\pi(u)$ is root;}\\
     up(\pi(u)), &\text{else.}
+
     up(\pi(u))\text{, else.}
   \end{cases}</tex>  
+
   \end{cases}</tex> - сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам.<br /><br />
 
+
Сжатые суффиксные ссылки могут отыскиваться при помощи ленивой рекурсии.
где <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 :: Алгоритм Ахо-Корасик]
 
 
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Поиск подстроки в строке]]
 
[[Категория: Точный поиск]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: