Как использовать Aho-Corasick, чтобы найти фрагмент текста в заданном наборе строк?

Question

Как использовать Aho-Corasick, чтобы найти фрагмент текста в заданном наборе строк?

У меня есть код алгоритма Aho-Corasick. Но я все еще не понимаю, как использовать информацию о состоянии во время процедуры поиска при поиске текста в заданном списке строк.

Например у меня есть список строк [MOSCOW][COLA]и теперь мне нужно определить, CA в списке, и если да, то какова его позиция?

Вот ссылка на код.

2

algorithm string-matching aho-corasick

Источник

user1352002 18 июл '12 в 12:36

1 ответ

Другие вопросы по тегам algorithm string-matching aho-corasick

user1235565 18 июл '12 в 17:41 2012-07-18 17:41 · Answer 1 · 2012-07-18 17:41

Алгоритм, который вы изучаете, работает совсем наоборот. Если словарь [MOSCOW][COLA] и входная строка CA, тогда алгоритм скажет вам все места MOSCOW в CA, а также все места COLA в CA,

Теперь определенное состояние (или, Node, как это называется в связанном коде), имеет значение что-то вроде: " Мы могли бы быть сразу после C в COLA , но мы определенно не где-то в середине MOSCOW ". (Это может быть узел, посещенный после первого символа CA.)

Сила алгоритма легче увидеть при поиске другого входа, скажем, MOSCOLONI, Перед тем как увидеть L текущее состояние будет означать " Мы могли бы быть 5 символов в потенциальном MOSCOW или 2 символа в потенциал COLA "Важно то, что государство смотрит на все слова словаря одновременно, фактически даже на все позиции во всех словах, если учесть также повторяющиеся символы.