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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм Ахо — Корасик — алгоритм поиска подстроки, разработанный Альфредом Ахо и Маргарет Корасик. Алгоритм реализует поиск множества подстрок из словаря в данной строке.

Принцип работы[править | править вики-текст]

Недетерминированный автомат для словаря {a, ab, bc, bca, c, caa}. Серые вершины промежуточные, белые конечные. Синие стрелки — суффиксные ссылки, зелёные — конечные.

Алгоритм строит конечный автомат, которому затем передаёт строку поиска. Автомат получает по очереди все символы строки и переходит по соответствующим рёбрам. Если автомат пришёл в конечное положение, соответствующая строка словаря присутствует в строке поиска.

Несколько строк поиска можно объединить в дерево поиска, так называемый бор. Бор является конечным автоматом, распознающим одну строку из m — правда, при условии, что начало строки известно. Первое, что мы сделаем — научим автомат «самовосстанавливаться», если подстрока не совпала. Заманчиво при любой неподходящей букве переводить автомат в начальное состояние, однако это может привести к пропуску подстроки. Например: ищем строку aabab, попадается aabaabab. После считывания пятого символа переводим автомат в исходное состояние и пропускаем подстроку — верно было бы перейти в состояние a (а потом снова обработать пятый символ).

Чтобы автомат самовосстанавливался, добавим к нему суффиксные ссылки, нагруженные пустым символом ⌀ (так что детерминированный автомат превращается в недетерминированный). А именно: пусть, например, разобрана строка aaba. Пробуем «скормить» бору суффиксы aba, ba, a. Суффиксная ссылка — это ссылка на узел, соответствующий самому длинному суффиксу, который не заводит бор в тупик (в данном случае a).

Для корневого узла суффиксная ссылка — петля. Для остальных правило таково. Пусть последний распознанный символ — c. Проходимся по суффиксной ссылке родителя. Если оттуда есть дуга, нагруженная символом c, направляем суффиксную ссылку в тот узел, куда эта дуга ведёт. Иначе — проходимся по суффиксной ссылке ещё и ещё раз, пока либо не пройдём по корневой ссылке-петле, либо не найдём дугу, нагруженную символом c.

 * ···Ø···> * ···Ø···> * ···Ø···> *
 |                                |
 c                                c
 ↓                                ↓
[*] ·············Ø··············> *
     новая суффиксная ссылка

Этот автомат недетерминированный. Преобразование недетерминированного конечного автомата в детерминированный в общем случае приводит к значительному увеличению количества вершин. Но этот автомат можно превратить в детерминированный, не создавая новых вершин. А именно: если для вершины v некуда идти по символу c, проходимся по суффиксной ссылке ещё и ещё раз — пока либо не попадём в корень, либо будет куда идти по символу c.

Всю детерминизацию удобно делать рекурсивно. Например, для суффиксной ссылки:

 алг СуффСсылка(v)
   если v.кэшСуффСсылка ≠ Ø      // для корня изначально корень.кэшСуффСсылка = корень
     вернуть v.кэшСуффСсылка
   u := v.родитель
   c := v.символ
   повторять
     u := СуффСсылка(u)
   до (u = корень) или (существует путь u —c→ w)
   если существует переход u —c→ w
     то v.кэшСуффСсылка := w
     иначе v.кэшСуффСсылка := корень
   вернуть v.кэшСуффСсылка

Детерминизация увеличивает количество конечных вершин. А именно: если суффиксные ссылки из вершины v ведут в конечную u, сама v тоже объявляется конечной. Для этого устроим так называемые конечные ссылки: конечная ссылка ведёт на ближайшую по суффиксным ссылкам конечную вершину. Пройдя по конечным ссылкам, находим все совпавшие строки.

 алг ВывестиРезультат(v, i)
   напечатать "Найдено " + v.иголка + " в позиции " + (i - v.глубина + 1)
 алг ОсновнаяЧастьПоиска(v)
   состояние := корень
   цикл i=1..|стогСена|
     состояние := Переход(состояние, стогСена[i]);
     если состояние.иголка ≠ Ø
       ВывестиРезультат(состояние, i)
     времСост := состояние
     пока КонечнаяСсылка(времСост) ≠ Ø
       времСост := КонечнаяСсылка(времСост);
       ВывестиРезультат(времСост, i)

