1632
правки
Изменения
м
'''else'''
'''else''' '''if''' v == root
'''else'''
'''else''' '''if''' getSuffLink(v) == root
'''else'''
'''for''' j = 0 '''to''' cur.leafPatternNumber.size - 1
found[cur.leafPatternNumber[j]] = ''true''
rollbackEdits.php mass rollback
{{Задача
|definition = Дан набор строк в алфавите размера <tex>k</tex> суммарной длины <tex>m</tex>. Найти Необходимо найти для каждой строки все ее вхождения в текст за время <tex>O(m)</tex> и <tex>O(mk)</tex> памяти.
}}
====Пример построенного бора====
Бор для набора строк <tex> \{ \textbf{he}, \ \textbf{she}, \ \textbf{his}, \ \textbf{hers}\} </tex>:<br />
[[Файл:Бор.jpg]]
=== Шаг 2. Преобразование бора. ==='''Обозначения''': Обозначим за <tex>[u]</tex> {{---}} слово, приводящее в вершину <tex>u</tex> в боре.<br />Узлы бора можно понимать как состояния [[Детерминированные_конечные_автоматы | автомата]], а корень как начальное состояние.<br />Узлы бора, в которых заканчиваются строкстроки, становятся терминаламитерминальными.<br />
Для переходов по автомату заведём в узлах несколько функций:<br />
*<tex>\mathrm{parent}(u)</tex> {{---}} возвращает родителя вершины <tex>u</tex>;<br />
*<tex>\pi(u) = \delta(\pi(\mathrm{parent}(u)), c)</tex> {{---}} '''суффиксная ссылка; здесь ''', и существует переход из <tex>\mathrm{parent}(u)</tex> {{---}} сын в <tex>\mathrm{parent}(u)</tex> по символу <tex>c</tex>;<br />
*<tex>\delta(u, c) =
\begin{cases}
\delta(\pi(u), c), &\text{else.}
\end{cases}</tex> {{---}} функция перехода.
Мы можем понимать рёбра бора как переходы в автомате по соответствующей букве. Однако одними только рёбрами бора нельзя ограничиваться. Если мы пытаемся выполнить переход по какой-либо букве, а соответствующего ребра в боре нет, то мы тем не менее должны перейти в какое-то состояние. Для этого нам и нужны суффиксные ссылки.
<br> Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> {{---}} максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>.
Функции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]].
Из определений выше можно заметить два следующих факта:
* функция перехода определена через суффиксную ссылку, а суффиксная ссылка {{---}} через функию переходов;
* для построения суффиксных ссылок небходимо знать информацию только выше по бору от текущей вершины до корня.
Это позволяет реализовать функции поиска переходов по символу и суффиксных ссылок ленивым образом при помощи взаимной рекурсии.
==== Пример автомата Ахо-Корасик ====
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.
Суффиксная ссылка для каждой вершины <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. Построение сжатых суффиксных ссылок. ===При построении автомата может возникнуть такая ситуация, что ветвление есть не на каждом символе. Тогда можно маленький бамбук заменить одним ребром. Для этого и используются сжатые суффиксные ссылки.
<tex>up(u) =
\begin{cases}
\varnothing,&\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 />''Примечание.'' Если требуется найти только первое вхождение строки в текст, то существенно ускорить работу алгоритма могут пометки о посещённости узла, т.е. если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
== Пример реализации ==
Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br /><tex>k<br /tex>{{---}} размер алфавита.
'''Структура вершины:'''
'''struct''' Node:
'''Node''' son[k] <font color=green>// массив сыновей; k - это размер алфавита</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 == '''not'null'' v.suffLink <font color=green>// если суффиксная ссылка ещё не вычислена</font>
'''if''' v == root '''or''' v.parent == root
v.suffLink = root
v.suffLink = getLink(getSuffLink(v.parent), v.charToParent)
'''return''' v.suffLink
'''Функция, для вычисления перехода:'''
'''Node''' getLink('''Node''' v, '''char''' c):
'''if''' '''not''' v.go[c] == ''null'' <font color=green>// если переход по символу c ещё не вычислен</font>
'''if''' v.son[c]
v.go[c] = v.son[c]
v.go[c] = root
v.go[c] = getLink(getSuffLink(v), c)
'''return''' v.go[c]
'''Функция, для вычисления сжатой суффиксной ссылки:'''
'''Node''' getUp('''Node''' v):
'''if''' v.up == '''not'null'' v.up <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font>
'''if''' getSuffLink(v).isLeaf
v.up = getSuffLink(v)
v.up = root
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 = cur.son[c]
cur.isLeaf = ''true''
cur.leafPatternNumber.push_backpushBack(patternNumber)'''Функция, для процессинга текста (поиск, встречается строка или нет):''' '''fun''' processText('''string const&''' t, '''vector<bool>&''' found): <font color=green>// found - это вектор, длина которого равна количеству строк</font> found.assign(w, ''false'') <font color=green>// w - количество строк</font>
'''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>87</tex> строки <tex>xabvccababcax</tex>.
=== Алгоритм поиска ===
