倒排索引

搜索引擎的的检索方式

 &emsp 让我们从搜索引擎开始。首先我们来思考一下搜索引擎是怎么工作的，举个例子，当我们在Goggle搜索关键字"Computer Science"时，发生了什么？一个简单的想法是引擎遍历所有包含的文章，再逐字查找关键字。但显而易见，这么做的开销将会是极其恐怖的，因此这个方案是不可行的。

 &emsp 在这个基础上，我们可以尝试一种优化方案，即我们不再等到查询时再去遍历文档寻找关键字，而是提前创建索引，将文档中包含的关键字提取出来，检索时检查被提取出的关键字即可。适合这套方案的数据结构是“文档关联矩阵”。文档关联矩阵是一个以词典中的词项为行，文档集合中的文档为列，单元格值为0或1的矩阵。单元格为1代表着该词项出现在了该文档中。假设某一行为"Doc1.doc"，一列为"Computer"，单元格值为1，这就代表着词"Computer"出现在了文档Doc1.doc中。反之则代表未出现。但是我们同样可以显然地发现，这个矩阵应当是极其稀疏的，并且规模可以极其巨大，这是显然不实用的。

 &emsp 那么是否有进一步的优化方案呢？答案是肯定的。我们可以尝试颠倒一下思路，上面建立的“文档 -> 词项”映射存在低效率的问题，那么我们可以改成建立“词项 -> 文档”的映射，这就是倒排索引(Inverted File Index)

倒排索引

倒排索引的结构

• 倒排索引由两个核心部分组成：
  • 词项词典：一个包含所有唯一词项（经过规范化处理，如小写）的集合。它是访问记录表的“钥匙”。
  • 记录表：对于词典中的每个词项，对应一个记录表。记录表是一个列表，其中每个条目（称为Posting）包含：

    • 文档ID (Document ID): 标识包含该词项的文档。

    • （可选）其他信息: 如词项在该文档中出现的次数（TF - Term Frequency）、出现的位置（用于短语查询或邻近查询）、权重等。

• 关系：词典中的每个词项T指向其最近的记录表L。L中按顺序（通常是DoclD升序）存储了所有包含T的文档的ID。
• 索引构建伪代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Index Generator
while ( read a document D ) {
    while ( read a term T in D ) {
        if ( Find( Dictionary, T ) == false )
            Insert( Dictionary, T );
        Get T’s posting list;
        Insert a node (with docID D) to T’s posting list;
    }
}
Write the inverted index to disk;

文本预处理

• 可以想见的是，如果仅按上面的方式处理，那么索引仍然是很大的，并且远远不能达到与实际搜索引擎相近的结果，为了进一步优化，我们需要文本预处理。文本预处理的方式主要有两种：
  • 词干提取：
    • 停用词将单词的不同形态（如“running”, “runner”, “runs”）还原为其基本形式（词干/词根）“run”。这可以减少词典大小，并让查询“run”也能匹配包含其变体的文档。常用算法如Porter Stemmer。
  • 停用词:
    • 指那些在语言中极其常见但对区分文档内容几乎没有意义的词（如英文的“a”, “the”, “it”, “and”, “of”）。几乎每个文档都包含它们，索引它们会显著增大索引体积且对相关性排序帮助甚微。通常在预处理阶段直接移除。
• 处理时机：这些处理发生在分词之后，将词项T插入词典或记录表之前

词项词典的访问与储存

• 方案1：搜索树 (Search Trees): 如B树、B+树、字典树(Tries)。这些数据结构保持词项有序。
  • 优点： 支持范围查询（如查找以“comput”开头的所有词项）、前缀查询；易于处理更新；磁盘友好（B/B+树）。
  • 缺点： 查找单个词项的平均时间复杂度通常是O(log n)，略慢于哈希；实现相对复杂。
• 方案2：哈希 (Hashing): 使用哈希表存储词项到记录表指针的映射。
  • 优点： 查找单个词项的平均时间复杂度是O(1)，非常快；实现相对简单。
  • 缺点： 不支持范围查询或前缀查询；哈希冲突需要处理；扩容可能较复杂；对部分匹配不友好。

