跳转至

阅读信息

约 1555 个字  8 分钟  本页总访问量：加载中... 次

ADS Lec 03 倒排索引

倒排索引（inverted file index）是一种常见的文本检索技术，用于快速查找包含特定单词或短语的文档。它通过将单词或短语作为关键字，并将它们出现在文档中的位置记录在一个索引中，从而支持快速的文本检索。在搜索过程中，系统可以快速地定位包含指定单词或短语的文档，并返回它们的相关信息。倒排索引广泛应用于搜索引擎、数据库系统和信息检索等领域。

基本结构

倒排索引结构：

No. Term
1 Abies <2;(1;3),(2;7)>
2 ads ...

Term 栏记录所有文档中词汇，称为词典。
最右边一栏记录每个词汇总出现次数、对应的文档编号和文档中的位置，称为倒排列表。

记录每个词的出现次数是为了提升搜索速度：如果搜索输入中有多个关键词，优先搜索总次数少的关键词（更精确）

伪代码：

Text Only
1
2
3
4
5
6
7
8
9
while (read a document D) {
    while (read a term T in D) {
        if (Find(Dictionary, T) == false)
            Insert(Dictionary, T);
        Get T posting list;
        Insert a node to T posting list;
    }
}
Write the inverted index to disk;

流程

词性还原

同一个单词可能有不同形式，将其全部还原为基本的单词。

也可以将常见的拼写错误归入同一个词干，实现更智能的搜索。

停用词分析

某些过于常见、几乎出现在任何文档中的词称为停用词，如 a, the
停用词一般不具备特殊含义，可以预先从原始文本中删除，在进行倒排索引的匹配。

注意：不能简单地将出现频率高的词视为停用词。

词项访问

词项访问即为如何在索引结构中高效地定位或检索某个词项。

  • B 树/B+树
  • 优点：查找、插入、删除较稳定，适合磁盘存储
  • 缺点：实现复杂，占空间较多
  • 字典树：
  • 优点：对字符串查找极快，支持前缀搜索
  • 缺点：空间开销大
  • 哈希表：
  • 优点：单个词查找速度最快
  • 缺点：多个词汇的位置不确定、可能相距很远，不支持范围查找

内存管理

在内存中累积一个块的词典和倒排表；
一旦内存达到上限，就把该块序列化并写在磁盘，清空内存结构，继续处理下一个块；
最后将所有块外部合并成最终的倒排索引。

伪代码：

Text Only
 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]);

实现

索引分配

实际中数据量大，将倒排索引放在多台计算机内，这些计算机称为集群（cluster）。
其中每一天计算机称为节点（node），每个节点存储整体倒排索引的一个子集。

划分方法：

  • 按词汇编号划分（如 A~Z）
  • 按文档编号划分

动态索引

文档随时有可能增加或删除，如果每次都更新倒排索引则效率低。

将原先的索引称为主索引；另外新增一个存储少量索引的空间，称为辅助索引。

新增文档的索引暂时放在辅助索引内。

用关键词搜索时，搜索引擎会同时在主索引和辅助索引中搜索（查找辅助索引更快一些）。

在适当的时候将辅助索引的内容合并到主索引（归档），同时清空辅助索引。

存储空间压缩

如果将所有词汇存储在数组中，存储空间取决于最长单词的长度，浪费空间多。

一种压缩方法：

  • 先去除停用词
  • 将所有的词汇放在同一个存储块内，词汇之间没有任何间隔（类似字符串）
  • 为了从字符串中分离出词汇，需要另一张小的表记录每个词汇开头的位置
  • 每个词汇的索引：记录相邻词汇开头的差分
  • 这样避免字符串长导致索引值过大。
  • 这样将很大的数组压缩为两张较小的表。

阈值

没有必要检索所有相关的网页，所以设定阈值。

  • 文档截断阈值：只取权重排名（例如 TF-IDF、BM25 得分）靠前的前 x 个文档。
  • 优点：减少不必要的文档计算或展示，提高响应速度。
  • 缺点：可能会遗漏部分相关文档（召回率下降）。
  • 示例：搜索引擎只展示前 1000 条结果。
  • 查询词阈值：对查询中的词项按出现频率升序排列，只用出现频率较低（更具区分性）的词项检索。
  • 优点：显著减少访问倒排表的数量，提高效率。
  • 缺点：若阈值过低，可能丢失相关结果

性能衡量

衡量搜索引擎性能，可以分为两大类：

  1. 系统性能：关注“速度”和“资源效率”，即搜索引擎运行得快不快、省不省资源。
  2. 检索性能：关注“结果质量”，即搜索引擎搜出来的结果是否有用、是否相关。

系统性能：

  • 索引速度：每小时处理的文档数量
  • 搜索速度：用户输入查询后，系统返回结果的速度
  • 时延（Latency）：从用户输入查询到看到结果的等待时间
  • 查询语句的可表达性：系统能否支持复杂查询（多关键词，带权重，模糊匹配等）的能力
  • 用户满意度：综合性指标，最终用户主观上的使用体验
  • 数据检索性能评估 (data retrieval performance evaluation)：主要考虑响应时间、索引占用空间等指标
  • 信息检索性能评估 (information retrieval performance evaluation)：主要考虑回答的相关程度等

检索性能：

Relavant Irrelevant
Retrieved \(R_R\) \(I_R\)
Not Retrieved \(R_N\) \(I_N\)
  • 精确度(precision, P)：所有检索到的文档中，有多少是有意义的（考虑表格第一行）
\[P=\frac{R_R}{R_R+I_R}\]
  • 召回率(recall, R)：所有有意义的文档中，有多少是被检索到的（考虑表格第一列）
\[R=\frac{R_R}{R_R+R_N}\]

如果精确度高而召回率低，那么我们会错过很多有价值的网页；
如果召回率高而精确度低，那么我们会得到很多无意义的网页；
因此理想情况是同时具备较高的精确度和召回率，但实际应用中可能无法同时兼顾两者，需要做好权衡。