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

← →
cyborg (2008-08-14 15:37) [0]

У кого-нибудь есть информация по этому алгоритму? В инете искал, не нашел. Если есть готовый код на Delphi, буду безмерно рад.

← →
TUser © (2008-08-14 15:44) [1]

Стоит поискать книгу Гасфилда, там есть код на паскале, считай, что на Delphi. В качестве отсебятины могу нарисовать тут псевдокод, если надо.

← →
cyborg (2008-08-14 15:51) [2]

> TUser © (14.08.08 15:44) [1]

Нарисуй, если не сложно.

← →
easy © (2008-08-14 16:25) [3]

не этот?
http://en.literateprograms.org/Kruskal%27s_algorithm_(Pascal)

← →
easy © (2008-08-14 16:38) [4]

на C#
http://www.codeproject.com/KB/recipes/ahocorasick.aspx

← →
cyborg (2008-08-14 17:10) [5]

> easy ©

Спасибо

← →
TUser © (2008-08-14 17:41) [6]

Странно, я под именем "алгоритм Ахо-Корасика" понимаю нечто совсем другое - множественный поиск подстроки.

Какую задачу хочет решить автор?

← →
cyborg (2008-08-14 17:46) [7]

Меня интересует хранение списка слов (включая слова с масками), быстрый поиск в этом списке нового слова, ну и множественный поиск подстроки тоже интересует.

Ну да, просто Крускал - это вроде из другой оперы.

Без деталей, и вряд ли это будет понятно, увы. Кажется на алголисте было описание этого алгоритма.

type
TTree = префиксное дерево банка текстов, в которых производится поиск

procedure FindMovement (vertex)
begin
// находим максимальный суффикс, являющийся префиксом какого-либо текста
// это делается аналогично такому же методу в алгоритме Кнута-Мориса-Пратта, только тут у нас не один текст, а префиксное дерево
end;

procedure FindStringInTexts (string, position, vertex);
begin
if no childs of the vertex then
return "Найдено"

for the every child of the vertex do
if the child_letter is string[position] then
FindStringInTexts (string, position+1, child)

if no hit obtained then
FindStringInTexts (string, position, movment for child);
end;

procedure AhoCorasic(Str: string; texts);
begin
1. Build the prefix tree (при этом добавляем фиктивные листья, маркирующие коноцы текстов - см. пример).

2. Ищем функции перехода
Для каждого узла ф.п. - это такой предковй узел (возможно, не непосредственный предок, на который надо переходить, если найдено несовпадение символов.)
for the every child of the top vertex do
FindMovments (child)

FindStringInTexts (Str + "$", 1, TopVertexOfTheTree)
end;

Пример построения префиксного дерева

Даны тексты
abcabac
abcab
caba
abcaabac

Добавляем фиктивный конечный символ, отсуствующий в алфавите
abcabac$
abcab$
caba$
abcaabac$

Имеем дерево
a-b-a-c-$ | Top-a-b-c-a-b-a-c-$ | | | $ | Lc-a-b-a-$

← →
cyborg (2008-08-14 18:02) [9]

Алгоритм Ахо-Карасик Найти похожие ветки