在 DAWG 而不是 Trie 上使用 Aho-Corasick
有人知道是否可以修改 Aho-Corasick 字符串匹配算法以用于 DAWG（有向无环字图）而不是 Trie 上？
does anybody know if it's possible to modify the Aho-Corasick string matching algorithm to be used on a DAWG (Directed Acyclic Word Graph) rather than a Trie?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
Aho-Corasick 算法中的 trie 不是简单的单词 trie，而是包含失败函数的附加转换（不匹配后从哪里继续）。有一种名为 multiBDM 的算法，它同时使用 trie和一个 DAWG。您可以在本书的第 7 章中找到详细信息和其他基于自动机的方法：M. Crochemore 和 W. Rytter，文本算法，牛津大学出版社，纽约，1994 年。您可以找到有关它的更多信息 此处。
The trie in the Aho-Corasick algorithm is not a simple trie of the words but contains additional transitions for the failure function (where do you continue after a mismatch). There is a algorithm called multiBDM that uses both a trie and a DAWG. You can find details and other automata based approaches in chapter 7 of the book: M. Crochemore and W. Rytter, Text Algorithms, Oxford University Press, New York, 1994. You can find more info about it here.