10

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

4

4 回答 4

12

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

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

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

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

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

在实践中，它可能会增加 3 到 10 倍，但非常易于管理，因为今天即使 500Mb 内存也非常适中。（将其与 Word 或 Outlook 等 Windows 应用程序进行比较）

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

所有关于可能优于 AC 的“新”最新和最伟大算法的报告都被高度夸大了（可能除了一些像 DNA 这样的短模式的特殊情况）

在实践中，AC 的唯一改进可能是更多更快的硬件（多核、更快的 CPU、集群等）

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

于 2012-12-04T16:44:59.410 回答
6

从理论上讲，它应该保持线性速度，只受内存层次结构的影响——当它变得太大而无法放入缓存时，它会变慢，当它变得非常大时，如果它开始被分页，你就会遇到问题.

OTOH Aho-Corasick 的最大胜利是在搜索可能出现在输入字符串中任何可能位置的大小合适的子字符串时。如果您的文本文档已经被分割成单词，并且您的搜索短语不超过例如 6单词长，那么你可以建立一个 K-word 短语的哈希表，然后从其中的输入文本中查找每个 K-word 连续的单词部分，对于 K = 1..6。

（回复评论）

Aho-Corasick 需要存在于内存中，因为您将在所有地方都遵循指针。如果您必须在内存之外工作，那么回到老式的排序/合并可能最容易。从输入数据创建一个 K 字记录文件，其中 K 是您感兴趣的任何短语中的最大单词数。对其进行排序，然后将其与排序后的 Wikipedia 短语文件合并。您可能几乎可以在 Unix/Linux 上手动完成此操作，使用诸如排序和连接之类的实用程序，以及一些 shell/awk/perl/whatever。另请参阅http://en.wikipedia.org/wiki/Key_Word_in_Context（我已经足够大，可以实际使用这些索引之一，作为计算机打印输出的装订页提供）。

于 2011-02-27T17:27:34.537 回答
1

那么有一个解决方法。通过将构建的字典 AC trie 以类似 xml 的格式写入文本文件，为该 trie 的前 6 个级别制作索引文件，等等......在我的测试中，我搜索句子中的所有部分匹配字典（500'000 个条目），对于 150-200 个符号的句子，我得到约 100 个结果的约 150 毫秒。

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

于 2011-06-07T14:42:39.867 回答
0

还有其他获得性能的方法： - 压缩状态转换：您可以将它们降低到 32 位。- 放弃指针；将状态转换写入平面向量。- 将树根附近的节点打包在一起：它们将在缓存中。该实现占用原始模式集的每个字符大约 3 个字节，对于 32 位节点，可以占用大约 10M 字符的模式空间。对于 64 位节点，尚未达到（或计算）限制。

文档：https : //docs.google.com/document/d/1e9Qbn22__togYgQ7PNyCz3YzIIVPKvrf8PCrFa74IFM/view Src：https ://github.com/mischasan/aho-corasick

于 2018-08-25T21:28:30.040 回答