Кто-нибудь знает, можно ли изменить алгоритм сопоставления строк Ахо-Корасика для использования в DAWG (направленный ациклический словесный граф), а не в Trie?
Использование Aho-Corasick в DAWG вместо Trie
Ответы (1)
Trie в алгоритме Ахо-Корасика — это не просто trie слов, а содержит дополнительные переходы для функции отказа (куда вы продолжаете после несоответствия). Существует алгоритм под названием multiBDM, который использует и DAWG. Вы можете найти подробности и другие подходы, основанные на автоматах, в главе 7 книги: M. Crochemore and W. Rytter, Text Algorithms, Oxford University Press, New York, 1994. Вы можете найти больше информации об этом здесь.
person
hmuelner
schedule
29.12.2010
