我想从 key 短语的数据库(摘录自维基百科文章标题)中搜索文本文档以查找 key 短语的出现。 (即给定一个文档，我想查找是否有任何短语具有相应的维基百科文章)我发现了有关Aho-Corasick算法的信息。我想知道为数百万个条目的字典构建Aho-Corasick自动机是否高效且可扩展。
最佳答案
从理论上讲，它应该保持线性速度，而仅受内存层次结构的影响-当它变得太大而无法放入缓存时，它会放慢速度；当它变得很大时，如果它开始分页，就会遇到问题。
OTOH Aho-Corasick的最大优势是在搜索可能在馈送的字符串内任何位置出现的大小合适的子字符串时。如果您的文本文档已经被切成单词，并且搜索短语不超过例如长度为6个单词，则可以构建一个K词短语的哈希表，然后从其中的输入文本中查找每个K词连续的词段，其中K = 1..6。
(回答评论)
Aho-Corasick需要保留在内存中，因为您将在各处跟踪指针。如果您必须在内存之外工作，那么回到老式的排序/合并可能最简单。根据输入数据创建一个包含K个单词记录的文件，其中K是您感兴趣的任何短语中单词的最大数目。对其进行排序，然后将其与已排序的Wikipedia短语文件合并。您可能几乎可以在Unix/Linux上手工完成此操作，使用诸如sort和join之类的实用程序，以及一些shell/awk/perl/whatever。另请参阅http://en.wikipedia.org/wiki/Key_Word_in_Context(我已经大到可以实际使用这些索引之一，作为计算机打印输出的装订页提供)。