aho corasick的可伸缩性

我想从关键字句库（从维基百科文章标题中提取）的数据库中搜索文本文档中是否出现关键短语。（即给定一个文件，我想找出是否有任何短语有相应的维基百科文章）我发现了关于Aho-Corasick算法。我想知道如果为数百万条目的字典构建Aho-Corasick自动机是否高效且可扩展。aho corasick的可伸缩性

来源

2011-02-27 z33m

从理论上讲，它应该只到存储器层次的影响，保持线速的对象 - 因为它得到太大，不适合在高速缓存中它会减慢，而当它变得非常大，你必须，如果它的问题开始分页。

OTOH与Aho-Corasick的大赢家是当搜索可能发生在字符串中的任何可能位置的正确大小的子字符串被馈入英寸如果您的文本文件已被切割成单词，并且您的搜索短语是不止如此然后你可以建立一个K字短语的散列表，然后从它的输入文本中查找每个K字连续的单词部分，K = 1..6。

（答评论）

阿霍Corasick需要生活在内存中，因为您将以下所有的地方的指针。如果你不得不在记忆之外工作，那么回到老式的排序/合并可能是最容易的。根据输入数据创建一个K字记录文件，其中K是您感兴趣的任何短语中单词的最大数量。对它进行排序，然后将其合并到排序的维基百科短语文件中。你几乎可以在Unix/Linux上手工操作，使用sort和join等实用工具，以及一些shell/awk/perl/whatever。另请参阅http://en.wikipedia.org/wiki/Key_Word_in_Context（我已经足够大了，可以实际使用这些索引中的一个，作为计算机打印输出的绑定页面提供）。

来源

2011-02-27 17:27:34 mcdowella

所以树/散列必须完全在内存中？我有大约800万词典在词典中，所以完全在内存中的数据结构是困难的，我猜... – z33m 2011-02-27 19:21:59

有关K-Word散列集解决方案..如果我使用800万词条的词典的布隆过滤器，它可以留下来在内存中，并且快速和高效？一个小的误报率是可以接受的，因为在我的应用程序的后期阶段，我会查找比赛的细节，所以我可以消除他们.. – z33m 2011-02-28 07:28:58

这听起来似乎合理 - 我认为你可能会逃脱与Aho-Corasick在一个大足够的机器，但我不知道你有多大的机器，对涉及的常量没有多少感觉。维基百科条目http://en.wikipedia.org/wiki/Bloom_filter在底部给出了一个公式，用于支持任意给定数量的条目和误报率的所需数量的Bloom过滤器位 - 将其放入您的大小并且要求虚假肯定率，看看你能负担得起的结果。 – mcdowella 2011-03-05 12:20:57

那么有一个解决方法。通过将字典中的内置AC字典编写成类似xml格式的文本文件，为该字典的前6个级别创建索引文件，等等......在我的测试中，我搜索了一个句子的所有部分匹配字典（500'000条目），并且我得到〜150ms〜150个符号的句子的100个结果。

有关详细信息，请查看本文：http://212.34.233.26/aram/IJITA17v2A.Avetisyan.doc

来源

2011-06-07 14:42:39

我们只是做一个简单的计算：

假设你有百万模式（字符串，短语），平均长度为10个字符和值（标签，令牌，指针等）长度为1字（4字节），分配给每个模式

然后，您将需要一个10 + 4 = 14百万字节（14Mb）的数组来保存模式列表。

从100万个图案10个字节（字母，字符），每次可以用不超过10万个节点构建一个交流特里。在实践中这个特里结构有多大取决于每个结点的大小。应该至少保持1个字节用于一个指向特里结构的下一个节点的标签（字母）和字（4字节）（或用于终端节点的图案）加1位（布尔值）来标记终端节点，总大约5个字节

所以，以100万个图案10个字符字典树的最小尺寸将需要最小50个百万字节或存储器的约50 MB。

在实践中，可能会更3-10倍，但仍是非常，非常易于管理，今天甚至500MB的内存是非常温和的。（将其与Windows应用程序比较，如Word或Outlook）

鉴于速度方面Aho-Corasick（AC）算法几乎无与伦比，它仍然是多模式匹配的最佳算法。除了学术垃圾之外，这是我强烈的个人教育意见。

的“新”最新和最伟大的算法，所有的报告可能优于AC是非常夸张（可能除了一些特殊情况下的短模式，如DNA）

AC唯一的改进可以在实践中沿直线走更多，更快的硬件（多核心，更快的CPU，集群等）

不要为我们说话，自己测试一下。但请记住，AC的真实速度很大程度上取决于实现（语言和编码质量）

来源

2012-12-04 16:44:59 nirvichara

aho corasick的可伸缩性

回答

相关问题