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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм поиска)
м (rollbackEdits.php mass rollback)
 
(не показаны 92 промежуточные версии 10 участников)
Строка 1: Строка 1:
== Задача алгоритма ==
+
{{Задача
Найти для каждого образца из заданного множества образцов (размером <tex>k</tex>) все его вхождения в текст за время <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> {{---}} суммарная длина строк.
  
=== Пример построенного бора ===
+
====Пример построенного бора====
Бор для набора образцов <tex>\{he, she, his, hers\}</tex>:<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 />
*<tex>parent(u)</tex> {{---}} возвращает родителя вершины <tex>u</tex>;<br />
+
*<tex>\mathrm{parent}(u)</tex> {{---}} возвращает родителя вершины <tex>u</tex>;<br />
*<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 />
 
*<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;}\\
     root\text{, if $u$ is root and $u$ has no child 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>.
=== Пример автомата Ахо-Корасик ===
+
Функции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]].
[[Файл: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 />
''Примечание.'' Если требуется найти только первое вхождение образца в текст, то существенно ускорить работу алгоритма могут пометки о посещённости узла, т.е. если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
 
  
 
== Пример реализации ==
 
== Пример реализации ==
Ниже представлена реализация на C++ некоторых функций (используется ленивая рекурсия).<br /><br />
+
Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br />
 +
<tex>k</tex> {{---}} размер алфавита.
 +
 
 
'''Структура вершины:'''
 
'''Структура вершины:'''
  struct Node {
+
  '''struct''' Node:
     Node* son[SZ];        <font color=green>// массив сыновей; SZ - это размер алфавита</font>
+
     '''Node''' son[k]                                 <font color=green>// массив сыновей</font>
     Node* go[SZ];        <font color=green>// массив переходов (запоминаем переходы в ленивой рекурсии)</font>
+
     '''Node''' go[k]                                 <font color=green>// массив переходов (запоминаем переходы в ленивой рекурсии), используемый для вычисления суффиксных ссылок</font>
     Node* parent;        <font color=green>// вершина родитель</font>
+
     '''Node''' parent                                 <font color=green>// вершина родитель</font>
     Node* suffLink;      <font color=green>// суффиксная ссылка (вычисляем в ленивой рекурсии)</font>
+
     '''Node''' suffLink                               <font color=green>// суффиксная ссылка (вычисляем в ленивой рекурсии)</font>
     Node* up;            <font color=green>// сжатая суффиксная ссылка</font>
+
     '''Node''' up                                     <font color=green>// сжатая суффиксная ссылка</font>
     char charToParent;    <font color=green>// символ, ведущий к родителю</font>
+
     '''char''' charToParent                           <font color=green>// символ, ведущий к родителю</font>
     bool leaf;            <font color=green>// флаг, является ли вершина терминалом</font>
+
     '''bool''' isLeaf                                <font color=green>// флаг, является ли вершина терминалом</font>
     std::vector<int> leafPatternNumber<font color=green>// номера образцов, за которые отвечает терминал</font>
+
     '''vector<int>''' leafPatternNumber               <font color=green>// номера строк, за которые отвечает терминал</font>
};
+
 
'''Функция, для вычисления суффиксной ссылки:'''
+
'''Функция для вычисления суффиксной ссылки:'''
  Node* getSuffLink(Node* v) {
+
  '''Node''' getSuffLink('''Node''' v):
     if (!v->suffLink) {  <font color=green>// если суффиксная ссылка ещё не вычислена</font>
+
     '''if''' v.suffLink == ''null''                      <font color=green>// если суффиксная ссылка ещё не вычислена</font>
        if (v == root || v->parent == root) {
+
        '''if''' v == root '''or''' v.parent == root
             v->suffLink = root;
+
             v.suffLink = root
        } else {
+
        '''else'''
             v->suffLink = getGo(getSuffLink(v->parent), v->charToParent);
+
             v.suffLink = getLink(getSuffLink(v.parent), v.charToParent)
        }
+
     '''return''' v.suffLink
    }
+
   
     return v->suffLink;
+
'''Функция для вычисления перехода:'''
  }
+
  '''Node''' getLink('''Node''' v, '''char''' c):
'''Функция, для вычисления перехода:'''
+
    '''if''' v.go[c] == ''null''                          <font color=green>// если переход по символу c ещё не вычислен</font>
  Node* getGo(Node* v, char c) {
+
         '''if''' v.son[c]
    if (!v->go[c]) {      <font color=green>// если переход по символу c ещё не вычислен</font>
+
             v.go[c] = v.son[c]
         if (v->son[c]) {
+
         '''else''' '''if''' v == root
             v->go[c] = v->son[c];
+
             v.go[c] = root
         } else {
+
        '''else'''
             v->go[c] = (v == root) ? root : getGo(getSuffLink(v), c);
+
            v.go[c] = getLink(getSuffLink(v), c)
        }
+
     '''return''' v.go[c]
    }
+
   
     return v->go[c];
+
'''Функция для вычисления сжатой суффиксной ссылки:'''
  }
+
  '''Node''' getUp('''Node''' v):
'''Функция, для вычисления сжатой суффиксной ссылки:'''
+
     '''if''' v.up == ''null''                            <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font>
  Node* getUp(Node* v) {
+
         '''if''' getSuffLink(v).isLeaf
     if (!v->up) {        <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font>
+
             v.up = getSuffLink(v)
         if (getSuffLink(v)->leaf) {
+
         '''else''' '''if''' getSuffLink(v) == root
             v->up = getSuffLink(v);
+
             v.up = root
         } else if (getSuffLink(v) == root) {
+
         '''else'''
             v->up = root;
+
             v.up = getUp(getSuffLink(v))
         } else {
+
     '''return''' v.up
             v->up = getUp(getSuffLink(v));
+
 
        }
+
'''Функция для добавления строки в бор:'''
    }
+
  '''fun''' addString('''string''' s, '''int''' patternNumber):
     return v->up;
+
     '''Node''' cur = root
}
+
     '''for''' i = 0 '''to''' s.length - 1
'''Функция, для добавление образца в бор:'''
+
         '''char''' c = s[i]
  void addString(std::string const& s, int patternNumber) {
+
        '''if''' cur.son[c] == 0
     Node* cur = root;
+
             cur.son[c] = Node
     for (int i = 0; i < s.length(); ++i) {
 
         char c = s[i] - 'a';
 
        if (cur->son[c] == 0) {
 
             cur->son[c] = new Node;
 
 
             <font color=green>/* здесь также нужно обнулить указатели на переходы и сыновей */</font>
 
             <font color=green>/* здесь также нужно обнулить указатели на переходы и сыновей */</font>
             cur->son[c]->suffLink = 0;
+
             cur.son[c].suffLink = 0
             cur->son[c]->up = 0;
+
             cur.son[c].up = 0
             cur->son[c]->parent = cur;
+
             cur.son[c].parent = cur
             cur->son[c]->charToParent = c;
+
             cur.son[c].charToParent = c
             cur->son[c]->leaf = false;
+
             cur.son[c].isLeaf = ''false''
        }
+
         cur = cur.son[c]
         cur = cur->son[c];
+
     cur.isLeaf = ''true''
    }
+
     cur.leafPatternNumber.pushBack(patternNumber)
     cur->leaf = true;
+
'''Функция для процессинга текста (поиск, встречается строка или нет):'''
     cur->leafPatternNumber.push_back(patternNumber);
+
  '''fun''' processText('''string''' t):   
}
+
     '''Node''' cur = root
'''Функция, для процессинга текста (поиск, встречается образец или нет):'''
+
     '''for''' i = 0 '''to''' t.length - 1
  void processText(std::string const& t, std::vector<bool>& found) {   <font color=green>// found - это вектор, длина которого равна количеству образцов</font>
+
         '''char''' c = t[i] - 'a'
    found.assign(w, false);  <font color=green>// w - количество образцов</font>
+
         cur = getLink(cur, c)
     Node* cur = root;
 
     for (int i = 0; i < t.length(); ++i) {
 
         char c = t[i] - 'a';
 
         cur = getGo(cur, c);
 
        for (int j = 0; j < cur->leafPatternNumber.size(); ++j) {
 
            found[cur->leafPatternNumber[j]] = true;
 
        }
 
 
         <font color=green>/* В этом месте кода должен выполняться переход по '''сжатой''' суффиксной ссылке getUp(cur). Для вершины,
 
         <font color=green>/* В этом месте кода должен выполняться переход по '''сжатой''' суффиксной ссылке getUp(cur). Для вершины,
 
             обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки
 
             обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки
             и так до корня. Хорошо ускорит программу сброс сжатых суффиксных ссылок для посещённых вершин. */</font>
+
             и так до корня. */</font>
    }
 
}
 
 
Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет.
 
Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет.
  
 +
== Оптимизации ==
 +
Существует несколько оптимизаций данного алгоритма, направленных на случаи, когда нас интересует только первое вхождение образца в текст:
 +
 +
# '''Сброс сжатых суффиксных ссылок для посещённых вершин.'''
 +
#: Существенно ускорить работу алгоритма могут пометки о посещённости узла, то есть если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
 +
# '''Сброс пометки терминальной вершины.'''
 +
#: В изначальном множестве образцов могут быть дублирующиеся строки. Мы можем хотеть из различать, если с одинаковыми строками связана разная мета-информация. Тогда при попадании в терминальную вершину можно осуществлять сброс пометки этой терминальной вершины, что сэкономит время на обновлении информации о вхождении образцов в текст. Тривиальным примером, в котором возникает ситуация долгой обработки, служит огромное множество образцов из одинаковых символов и текст только из этих символов.
  
 
== Поиск шаблонов с масками ==
 
== Поиск шаблонов с масками ==
=== Постановка задачи ===
+
 
Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ.Например, шаблон <tex>ab\varphi\varphi c\varphi</tex>, который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex>8</tex> строки <tex>xabvccababcax</tex>. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.<BR>
+
{{Задача
 +
|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</tex>, необходимо обнаружить вхождения в текст всех его безмасочных кусков.<BR>
Пусть <tex>\{</tex><tex>Q_1</tex>, ..., <tex>Q_k</tex><tex>\}</tex> {{---}} набор подстрок
+
Пусть <tex>\{Q_1, \dots, Q_k \}</tex> {{---}} набор подстрок
<tex>Q</tex>, разделенных масками, и пусть <tex>l_1</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>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>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>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>\{</tex><tex>Q_1</tex>, ..., <tex>Q_k</tex><tex>\}</tex>. Остальная часть шаблона является масками, поэтому шаблон входит в текст на позиции <tex>i</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>.
 
Поиск подстрок заданного шаблона с помощью алгоритма Ахо-Корасик выполняется за время <tex>O(m+n+a)</tex>, где <tex>n</tex> {{---}} суммарная длина подстрок, то есть длина шаблона, <tex>m</tex> {{---}} длина текста, <tex>a</tex> {{---}} количество появлений подстрок шаблона. Далее просто надо пробежаться по массиву <tex>C</tex> и просмотреть значения ячеек за время <tex>O (m)</tex>.
  
Строка 145: Строка 157:
 
* [[Алгоритм Кнута-Морриса-Пратта]]
 
* [[Алгоритм Кнута-Морриса-Пратта]]
  
== Источники ==
+
== Источники информации ==
 
*[http://e-maxx.ru/algo/aho_corasick MAXimal :: algo :: Алгоритм Ахо-Корасик]
 
*[http://e-maxx.ru/algo/aho_corasick MAXimal :: algo :: Алгоритм Ахо-Корасик]
 
*[http://aho-corasick.narod.ru Сопоставление множеств и алгоритм Ахо-Корасик]
 
*[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:18, 4 сентября 2022

Задача:
Дан набор строк в алфавите размера [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].

См. также

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