Изменения

== {{Задача алгоритма |definition ==Найти для каждого образца из заданного множества образцов (размером Дан набор строк в алфавите размера <tex>k</tex>) все его вхождения в текст за время суммарной длины <tex>O(m+n+a)</tex>, где <tex>m</tex> {{---. Необходимо найти для каждой строки все ее вхождения в текст.}} суммарная длина образцов, <tex>n</tex> {{---}} длина текста, <tex>a</tex> {{---}} размер ответа (количество пар). В худшем случае <tex>a=nk</tex>, но на практике он встречается редко.

==Алгоритм===== Шаг 1 . Построение бора ===Строим [[Бор|бор]] из образцовстрок.<br />Построение выполняется за время <tex>O(m)</tex>, где <tex>m</tex> {{---}} суммарная длина образцовстрок.

==== Пример построенного бора ====Бор для набора образцов строк <tex>\{ \textbf{he}, \ \textbf{she}, \ \textbf{his}, \ \textbf{hers}\}</tex>:<br />[[Файл:Aho-corasick1Бор.jpg‎]]

=== Шаг 2 . Преобразование бора ===Превращаем бор Обозначим за <tex>[u]</tex> слово, приводящее в вершину <tex>u</tex> в автоматборе.<br />Узлы бора становятся состояниями можно понимать как состояния [[Детерминированные_конечные_автоматы | автомата; ]], а корень {{---}} как начальное состояние.<br />Узлы бора, в которых заканчиваются образцыстроки, становятся терминаламитерминальными.<br /><br />

1) *<tex>\mathrm{parent}(u)</tex> {{---}} возвращает родителя вершины <tex>u</tex>;<br />2) *<tex>\pi(u) = \delta(\pi(\mathrm{parent}(u)), c)</tex> {{---}} '''суффиксная ссылка; здесь ''', и существует переход из <tex>\mathrm{parent}(u)</tex> {{---}} сын в <tex>parent(u)</tex> по символу <tex>c</tex>;<br />3) *<tex>\delta(u, c) =

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}</tex> {{---}} функция перехода.Мы можем понимать рёбра бора как переходы в автомате по соответствующей букве. Однако одними только рёбрами бора нельзя ограничиваться. Если мы пытаемся выполнить переход по какой-либо букве, а соответствующего ребра в боре нет, то мы тем не менее должны перейти в какое-то состояние. Для этого нам и нужны суффиксные ссылки.<br /><br />Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> {{---}} максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>. Обозначение: <tex>[u]</tex> {{---}} слово, приводящее в вершину <tex>u</tex> в боре.<br />Функции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину ]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]]. Из определений выше можно заметить два следующих факта:* функция перехода определена через суффиксную ссылку, а суффиксная ссылка {{---}} через функию переходов;* для построения суффиксных ссылок небходимо знать информацию только выше по бору от текущей вершины до корня.Это позволяет реализовать функции поиска переходов по символу и суффиксных ссылок ленивым образом при помощи взаимной рекурсии. ==== Пример автомата Ахо-Корасик ====[[Файл:Aho-corasick2axo.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 ==. Построение сжатых суффиксных ссылок===При построении автомата может возникнуть такая ситуация, что ветвление есть не на каждом символе. Тогда можно маленький бамбук заменить одним ребром. Для этого и используются сжатые суффиксные ссылки.<br /> 

\pi(u), &\text{, if $\pi(u)$ is terminal;}\\ \emptysetvarnothing,&\text{, if $\pi(u)$ is root;}\\ up(\pi(u)), &\text{, else.} \end{cases}</tex>  где <tex>up</tex> {{---}} сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам.<br /><br />Сжатые Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут отыскиваться быть найдены при помощи ленивой рекурсии.

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

Ниже представлена реализация на C++ некоторых функций (используется ленивая рекурсия).<br /><tex>k<br /tex>{{---}} размер алфавита. 

'''struct ''' Node {: '''Node* ''' son[SZk]; <font color=green>// массив сыновей; SZ - это размер алфавита</font> '''Node* ''' go[SZk]; <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 leaf; ''' isLeaf <font color=green>// флаг, является ли вершина терминалом</font> std::'''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 = getGogetLink(getSuffLink(v->.parent), v->.charToParent); } } '''return ''' v->.suffLink; }'''Функция, для вычисления перехода:''' '''Node* getGo''' 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] == root) ? root : getGogetLink(getSuffLink(v), c); } } '''return ''' v->.go[c]; }'''Функция, для вычисления сжатой суффиксной ссылки:''' '''Node* ''' getUp('''Node* ''' v) {: '''if (!''' v->.up) { == ''null'' <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font> '''if (''' getSuffLink(v)->leaf) {.isLeaf v->.up = getSuffLink(v); } '''else ''' '''if (''' getSuffLink(v) == root) { v->.up = root; } '''else {''' v->.up = getUp(getSuffLink(v)); } } '''return ''' v->.up; }'''Функция, для добавление образца добавления строки в бор:''' void '''fun''' addString(std::'''string const& ''' s, '''int ''' patternNumber) {: '''Node* ''' cur = root; '''for (int ''' i = 0; i < '''to''' s.length(); ++i) {- 1 '''char ''' c = s[i] - ''a'; if (''' cur->.son[c] == 0) { cur->.son[c] = new Node;

cur->.son[c]->.suffLink = 0; cur->.son[c]->.up = 0; cur->.son[c]->.parent = cur; cur->.son[c]->.charToParent = c; cur->.son[c]->leaf .isLeaf = ''false; }'' cur = cur->.son[c]; } cur->leaf .isLeaf = ''true;'' cur->.leafPatternNumber.push_backpushBack(patternNumber); }'''Функция, для процессинга текста (поиск, встречается образец строка или нет):''' void '''fun''' processText(std::'''string const& ''' t, std:):vector<bool>& found) { <font color=green>// found - это вектор, длина которого равна количеству образцов</font> found.assign(w, false); <font color=green>// w - количество образцов</font> '''Node* ''' cur = root; '''for (int ''' i = 0; i < '''to''' t.length(); ++i) {- 1 '''char ''' c = t[i] - 'a'; cur = getGogetLink(cur, c); for (int j = 0; j < cur->leafPatternNumber.size(); ++j) { found[cur->leafPatternNumber[j]] = true; }

и так до корня. Хорошо ускорит программу сброс сжатых суффиксных ссылок для посещённых вершин. */</font> } }

 {{Задача|definition === Постановка задачи ===Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ.Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.<BR>}}Например, шаблон <tex>ab\varphi\varphi c\varphi</tex>, который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex>87</tex> строки <tex>xabvccababcax</tex>. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.<BR> 

Пусть <tex>\{</tex><tex>Q_1</tex>, ...\dots, <tex>Q_k</tex><tex>\}</tex> {{---}} набор подстрок<tex>Q</tex>, разделенных масками, и пусть <tex>\{ l_1</tex>, ...\dots,<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>QT[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>k\{Q_1, \dots , Q_k \}</tex> раз. Остальная часть шаблона является масками, что будет означать появление шаблона поэтому шаблон входит в тексте текст на позиции этой ячейки<tex>i</tex>.<BR>

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