如何在倒排索引结构中搜索短语查询？

Question

如果我们想在反向索引结构中搜索像这样的查询“ t1 t2 t3”（t1，t2，t3必须排队），该怎么办？

1-首先，我们搜索“ t1”项，找到包含“ t1”的所有文档，然后对“ t2”然后是“ t3”进行此操作。然后找到位置“ t1”，“ t2”和“ t3”彼此相邻的文档。

2-首先，我们搜索“ t1”项并找到包含“ t1”的所有文档，然后在找到的所有文档中搜索“ t2”，然后在此结果中找到包含“ t3”的文档“。

我有一个完整的倒排索引。我想知道上面的哪些方法是优化的（1）或（2）？

非常感谢。

Answer 1

由于维基百科入口井解释说，

反向索引主要有两种变体：记录级反向索引（或反向文件索引 或仅反向文件）包含每个单词的文档引用列表。甲字电平倒排索引（或 全倒排索引或倒排列表）还含有文档中的每个字的位置。后一种形式提供更多功能（例如词组搜索），但需要更多的时间和空间来创建。

由于您没有告诉我们您拥有哪种变体，因此我们无法真正准确地回答您的问题，但是考虑每种可能性将有所帮助。

除非您的文档非常小，否则打开和搜索文档通常是一项昂贵的操作，因此您希望将其最小化-选项（2）并没有真正将其最小化。如果您有一个反向列表，则带有选项（1）甚至不需要打开任何文档；如果您只有倒排的文件，那么您将不可避免地需要打开文档并进行扫描（因为否则会缺少信息来确认单词相邻性），但是至少使用选项（1）可以使您必须打开的文档数最少并扫描（仅包含每个单词的文档列表的交集中的那些）。

因此，无论哪种情况，选项（1）都更有前途（除非您的文档特别小）。