问索引全文搜索查询以实现高效的扇出

EN

一种方法是使用一个简单的字典将术语映射到查询。因此，考虑到以下四个问题：

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

现在，考虑一下这样的句子：“knol上的红色玻璃来自谷歌。”

解析每个单词并在字典中查找它。对于字典中的每个单词，将其查询列表添加到查询的主列表中。此外，对于字典中的每个单词，将其添加到相关单词的散列表中。在这一步的末尾，您将有两个结构:要检查的查询列表和相关单词列表：

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

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

例如，对于Query1，您可以检查相关单词列表是否包含谷歌和谷歌眼镜。

这件事的复杂性还不算太坏。您可以对文本中的每个解析单词进行O(1)查找。对于在解析阶段确定的每个查询，您可以对相关的单词哈希表进行N，O(1)查找。执行布尔运算涉及的逻辑非常少，但大多数查询都是简单的“所有单词”或“任何单词”类型的查询(即“这个和那个”，或者“这个或那个”)。

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

假设您有100万次查询，平均每个查询5个单词(这可能是一个很大的平均值)。这里最糟糕的情况是，有些文本至少包含每个查询中的一个单词。因此，您有一个100万个查询的列表来签入第2次传递。最坏的情况是，这是500万次字典查找。

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

这种方法的优点在于它的简单性，它可以很好地处理大量查询，这取决于您要输入的文本的大小。有一个可能更快的方法，但它涉及的更多。

您不用构建将术语映射到查询的字典，而是使用一个修改后的Aho字符串搜索算法，该算法与Unix fgrep程序在一次遍历文本时匹配多个正则表达式所使用的算法非常相似。在这里，我无法用简短的说明来解释这方面的细节。你可能想找到一篇名为“并行模式匹配和fgrep”的Dobb博士的老文章，据我回忆，这篇文章对如何做到这一点有一个相当好的解释。(快速搜索没有找到文章文本，但你可能会运气更好。)你也会想要阅读最初的Aho报纸：高效的字符串匹配:书目检索的辅助手段。这将讨论匹配文本字符串的并行模式，但基本思想适用于匹配正则表达式或布尔搜索查询。