algorithm - aho corasick 的可扩展性

Question

我想在文本文档中搜索关键短语数据库(从维基百科文章标题中提取)中出现的关键短语。 (即给定一份文件，我想查找是否有任何短语具有相应的维基百科文章)我发现了 Aho-Corasick 算法。我想知道为包含数百万条目的字典构建 Aho-Corasick 自动机是否高效且可扩展。

Answer 1

让我们做一个简单的计算:

假设您有 100 万个模式(字符串、短语)，平均长度为 10 个字符，并且分配给每个模式的值(标签、标记、指针等)长度为 1 个单词(4 字节)

那么您将需要一个 10+4=1400 万字节 (14Mb) 的数组来保存模式列表。

从 100 万个模式中，每个模式 10 个字节(字母、字符)，您可以构建一个节点数不超过 1000 万的 AC trie。这个 trie 在实践中有多大取决于每个节点的大小。它应该至少保留 1 个字节用于标签(字母)和字(4 字节)用于指向 trie 中下一个节点的指针(或终端节点的模式)加上 1 位( bool 值)来标记终端节点，总共约5个字节

因此，对于 100 万个模式 10 个字符的 trie，您至少需要 5000 万字节或大约 50 Mb 的内存。

在实践中，它可能是 3-10 倍，但仍然非常易于管理，因为即使是 500Mb 内存在今天也非常适中。 (与 Word 或 Outlook 等 Windows 应用程序进行比较)

鉴于 Aho-Corasick (AC) 算法在速度方面几乎无可匹敌，它仍然是有史以来最佳的多模式匹配算法。除了学术垃圾之外，这是我强烈的个人教育观点。

所有关于可能优于 AC 的"new"最新和最伟大算法的报告都被高度夸大了(除了一些具有短模式的特殊情况，如 DNA)

AC 的唯一改进实际上可以沿着更多更快的硬件(多核、更快的 CPU、集群等)的方向发展

不要相信我的话，请亲自测试一下。但请记住，AC 的实际速度在很大程度上取决于实现(语言和编码质量)