z33*_*33m 10 algorithm search wikipedia automaton aho-corasick
我想在一个文本文档中搜索关键短语数据库中出现的关键短语(从维基百科文章标题中提取).(即,给定一个文档,我想找出是否有任何短语都有相应的维基百科文章)我发现了Aho-Corasick算法.我想知道为数百万条目的字典构建Aho-Corasick自动机是否有效且可扩展.
小智 12
我们来做一个简单的计算:
假设您有100万个模式(字符串,短语),平均长度为10个字符,并且长度为1个字(4个字节)的值(标签,标记,指针等),分配给每个模式
然后你需要一个10 + 4 = 1400万字节(14Mb)的数组来保存模式列表.
从100万个模式中,每个10字节(字母,字符)可以构建一个不超过1000万个节点的AC trie.这个特里在实践中有多大取决于每个节点的大小.对于指向trie中的下一个节点(或终端节点的模式)的指针,以及标记终端节点的1位(布尔值),它至少应保留1个字节(字母)和字(4字节),总计约5个字节
因此,对于100万个模式10个字符的trie的最小大小,您将需要最少5000万字节或大约50 Mb的内存.
在实践中它可能是3-10倍,但是非常非常易于管理,因为即使500Mb内存今天也非常温和.(将其与Word或Outlook等Windows应用程序进行比较)
鉴于在速度方面Aho-Corasick(AC)算法几乎是无与伦比的,它仍然是有史以来多模式匹配的最佳算法.除了学术垃圾之外,这是我强烈的个人教育观点.
所有可能超出AC的"新"最新和最佳算法的报告都被夸大了(除了一些像DNA这样的短模式的特殊情况)
AC的唯一改进实际上可以沿着越来越快的硬件线路(多核,更快的CPU,集群等)
不要相信我的话,为自己测试一下.但请记住,AC的实际速度很大程度上取决于实现(编码的语言和质量)
从理论上讲,它应该保持线性速度仅受内存层次结构的影响 - 它会因为它太大而无法适应缓存而变慢,当它变得非常大时,如果它开始被分页,你将遇到问题.
OTOH与Aho-Corasick的最大胜利是在搜索可能出现在正在输入的字符串中任何可能位置的合适大小的子串.如果您的文本文档已经被切成单词,并且您的搜索短语不超过例如6单词长,然后你可以建立一个K字短语的哈希表,然后从其中的输入文本中查找每个K字连续的单词部分,K = 1..6.
(回答评论)
Aho-Corasick需要留在记忆中,因为你将会到处追踪指针.如果你必须在内存之外工作,那么回归老式的排序/合并可能是最容易的.从输入数据创建一个K-words记录文件,其中K是您感兴趣的任何短语中的最大单词数.对其进行排序,然后将其与已排序的Wikipedia短语文件合并.您几乎可以在Unix/Linux上手动执行此操作,使用排序和连接等实用程序,以及一些shell/awk/perl /等等.另请参见http://en.wikipedia.org/wiki/Key_Word_in_Context(我已经足够实际使用其中一个索引,作为计算机打印输出的绑定页面提供).