Использование Aho-Corasick на DAWG, а не на Trie

Question

Использование Aho-Corasick на DAWG, а не на Trie

Кто-нибудь знает, возможно ли изменить алгоритм сопоставления строк Aho-Corasick для использования в DAWG (направленный график ациклических слов), а не в Trie?

2

java algorithm string-matching aho-corasick dawg

Источник

user427079 01 окт '10 в 01:29

1 ответ

Решение

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

user324065 29 дек '10 в 23:21 2010-12-29 23:21 · Accepted Answer · 2010-12-29 23:21

Три в алгоритме Aho-Corasick это не простая три слова, а содержит дополнительные переходы для функции сбоя (где вы продолжаете после несоответствия). Существует алгоритм multiBDM, который использует как три, так и DAWG. Вы можете найти подробности и другие подходы, основанные на автоматах, в главе 7 книги: М. Крочемор и У. Риттер, Алгоритмы текста, Oxford University Press, Нью-Йорк, 1994. Вы можете найти больше информации об этом здесь.