Алгоритм Ахо-Корасик

2014-06-10T10:28:42Z

217.66.159.55:

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

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

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

== Шаг 2 ==
Превращаем бор в автомат. 
Узлы бора становятся состояниями автомата; корень {{---}} начальное состояние. 
Узлы бора, в которых заканчиваются образцы, становятся терминалами. 
Для переходов по автомату заведём в узлах несколько функций: 
1) <tex>parent(u)</tex> {{---}} возвращает родителя вершины <tex>u</tex>; 
2) <tex>\pi(u) = \delta(\pi(parent(u)), c)</tex> {{---}} суффиксная ссылка; здесь <tex>u</tex> {{---}} сын <tex>parent(u)</tex> по символу <tex>c</tex>; 
3) <tex>\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}</tex> {{---}} функция перехода. 
Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> {{---}} максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>. Обозначение: <tex>[u]</tex> {{---}} слово, приводящее в вершину <tex>u</tex> в боре. 
Функции перехода и суффиксные ссылки можно найти либо алгоритмом обхода в глубину с ленивыми вычислениями, либо с помощью алгоритма обхода в ширину.
=== Пример автомата Ахо-Корасик ===
[[Файл:Aho-corasick2.jpg]] 
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.

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

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

== Пример реализации ==
Ниже представлена реализация на C++ некоторых функций (используется ленивая рекурсия). 
'''Структура вершины:'''
struct Node {
Node* son[SZ]; // массив сыновей; SZ - это размер алфавита
Node* go[SZ]; // массив переходов (запоминаем переходы в ленивой рекурсии)
Node* parent; // вершина родитель
Node* suffLink; // суффиксная ссылка (вычисляем в ленивой рекурсии)
Node* up; // сжатая суффиксная ссылка
char charToParent; // символ, ведущий к родителю
bool leaf; // флаг, является ли вершина терминалом
std::vector<int> leafPatternNumber; // номера образцов, за которые отвечает терминал
};
'''Функция, для вычисления суффиксной ссылки:'''
Node* getSuffLink(Node* v) {
if (!v->suffLink) { // если суффиксная ссылка ещё не вычислена
if (v == root || v->parent == root) {
v->suffLink = root;
} else {
v->suffLink = getGo(getSuffLink(v->parent), v->charToParent);
}
}
return v->suffLink;
}
'''Функция, для вычисления перехода:'''
Node* getGo(Node* v, char c) {
if (!v->go[c]) { // если переход по символу c ещё не вычислен
if (v->son[c]) {
v->go[c] = v->son[c];
} else {
v->go[c] = (v == root) ? root : getGo(getSuffLink(v), c);
}
}
return v->go[c];
}
'''Функция, для вычисления сжатой суффиксной ссылки:'''
Node* getUp(Node* v) {
if (!v->up) { // если сжатая суффиксная ссылка ещё не вычислена
if (getSuffLink(v)->leaf) {
v->up = getSuffLink(v);
} else if (getSuffLink(v) == root) {
v->up = root;
} else {
v->up = getUp(getSuffLink(v));
}
}
return v->up;
}
'''Функция, для добавление образца в бор:'''
void addString(std::string const& s, int patternNumber) {
Node* cur = root;
for (int i = 0; i < s.length(); ++i) {
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 = false;
}
cur = cur->son[c];
}
cur->leaf = true;
cur->leafPatternNumber.push_back(patternNumber);
}
'''Функция, для процессинга текста (поиск, встречается образец или нет):'''
void processText(std::string const& t, std::vector<bool>& found) { // found - это вектор, длина которого равна количеству образцов
found.assign(w, false); // w - количество образцов
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;
}
/* В этом месте кода должен выполняться переход по '''сжатой''' суффиксной ссылке getUp(cur). Для вершины,
обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки
и так до корня. Хорошо ускорит программу сброс сжатых суффиксных ссылок для посещённых вершин. */
}
}
Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет.

== Поиск шаблонов с масками ==
Пусть <tex>\phi</tex> {{---}} маска, обозначающая любой одиночный символ. 
Например, шаблон <tex>ab\phi\phi c\phi</tex> встречается на позициях 2 и 8 строки
<tex>xabvccababcax</tex>. 
Если количество <tex>\phi</tex> ограничено сверху константой, то шаблоны с
масками могут быть выявлены за линейное время. Для этого надо обнаружить
безмасочные куски шаблона <tex>Q</tex>: 
Пусть {<tex>Q_1</tex>, ..., <tex>Q_k</tex>} {{---}} набор подстрок
<tex>Q</tex>, разделенных масками, и пусть <tex>l_1</tex>, ...,
<tex>l_k</tex> {{---}} их стартовые позиции в <tex>Q</tex>. 
1. <tex>\forall i = 1 \ldots m: C[i] = 0 </tex>, где <tex>m</tex> {{---}} длина текста. 
2. Используя АК, находим подстроки <tex>Q</tex>: когда находим <tex>Q_i</tex>
в тексте T на позиции <tex>j</tex>, увеличиваем на единицу <tex>C[j - l_i + 1]</tex>. 
3. Каждое <tex>i</tex>, для которого <tex>C[i] = k</tex>, является
стартовой позицией появления шаблона <tex>Q</tex>.

== Источники ==
* http://e-maxx.ru/algo/aho_corasick
* http://aho-corasick.narod.ru/

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Поиск подстроки в строке]]

Викиконспекты - Вклад участника [ru]

Алгоритм Ахо-Корасик