Ну и наконец: суффиксные и конечные ссылки в автомате можно рассчитывать по мере надобности уже на фазе поиска. Побочные переходы — можно вычислять на месте, никак не кэшируя, можно кэшировать для всех узлов, можно — для важнейших (на асимптотическую оценку алгоритма всё это не влияет).

Вычислительная сложность[править | править вики-текст]

Время работы зависит от организации данных. Например:

  • Если таблицу переходов автомата хранить как индексный массив — расход памяти O(nσ), вычислительная сложность O(nσ + H + k), где H — длина текста, в котором ищем, n — общая длина всех слов в словаре, σ — размер алфавита, k — общая длина всех совпадений.
  • Если таблицу переходов автомата хранить как красно-чёрное дерево — расход памяти снижается до O(n), однако вычислительная сложность поднимается до O((H + n) log σ + k).

Применение[править | править вики-текст]

Самое впечатляющее применение алгоритму Ахо-Корасик — антивирусы. Вирусная база может занимать сотни мегабайт, однако разница в скорости между 2- и 200-мегабайтной базой совсем невелика. Также метод применяется в обработке текстов, дешифровке ДНК.[источник не указан 243 дня]

Пример реализации[править | править вики-текст]

Пример реализации алгоритма на языке C++

# include <iostream>
# include <map>
# include <vector>
# include <string>
# include <queue>
 
using std::string;
using std::map;
using std::vector;
using std::queue;
using std::cin;
using std::cout;
using std::endl;
 
class BorNode;
typedef map<const char, BorNode *> LinksMap;
 
// Следующий класс может быть целесообразно поместить внутрь автомата среди приватных полей.
class BorNode {
public:
    LinksMap links;
    BorNode *fail;  // Предыдущее состояние для функции отката. Только для root равно NULL.
    BorNode *term; // Ближайшее терминальное состояние. Если отстутствует - NULL
    int out;
 
public:
    BorNode(BorNode *fail_node = NULL)
        : fail(fail_node)
        , term(NULL) 
        , out(-1)
    { }
 
    BorNode* getLink(const char c) const 
    {
        LinksMap::const_iterator iter = links.find(c);
        if (iter != links.cend()) {
            return iter->second;
        }
        else {
            return NULL;
        }
    }
 
    bool isTerminal() const 
    {
        return (out >= 0);
    }
};
 
class AhoCorasick
{
public:
    typedef void (*Callback) (const char* substr);
    BorNode root;
    vector<string> words;
    BorNode* current_state;
 
public:
    void addString(const char* const str) 
    {
        BorNode *current_node = &root;
        for(const char *cp = str; *cp; ++cp) {
            BorNode *child_node = current_node->getLink(*cp);
            if (!child_node) {
                child_node = new BorNode(&root);
                current_node->links[*cp] = child_node;
            }
            current_node = child_node;
        }
        current_node->out = words.size();
        words.push_back(str);
    }
 
    void init() 
    {
        queue<BorNode *> q;
        q.push(&root);
        while (!q.empty()) {
            BorNode *current_node = q.front();
            q.pop();
            for (LinksMap::const_iterator iter = current_node->links.cbegin();
                 iter != current_node->links.cend(); ++iter)
            {
                const char symbol = iter->first;
                BorNode *child = iter->second;
 
                // Defining .fail for the childnode
                BorNode *temp_node = current_node->fail;
                while (temp_node) {
                    BorNode *fail_candidate = temp_node->getLink(symbol);
                    if (fail_candidate) {
                        child->fail = fail_candidate;
                        break;
                    }
                    temp_node = temp_node->fail;
                }
 
                // Defining .term for the childnode using .term of current node
                    if (child->fail->isTerminal()) {
                        child->term = child->fail;
                    }
                    else {
                        child->term = child->fail->term;
                    }
                q.push(child);
            }
        }
    }
 
