Алгоритм Ахо

Алгоритм Ахо — Корасик — алгоритм поиска подстроки, созданный Альфредом Ахо и Маргарет Корасик. Алгоритм реализует поиск множества подстрок из словаря в данной строке. Время работы пропорционально $O(M+N+K)$, где $N$ — длина строки-образца, $M$ — суммарная длина строк словаря, а $K$ — длина ответа, то есть суммарная длина вхождений слов из словаря в строку-образец.

Принцип работы

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

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

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

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <queue>
 
using namespace std;
 
class AhoCorasick
{
public:
    typedef void (*Callback) (const char* substr, int begin, int end);
 
    ~AhoCorasick()
    {
        queue<BorNode*> q;
        for(map<char, BorNode*>::const_iterator iter = root.links.begin();
            iter != root.links.end(); ++iter)
            q.push(iter->second);
        while(!q.empty())
        {
            BorNode* current_node = q.front();
            q.pop();
            for(map<char, BorNode*>::const_iterator iter = current_node->links.begin();
                iter != current_node->links.end(); ++iter)
                q.push(iter->second);
            delete current_node;
        }
    }
 
    // Метод добавляет строку в бор
    void AddString(const char* str)
    {
        BorNode* node = &root;
        for(const char* s = str; *s; ++s)
        {
            map<char, BorNode*>::iterator iter = node->links.find(*s);
            if(iter != node->links.end())
                node = iter->second;
            else
            {
                BorNode* new_node = new BorNode;
                node->links[*s] = new_node;
                node = new_node;
            }
        }
        node->out = words.size();
        words.push_back(str);
    }
 
    // Метод вычисляет функции неудачи
    void Init()
    {
        root.fail = &root;
        queue<BorNode*> q;
        q.push(&root);
        while(!q.empty())
        {
            BorNode* current_node = q.front();
            q.pop();
            for(map<char, BorNode*>::const_iterator iter = current_node->links.begin();
                iter != current_node->links.end(); ++iter)
            {
                BorNode* child = iter->second;
                char symb = iter->first;
                q.push(child);
 
                BorNode* parent_fail = current_node->fail;
                while(true)
                {
                    map<char, BorNode*>::const_iterator it = parent_fail->links.find(symb);
                    if(it != parent_fail->links.end())
                    {
                        child->fail = it->second != child ? it->second : &root;
                        if(child->out < 0)
                            child->out = child->fail->out;
                        break;
                    }
                    if(parent_fail == &root)
                    {
                        child->fail = &root;
                        break;
                    }
                    else
                        parent_fail = parent_fail->fail;
                }
            }
        }
    }
 
    void Search(const char* str, Callback callback)
    {
        BorNode* current_node = &root;
        for(int pos = 1; *str; ++str, ++pos)
        {
            map<char, BorNode*>::const_iterator iter = current_node->links.find(*str);
            while(iter == current_node->links.end())
            {
                current_node = current_node->fail;
                iter = current_node->links.find(*str);
                if(current_node == current_node->fail)
                    break;
            }
            if(iter != current_node->links.end())
            {
                current_node = iter->second;
 
                if(current_node->out >= 0)
                    callback(words[current_node->out].c_str(), pos - words[current_node->out].length(), pos - 1);
            }
        }
    }
 
private:
    struct BorNode
    {
        BorNode() : fail(NULL), out(-1) {}
 
        map<char, BorNode*> links;
        BorNode* fail;
        int out;
    };
 
    BorNode root;
    vector<string> words;
};
 
void print(const char* str, int start, int end)
{
    cout << "Найдена подстрока " << str << " (начало " << start << ", конец " << end << ")\n";
}
 
int main()
{
    AhoCorasick ak;
    ak.AddString("test");
    ak.AddString("rok");
    ak.AddString("sto");
    ak.AddString("st");
    ak.Init();
    ak.Search("testovaya_stroka", print);
}

Пример реализации алгоритма на языке 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

Внешние ссылки

• Визуализатор алгоритма Ахо — Корасик
• Реализация алгоритма на C#
• Реализация алгоритма на Java
• Реализация алгоритма на Erlang
• Подробное описание алгоритма