我希望能从一个关键词短语的数据库中(这些短语是从维基百科文章标题中提取的)搜索文本文档中的关键词短语。(例如,给定一个文档,我想知道是否存在任何对应的维基百科文章)。我了解到了Aho-Corasick算法。我想知道为数百万个条目构建Aho-Corasick自动机是否高效且可扩展。
我希望能从一个关键词短语的数据库中(这些短语是从维基百科文章标题中提取的)搜索文本文档中的关键词短语。(例如,给定一个文档,我想知道是否存在任何对应的维基百科文章)。我了解到了Aho-Corasick算法。我想知道为数百万个条目构建Aho-Corasick自动机是否高效且可扩展。
让我们来进行简单的计算:
假设你有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的实际速度严重取决于实现(语言和编码质量)。
理论上,它应该只受到存储器层次结构的影响而保持线性速度 - 当它变得太大以至于无法适应缓存时,它会变慢;当它变得非常大时,如果开始被分页,就会出现问题。
另一方面,在使用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(我已经老到足以使用这些索引之一,它们提供了计算机打印输出的有限页面)"其实有一个解决方法。将字典的AC trie结构写入类似xml格式的文本文件中,为该trie的前6个级别创建索引文件等等... 在我的测试中,我搜索字典中(500,000条目)句子的所有部分匹配,并且对于150-200个符号的句子,我得到了大约100个结果,用时约为150毫秒。
更多细节请查看这篇论文:http://212.34.233.26/aram/IJITA17v2A.Avetisyan.doc
有其他提高性能的方法: - 压缩状态转换:可以将它们压缩为32位。 - 放弃指针;将状态转换写入扁平向量中。 - 将节点靠近树根打包在一起:它们会在缓存中。 该实现大约需要原始模式集每个字符3个字节的空间, 对于32位节点,可以占用大约1000万个字符的模式空间。 对于64位节点,尚未达到(或者尚未计算)极限。
文档: https://docs.google.com/document/d/1e9Qbn22__togYgQ7PNyCz3YzIIVPKvrf8PCrFa74IFM/view 源代码: https://github.com/mischasan/aho-corasick