内存不足时的索引建构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

BlockCnt = 0;
while ( read a document D ) {
    while ( read a term T in D ) {
        if ( out of memory ) {
            Write BlockIndex[BlockCnt] to disk;
            BlockCnt ++;
            FreeMemory;
        }
        if ( Find( Dictionary, T ) == false )
            Insert( Dictionary, T );
        Get T’s posting list;
        Insert a node to T’s posting list;
    }
}
for ( i=0; i<BlockCnt; i++ )
    Merge( InvertedIndex, BlockIndex[i] );
Sorted

• 基础构建算法假设整个词典和记录表能放入内存。对于海量数据，这是不现实的。这里描述了基于块的排序索引 (Blocked Sort-Based Indexing or BSBI) 算法：

  • 初始化块计数器 BlockCnt=0。
  • 逐文档、逐词项处理（包含分词、词干提取、停用词移除）。
  • 当内存不足时：
    • 将当前在内存中构建的部分索引（BlockIndex[BlockCnt]，它包含部分词项及其在这些已处理文档中的记录表）作为一个块(Block) 写入磁盘。
    • 块计数器 BlockCnt 增加。
    • 释放内存（清空当前内存中的部分索引结构）。
    • 继续处理后续文档和词项，重复步骤3直到所有文档处理完。最后内存中可能还有一个未写满的块。

• 关键步骤 - 归并 (Merge): 将写入磁盘的BlockCnt个块（每个块内部词项有序）和内存中最后的块，通过多路归并的方式合并成一个完整的、全局有序（Sorted）的倒排索引 InvertedIndex。

• 核心思想： “分而治之”。将大数据集分割成能在内存中处理的小块，分别构建部分索引，最后合并。

分布式处理

• 在上面讨论过了文本预处理和BSBI等针对web搜索庞大的数据量的优化方案后，可能仍会有质疑：这样数据规模仍然可以很大，能够储存吗？事实上确实不可以，所以这里要用到分布式的存储和处理。
• 词项分区索引：将词项词典划分到不同的节点。例如节点1存储A-F所有的词项词典，节点2存储G-J所有的词项词典。一个词项T的所有记录表都存储在T所在的节点
  • 优点：处理单个词项查询很快
  • 缺点：处理多个词项查询时可能涉及跨节点通信；新增节点或词项频率不均匀时可能出现负载不均衡
• 文档分区索引：将文档集合分布到不同的节点，每个节点存储它那一部分文档的的完整倒排索引。查询时将结果广播到所有节点，每个节点在自己的文档上查询并返回部分结果，由一个协调节点汇总。
  • 优点：易于扩展，新增文档时只要新增加节点即可
  • 缺点：查询每个词项都需要访问所有节点；节点需要存储完整词典副本。

动态索引

• 上面的分布式处理部分中提到了有关新增文档的问题。这同样是值得思考的问题。每次新增文档，或文档新增内容后，我们是否需要从头创建索引？答案是否定的，这样会造成巨大的资源浪费。为了解决这个问题，我们需要动态索引。
• 动态索引技术要解决主要是新增的删除的问题，可以通过使用主索引(Main Index)+辅助索引(Auxiliary Index)
  • 主索引：磁盘上的主要、相对稳定的大索引
  • 辅助索引：内存中的小索引，用于缓存新增文档
• 新增文档流程：
  • 新文档被添加到辅助索引
  • 当辅助索引达到一定大小，或经过一定时间间隔，将辅助索引合并到主索引，操作类似BSBI中的归并操作
• 删除文档操作：
  • 在主索引将待删除文档标记为已删除，执行查询时跳过被标记为已删除的文档。在下一次执行归并时物理移除被标记为已删除的文档ID。

压缩

