Реализации алгоритмов/Алгоритм Ахо — Корасик
Алгоритм Ахо — Корасик — алгоритм поиска подстроки, разработанный Альфредом Ахо и Маргарет Корасик. Алгоритм реализует поиск множества подстрок из словаря в данной строке.
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
[править]# -*- coding: utf-8 -*-
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 is not None and key not in fnode.goto:
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 is not None and s[i] not in node.goto:
node = node.fail
if node is 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