本节介绍布尔检索与倒排索引的一些相关内容。

倒排索引

倒排索引用于记录查询词term到文档的一个映射。

word1 -> doc1, doc2, doc3
word2 -> doc1, doc2

每个词记录的文档编号，通常被称为倒排表。

关于倒排表数据结构的选择，主要有两种

1. 单向链表：支持高效的插入倒排记录表，比如在更新后的插入，并且自然能拓展到更高级的索引，比如跳表，但跳表需要额外的指针
2. 变长数组：在空间上节省，避免了指针开销，在时间开销了，因为其连续内存，充分利用了cpu的缓存，在时间上也最优。

为了一些操作上的方便，要对文档进行编号，并且对每条记录的倒排表进行排序，这样有助于进行一些操作。

布尔检索

考虑最简单的两个词之间的布尔操作。假设两个词term1和term2，其中倒排表的长度分别为$X$和$Y$，词汇表长度为$N$。 下面的操作都在前面倒排表有序的前提下进行的

1. AND：两个词都出现的文档 伪代码实现

   vector<int> AND(vector<int>& list1, vector<int>& list2) {
       vector<int> result;
       int i = 0, j = 0;
       while (i < list1.size() && j < list2.size()) {
           if (list1[i] == list2[j]) {
               result.push_back(list1[i]);
               i++;
               j++;
           } else if (list1[i] < list2[j]) {
               i++;
           } else {
               j++;
           }
       }
       return result;
   }

   时间复杂度为 $O(X + Y)$，因为只需要遍历两个倒排表一次

2. OR：两个词其中之一出现的文档 伪代码实现

   vector<int> OR(vector<int>& list1, vector<int>& list2) {
       vector<int> result;
       int i = 0, j = 0;
       while (i < list1.size() && j < list2.size()) {
           if (list1[i] == list2[j]) {
               result.push_back(list1[i]);
               i++;
               j++;
           } else if (list1[i] < list2[j]) {
               result.push_back(list1[i]);
               i++;
           } else {
               result.push_back(list2[j]);
               j++;
           }
       }
       while (i < list1.size()) result.push_back(list1[i++]);
       while (j < list2.size()) result.push_back(list2[j++]);
       return result;
   }

   时间复杂度为 $O(X + Y)$，同样只需要遍历两个倒排表

3. NOT：两个词没有出现的文档 伪代码实现

   vector<int> NOT(vector<int>& list, int totalDocs) {
       vector<int> result;
       int j = 0;
       for (int i = 1; i <= totalDocs; i++) {
           if (j < list.size() && list[j] == i) {
               j++;
           } else {
               result.push_back(i);
           }
       }
       return result;
   }

   时间复杂度为 $O(N + X)$，其中N是总文档数，需要遍历所有文档和倒排表

注

只要出现了NOT操作，时间复杂度至少是$O(N)$,不会出现$O(X+Y)$的时间复杂度

AND操作的结果一定比两个倒排表长度小

OR操作的结果一定比两个倒排表长度大

其中，对布尔操作的组合，也能优化查询效率。考虑下面的布尔操作：

(term1 AND term2) OR (term3 AND term4)

这个可以先合并两个小的AND操作，因为AND操作会显著减少结果集大小，然后再进行OR操作。

(term1 OR term2) AND (term3 OR term4)

这个可以先对每个OR操作进行合并，再进行最后的AND操作，但需要注意中间结果可能较大。

(term1 AND term2 AND term3) OR term4

多个AND操作可以依次进行，每次都会减少结果集大小。

(term1 OR (term2 AND term3)) AND (term4 OR term5)

复杂表达式可以先计算括号内的子表达式，再进行外层操作，按照从内到外的顺序计算。

全是AND的情况下，如过出现了空集，则可以提前退出。在这种情况下按长度大小排序进行合并，并不一定是最优的，可能是次短的记录和第二长的记录合并为空，这样就可以提前退出了。 例如，假设有四个词的倒排表：

• term1: doc1, doc2, doc3 (长度3)
• term2: doc1, doc4, doc5, doc6 (长度4)
• term3: doc7, doc8, doc9, doc10 (长度4)
• term4: doc11, doc12 (长度2)

如果按照从短到长合并：先合并term4和term1，再合并term2，最后合并term3。这需要遍历大部分文档。

但如果先合并term1和term3：由于它们没有共同文档，结果为空集，可以立即退出，不需要再合并term2和term4，节省了大量计算时间。

优化策略

跳表（Skip List）

为了加速倒排表的合并操作，可以使用跳表结构。跳表通过建立多级索引，使得在查找时可以跳过部分元素，从而实现 $O(\log n)$ 的查找复杂度。

// 带跳跃指针的倒排表
struct PostingWithSkip {
    int docId;
    PostingWithSkip* next;
    PostingWithSkip* skip;  // 跳跃指针
};

跳表的主要优势在于：

• AND操作可以快速定位到可能匹配的位置
• 不需要完全遍历较长的倒排表
• 实现相对简单，空间开销适中

词频优化

在实际应用中，还可以记录词频（TF）信息来优化检索效果：

word1 -> {doc1: 3, doc2: 1, doc3: 5}
word2 -> {doc1: 2, doc2: 4}

这样可以在布尔检索的基础上，进一步进行相关性排序。

拓展布尔检索

Westlaw 是全球最大的商业法律搜索引擎（以付费用户数量计）。 拥有超过50万订阅用户，每天执行数百万次搜索，处理数十TB的文本数据。 服务始于1975年。截至2005年，尽管Westlaw在1992年已引入排序式自由文本查询（称为“Natural Language”）， 但布尔搜索（称为“Terms and Connectors”）仍是大多数用户的默认选择。

展示了三个实际的Westlaw布尔查询，每个都包含信息需求和对应的查询表达式。这些查询使用了扩展的布尔语法，包括：

• $/s$：表示两个词项之间相邻（same sentence）
• $/p$：表示同一段落内
• $/n$：表示在最多$n$个词的距离内

对于短语，可以记录文档中出现的位置来进行计算。

如果只用位置索引（positional index）来处理短语查询（如 “Michael Jackson”），每次查询都需要实时合并多个词项的位置列表，计算开销大，尤其对高频或固定搭配的短语来说效率很低。

1. 解决方案：
   把两种方法结合起来：

   • 对常见或重要短语（如名人名字）预先建立专门的短语索引（类似双词索引或直接存储完整短语）；
   • 其他非常规短语仍用通用的位置索引处理。
     这种混合索引方案（mixed indexing scheme）能兼顾效率与灵活性。

2. 效果验证（Williams et al., 2004）：

   • 查询速度：混合方案的执行时间只有纯位置索引的 1/4（快4倍）；
   • 空间代价：仅多占用 26% 的存储空间，换来显著性能提升。

3. 典型例子：

   • “The Who”（一个乐队名）包含常见词 “the”，如果每次都要从位置索引中拼接，会很慢；若提前将其作为整体索引，就能快速响应。

不要每次都临时拼短语——对常用短语“预存结果”，能大幅提速，而存储代价可控。
这是一种典型的用少量额外空间换大量时间节省的工程优化思路。

但是时代的趋势是从布尔检索，走向了自然语言检索。