• 此外，我们可以通过压缩进一步减小倒排索引体积规模。涉及到如下技术
  • 记录表压缩：记录表的核心是文档ID列表，记录表通常按ID升序排序，且文档ID可能本身较大。压缩利用两个特性：
    • 差值编码（间隙编码）：用ID之间的差值代替ID值存储
    • 变长编码：对小整数使用更少位数编码
  • 词项词典压缩：词项本身（字符串）也可压缩（如前缀/后缀压缩、块存储）。
  • 阈值化：有时为了提供速度或减小索引，会设定阈值，如
    • 只存储词频大于某个阈值的词项（过滤低频噪音词）。
    • 在记录表中，只存储词频最高的前K个文档ID（牺牲召回率换取速度和空间）。这通常在查询处理阶段应用（见下页），而非索引构建时。

快速查询处理技术

• 以下介绍了两种加速查询处理（特别是复杂查询或排序查询）的技术，但会牺牲一定的准确率（召回率）：
  • 方案1：文档截断 (Index Pruning / Document Thresholding): 对于排序查询 (Ranked Queries)（如BM25, TF-IDF），不计算所有匹配文档的得分，而是对每个词项，预先在其记录表中根据某种权重 (weight)（如词项在文档中的重要性，TF-IDF本身或变体）进行排序或只保留权重最高的 x 个文档ID。查询时，只在这些被截断的、高权重的记录表上进行操作（如交集、计算得分）。目标是快速找到最相关的 x 个文档。
  • 方案2：查询词项截断 (Query Term Thresholding):对查询中的词项，按它们在整个文档集中的频率（或文档频率 - DF）升序排序。低频词项通常更具区分度。只使用原始查询词项中的一部分（如前K个，或频率最低的某个百分比）进行搜索。例如，查询“computer science department”，按DF升序排序可能是“department”(低频)、“science”(中频)、“computer”(高频)。只使用“department”和“science”进行检索。
  • 缺点:Not feasible for Boolean queries：这些优化主要针对排序检索模型 (Ranked Retrieval Model)。对于严格的布尔查询 (Boolean Queries)（要求精确匹配所有词项AND/OR/NOT），截断可能导致漏掉本应匹配的文档（违反布尔条件）。
  • Can miss some relevant documents due to truncation：两种截断方法都可能导致丢失相关文档（False Negative），降低召回率 (Recall)。这是用精度（通常是速度）换取召回率的权衡。

搜索引擎的评价指标

• 最后我们来看一下使用的对搜索引擎的评价指标，其中可以分为性能评估和相关性评估
  • 性能评估：
    • 索引速度 (Indexing Speed): 每小时能处理多少文档 (Number of documents/hour)。影响索引更新频率。
    • 查询速度 (Search Speed / Query Latency): 用户提交查询到收到结果的时间 (Response time)。查询延迟 (Latency) 会随着索引大小 (index size) 增长而增加，设计需考虑可扩展性。
    • 查询语言表达能力 (Expressiveness of query language): 支持用户表达复杂信息需求的能力（如布尔操作符、短语查询、通配符、字段搜索、过滤器等）。同时也要考虑执行复杂查询的速度 (Speed on complex queries)。
    • 用户满意度 (User happiness): 最核心但最难量化。用户觉得结果有用、相关、体验好。
  • 相关性评估
    • 准确率 (Precision - P): 返回结果中相关的文档所占的比例。衡量“准不准”。
      • P = RR / (RR + IR)
      • RR (Relevant Retrieved): 检索到的相关文档数。
      • IR (Irrelevant Retrieved): 检索到的不相关文档数。
      • 关注的是结果的质量。
    • 召回率 (Recall - R): 所有相关文档中被检索到的比例。衡量“全不全”。
      • R = RR / (RR + RN)
      • RR (Relevant Retrieved): 检索到的相关文档数。
      • RN (Relevant Not Retrieved): 相关但未被检索到的文档数。
      • 关注的是系统的覆盖能力。
    • P-R 曲线 (Precision-Recall Curve): 幻灯片上的 1 0 1 Recall Precision 图示描绘了一个典型的P-R曲线。横轴是召回率(R)，纵轴是准确率(P)。曲线通常呈下降趋势（召回率越高，准确率往往越低）。曲线下的面积(AUC)或特定召回率点（如R=0.5）的准确率是常用汇总指标。F1值（2_P_R/(P+R)）是P和R的调和平均，也是一个常用单值指标。