algorithm - 索引全文搜索查询以实现高效扇出

Question

在考虑某天我可能想要构建的各种应用程序的设计时，在某些情况下，我需要根据它们是否匹配用户提供的大量全文搜索查询。

此问题的一个简单示例是 Twitter 流式搜索等工具的实现:给定每秒数千条新推文，有效地仅选择其搜索查询可能与传入推文匹配的流式订阅者。

问题的陈述类似于“反向全文搜索”，其中全文是查询，搜索结果是与该文本匹配的搜索查询。

对于单个术语查询，实现是显而易见的:简单地标记传入文档，然后搜索术语映射->(订阅者列表)，但是当 bool 查询成为可能时，事情变得更加困难。事实上，这个问题比全文搜索更普遍，但在那种情况下最容易理解。还有许多其他示例，其中大量 bool 项需要以某种方式组合以优化评估它们的成本。

例如，假设有 3 个搜索订阅:

1. 谷歌和眼镜
2. Google 和分析
3. ((谷歌眼镜和谷歌)不是 Knol)或 Twitter

一种可能是将查询解析成一棵树，然后访问每个节点，提取术语，并使用“术语映射”方法，但是这需要针对每个术语的传入文档重新评估订阅者查询.如果有足够的订阅者，这将很快开始变慢。

相反，我想知道是否有一种有据可查的方法可以将查询重写为单个查询，其中结果可以被评估一次，并且树节点用完全或几乎肯定已知的订户查询列表进行注释匹配树中指向该点的任何文档。

例如，上面的查询可能会被重写，以便存在 term->(query tree) 的映射，例如:

Google -> (分析[2]
玻璃 [1,3])
推特 -> ([3])


是否有任何现有的公开记录的系统可以执行类似的操作？理想情况下，该解决方案将允许逐步添加和删除订阅者，而无需执行一些昂贵的步骤来重写整个结构。

Answer 1

执行此操作的一种方法是使用将术语映射到查询的简单字典。所以给出这四个查询:

Query1: Google AND Glass
Query2: Google AND Analytics
Query3: ((Glass AND Google) NOT Knol) OR Twitter
Query4: Quick AND red AND fox

您构建了一个字典，以术语为关键字:

Google: Query1, Query2, Query3
Glass: Query1, Query3
Analytics: Query2
Knol: Query3
Twitter: Query3
Quick: Query4
red: Query4
fox: Query4

现在，考虑像“The red glass on the knol is from Google”这样的句子。

解析每个单词并在字典中查找。对于字典中的每个单词，将其查询列表添加到您的主查询列表中。此外，对于在字典中找到的每个单词，将其添加到相关单词的哈希表中。在此步骤结束时，您将拥有两个结构:要检查的查询列表和相关词列表:

Queries list: Query1, Query2, Query3, Query4
Relevant words: Google, Glass, Knol, red

现在是处理每个查询的问题，检查单词是否在相关单词列表中。

例如，对于查询 1，您将检查相关词列表是否包含 Google 和 Glass。

这个的复杂性还算不错。您对文本中每个已解析的词进行 O(1) 查找。对于在解析阶段识别的每个查询，您对相关单词哈希表进行了一些 N、O(1) 次查找。进行 bool 值计算时涉及的逻辑非常少，但大多数查询都是简单的“所有词”或“任何词”类型的查询(即“this AND that”或“this OR that”)。

此模型的好处在于它很容易分包给多个处理器。您可以在单个线程中解析单词，将它们推送到并发队列。多个线程为队列服务，进行查找并构建自己的需要检查的查询列表。完成所有这些查找后，您可以合并来自多个线程的查询列表，并再次将它们放在多个线程可以服务的并发队列中。

假设您有 100 万个查询，平均每个查询五个词(这可能是一个很大的平均值)。这里绝对最坏的情况是某些文本至少包含来自每个查询的一个词。因此，您有一个包含一百万个查询的列表要检查第 2 步。最坏的情况是 500 万个字典查找。

此算法的第一遍是 O(n)，其中 n 是传入文本中的单词数。这将创建一个包含 k 查询的列表。第二遍是 O(km)，其中 m 是每个查询的平均单词数。

这种方法的优点在于它的简单性，并且它对于中等数量的查询表现良好，具体取决于您输入的文本的大小。有一种可能更快的方法，但涉及更多。

您无需构建将术语映射到查询的字典，而是使用修改后的 Aho-Corasick 字符串搜索算法，该算法非常类似于 Unix fgrep 程序用于在单个文件中匹配多个正则表达式的算法传递文本。其中的细节超出了我在这里的简短说明中解释的能力。您可能想找到一篇名为“并行模式匹配和 fgrep”的旧 Dr. Dobb 期刊文章，我记得这篇文章对这是如何完成的有一个相当好的解释。 (快速搜索没有找到文章正文，但你可能运气更好。)你还想阅读原始的 Aho-Corasick 论文:Efficient String Matching: an Aid to Bibliographic Search .这讨论了并行模式匹配文字字符串，但基本思想适用于匹配正则表达式或 bool 搜索查询。