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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример реализации (ещё не весь))
(Пример реализации: (продолжение))
Строка 43: Строка 43:
  
 
== Пример реализации ==
 
== Пример реализации ==
Ниже представлена реализация на C++ некоторых функций (используется ленивая рекурсия).<br />
+
Ниже представлена реализация на C++ некоторых функций (используется ленивая рекурсия).<br /><br />
 
'''Структура вершины:'''
 
'''Структура вершины:'''
 
  struct Node {
 
  struct Node {
     Node* son[26];        // массив сыновей
+
     Node* son[26];        <font color=green>// массив сыновей</font>
     Node* go[26];        // массив переходов (запоминаем переходы в ленивой рекурсии)
+
     Node* go[26];        <font color=green>// массив переходов (запоминаем переходы в ленивой рекурсии)</font>
     Node* parent;        // вершина родитель
+
     Node* parent;        <font color=green>// вершина родитель</font>
     Node* suffLink;      // суффиксная ссылка (вычисляем в ленивой рекурсии)
+
     Node* suffLink;      <font color=green>// суффиксная ссылка (вычисляем в ленивой рекурсии)</font>
     Node* up;            // сжатая суффиксная ссылка
+
     Node* up;            <font color=green>// сжатая суффиксная ссылка</font>
     char charToParent;    // символ, ведущий к родителю
+
     char charToParent;    <font color=green>// символ, ведущий к родителю</font>
     bool leaf;            // флаг, является ли вершина терминалом
+
     bool leaf;            <font color=green>// флаг, является ли вершина терминалом</font>
     std::vector<int> leafPatternNumber;  // номера образцов, за которые отвечает терминал
+
     std::vector<int> leafPatternNumber;  <font color=green>// номера образцов, за которые отвечает терминал</font>
 
  };
 
  };
 
'''Функция, для вычисления суффиксной ссылки:'''
 
'''Функция, для вычисления суффиксной ссылки:'''
 
  Node* getSuffLink(Node* v) {
 
  Node* getSuffLink(Node* v) {
     if (!v->suffLink) {  // если суффиксная ссылка ещё не вычислена
+
     if (!v->suffLink) {  <font color=green>// если суффиксная ссылка ещё не вычислена</font>
 
         if (v == root || v->parent == root) {
 
         if (v == root || v->parent == root) {
 
             v->suffLink = root;
 
             v->suffLink = root;
Строка 65: Строка 65:
 
     }
 
     }
 
     return v->suffLink;
 
     return v->suffLink;
 +
}
 +
'''Функция, для вычисления перехода:'''
 +
Node* getGo(Node* v, char c) {
 +
    if (!v->go[c]) {      <font color=green>// если переход по символу c ещё не вычислен</font>
 +
        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) {        <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font>
 +
        if (getSuffLink(v)->leaf) {
 +
            v->up = getSuffLink(v);
 +
        } else if (getSuffLink(v) == root) {
 +
            v->up = 0;
 +
        } else {
 +
            v->up = getUp(getSuffLink(v));
 +
        }
 +
    }
 +
    return v->up;
 
  }
 
  }

Версия 18:23, 29 марта 2011

Задача алгоритма

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

Шаг 1

Строим бор из образцов. См. Бор.
Построение выполняется за время [math]O(m)[/math], где [math]m[/math] - суммарная длина образцов.

Пример построенного бора

Бор для набора образцов {he, she, his, hers}:
Aho-corasick1.jpg

Шаг 2

Превращаем бор в автомат.
Узлы бора становятся состояниями автомата; корень - начальное состояние.
Узлы бора, в которых заканчиваются образцы, становятся терминалами.

Для переходов по автомату заведём в узлах несколько функций:
1) [math]parent(u)[/math] - возвращает родителя вершины [math]u[/math];
2) [math]\pi(u) = \delta(\pi(parent(u)), c)[/math] - суффиксная ссылка; здесь [math]u[/math] - сын [math]parent(u)[/math] по символу [math]c[/math];
3) [math]\delta(u, c) = \begin{cases} v\text{, if $v$ is son 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]. Обозначение: [math][u][/math] - слово, приводящее в вершину [math]u[/math] в боре.
Функции перехода и суффиксные ссылки можно найти либо алгоритмом обхода в глубину с ленивыми вычислениями, либо с помощью алгоритма обхода в ширину.

Пример автомата Ахо-Корасик

Aho-corasick2.jpg
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.

Шаг 3

Построение сжатых суффиксных ссылок.
[math]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}[/math] - сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам.

Сжатые суффиксные ссылки могут отыскиваться при помощи ленивой рекурсии.

Использование автомата

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

Пример реализации

Ниже представлена реализация на C++ некоторых функций (используется ленивая рекурсия).

Структура вершины:

struct Node {
    Node* son[26];        // массив сыновей
    Node* go[26];         // массив переходов (запоминаем переходы в ленивой рекурсии)
    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 = 0;
        } else {
            v->up = getUp(getSuffLink(v));
        }
    }
    return v->up;
}