    void step(const char c) 
    {
        while (current_state) {
            BorNode *candidate = current_state->getLink(c);
            if (candidate) {
                current_state = candidate;
                return;
            }
            current_state = current_state->fail;
        }
        current_state = &root;
    }
 
    void printTermsForCurrentState(Callback callback) const 
    {
        if (current_state->isTerminal()) {
            callback(words[current_state->out].c_str());
        }
        BorNode *temp_node = current_state->term;
        while (temp_node) {
            callback(words[temp_node->out].c_str()); 
            temp_node = temp_node->term;
        }
    }
 
    void search(const char* str, Callback callback) 
    {
        current_state = &root;
        for(; *str; ++str) {
            cout << *str << ':' << endl;
            step(*str);
            printTermsForCurrentState(callback);
         }
    }
};
 
void print(const char* str)
{
    cout << "found substring " << str << "\n";
}
 
int main()
{
    AhoCorasick ak;
 
    ak.addString("test");
    ak.addString("rok");
    ak.addString("roka");
    ak.addString("strok");
    ak.addString("t");
 
    ak.init();
 
    ak.search("testovaya_stroka!", print);
 
    cin.get();
 
    return 0;
}

Пример реализации алгоритма на языке Python

class AhoNode:
    ''' Вспомогательный класс для построения дерева
    '''
    def __init__(self):
        self.goto = {}
        self.out = []
        self.fail = None
 
def aho_create_forest(patterns):
    '''Создать бор - дерево паттернов
    '''
    root = AhoNode()
 
    for path in patterns:
        node = root
        for symbol in path:
            node = node.goto.setdefault(symbol, AhoNode())
        node.out.append(path)
    return root
 
def aho_create_statemachine(patterns):
    '''Создать автомат Ахо-Корасика.
    Фактически создает бор и инициализирует fail-функции
    всех узлов, обходя дерево в ширину.
    '''
    # Создаем бор, инициализируем
    # непосредственных потомков корневого узла
    root = aho_create_forest(patterns)
    queue = []
    for node in root.goto.itervalues():
        queue.append(node)
        node.fail = root
 
    # Инициализируем остальные узлы:
    # 1. Берем очередной узел (важно, что проход в ширину)
    # 2. Находим самую длинную суффиксную ссылку для этой вершины - это и будет fail-функция
    # 3. Если таковой не нашлось - устанавливаем fail-функцию в корневой узел
    while len(queue) > 0:
        rnode = queue.pop(0)
 
        for key, unode in rnode.goto.iteritems():
            queue.append(unode)
            fnode = rnode.fail
            while fnode != None and not fnode.goto.has_key(key):
                fnode = fnode.fail
            unode.fail = fnode.goto[key] if fnode else root
            unode.out += unode.fail.out
 
    return root
 
def aho_find_all(s, root, callback):
    '''Находит все возможные подстроки из набора паттернов в строке.
    '''
    node = root
 
    for i in xrange(len(s)):
        while node != None and not node.goto.has_key(s[i]):
            node = node.fail
        if node == None:
            node = root
            continue
        node = node.goto[s[i]]
        for pattern in node.out:
            callback(i - len(pattern) + 1, pattern)
 
############################
# Демонстрация работы алгоритма
def on_occurence(pos, patterns):
    print "At pos %s found pattern: %s" % (pos, patterns)
 
patterns = ['a', 'ab', 'abc', 'bc', 'c', 'cba']
s = "abcba"
root = aho_create_statemachine(patterns)
aho_find_all(s, root, on_occurence)

Вывод скрипта:

At pos 0 found pattern: a
At pos 0 found pattern: ab
At pos 0 found pattern: abc
At pos 1 found pattern: bc
At pos 2 found pattern: c
At pos 2 found pattern: cba
At pos 4 found pattern: a

Ссылки[править | править вики-текст]