Aho-Corasick算法的可扩展性

Question

我希望能从一个关键词短语的数据库中（这些短语是从维基百科文章标题中提取的）搜索文本文档中的关键词短语。（例如，给定一个文档，我想知道是否存在任何对应的维基百科文章）。我了解到了Aho-Corasick算法。我想知道为数百万个条目构建Aho-Corasick自动机是否高效且可扩展。

- z33m

Answer 1

让我们来进行简单的计算：

假设你有100万个模式（字符串、短语），每个模式平均长度为10个字符，并且每个模式都分配了一个值（标记、令牌、指针等），长度为1个词（4个字节）。

那么，你将需要一个包含14百万字节（14MB）的数组来保存这些模式的列表。

对于100万个每个10个字符的模式，你可以构建一棵AC trie，其中节点数不超过1000万个。实际上，这个trie的大小取决于每个节点的大小。它至少应该保留1个字节的标签（字母）和4个字节的指向下一个节点的指针（或终端节点的模式）以及1个位（布尔）来标记终端节点，总共约5个字节。

因此，对于100万个10个字符的模式，你所需的trie的最小大小将是50百万字节，约50 MB的内存。

实际上，它可能会增加3-10倍，但这仍然非常可管理，因为即使是500 MB的内存在今天也很适中。（将其与Windows应用程序如Word或Outlook相比较）

鉴于速度方面Aho-Corasick（AC）算法几乎是无与伦比的，它仍然是迄今为止多模式匹配的最佳算法。这是我的坚定个人学术意见，不包括学术垃圾。

所有报告称“新”的最新和最伟大的算法可能超越AC都是高度夸张的（除了一些特殊情况，如DNA）。

AC唯一的改进在实践中可能沿着更多和更快的硬件（多核、更快的CPU、集群等）方向进行。

不要听信我的话，亲自测试吧。但请记住，AC的实际速度严重取决于实现（语言和编码质量）。

- nirvichara

---

恰巧，昆士兰大学肿瘤学院正在使用一种A-C实现来搜索DNA（用于癌症指标）--- DNA搜索具有极小的字母表，但模式非常长。 - Mischa

Answer 2

理论上，它应该只受到存储器层次结构的影响而保持线性速度 - 当它变得太大以至于无法适应缓存时，它会变慢；当它变得非常大时，如果开始被分页，就会出现问题。

另一方面，在使用Aho-Corasick算法搜索可能出现在输入字符串的任何位置的较大子字符串时，可获得显著的优势。如果您的文本文档已经被划分为单词，并且您的搜索短语不超过例如6个单词长度，则可以建立一个K个单词短语的哈希表，并在其中查找输入文本中每个连续的K个单词的部分，其中K = 1..6。

(对评论的回答)

"Aho-Corasick需要在内存中运行，因为您将会跟随指针穿梭于各个位置。如果必须在内存之外工作，那么回到传统的排序/合并可能是最简单的方法。从输入数据创建一个K-词记录文件，其中K是您感兴趣的任何短语中的最大单词数量。对其进行排序，然后将其与已排序的维基百科短语文件合并。您可以在Unix/Linux上几乎手动完成此操作，使用诸如sort和join以及一些shell/awk/perl/等实用程序。还请参见http://en.wikipedia.org/wiki/Key_Word_in_Context（我已经老到足以使用这些索引之一，它们提供了计算机打印输出的有限页面）"

- mcdowella

---

那么树形结构/哈希表必须完全存储在内存中吗？我字典中大约有800万个短语，所以完全使用内存的数据结构可能有些困难。 - z33m

关于K-Word哈希集解决方案...如果我使用800万条目字典的布隆过滤器，它能够保持在内存中并且快速高效吗？小的误判率是可以接受的，因为在我的应用程序的后期阶段，我将查找匹配项的详细信息，以便我可以消除它们。 - z33m

听起来很有道理 - 我认为你可以在足够大的机器上使用Aho-Corasick算法，但我不知道你有多大的机器，也不太了解涉及的常数。维基百科条目http://en.wikipedia.org/wiki/Bloom_filter在底部给出了一个公式，用于支持任何给定数量的条目和误报率所需的布隆过滤器位数 - 输入您的大小和所需的误报率，看看您是否能承担结果。 - mcdowella

Answer 3

其实有一个解决方法。将字典的AC trie结构写入类似xml格式的文本文件中，为该trie的前6个级别创建索引文件等等... 在我的测试中，我搜索字典中（500,000条目）句子的所有部分匹配，并且对于150-200个符号的句子，我得到了大约100个结果，用时约为150毫秒。

更多细节请查看这篇论文：http://212.34.233.26/aram/IJITA17v2A.Avetisyan.doc

- Aram Avetisyan

Answer 4

有其他提高性能的方法： - 压缩状态转换：可以将它们压缩为32位。 - 放弃指针；将状态转换写入扁平向量中。 - 将节点靠近树根打包在一起：它们会在缓存中。 该实现大约需要原始模式集每个字符3个字节的空间， 对于32位节点，可以占用大约1000万个字符的模式空间。 对于64位节点，尚未达到（或者尚未计算）极限。

文档: https://docs.google.com/document/d/1e9Qbn22__togYgQ7PNyCz3YzIIVPKvrf8PCrFa74IFM/view 源代码: https://github.com/mischasan/aho-corasick

- Mischa