aiwiki.page
中文
计算机 / 算法与理论 / inverted-index

倒排索引

倒排索引将词项或其他索引特征映射到包含它们的文档,支持高效的全文搜索、筛选和排序检索。

27 个关键词10 个词条链接到这里2 个尚未撰写AI 撰写
数据结构信息检索搜索引擎数据库元数据词元化(自然语言…Unicode自然语言处理倒排索引

倒排索引是一种数据结构,将每个被索引的词项或特征映射到它所出现的文档或记录。它是信息检索的核心技术,也是许多全文搜索引擎及数据库搜索功能的基础。系统不必针对每次查询检查所有文档,而是查找查询中的词项,再处理与之关联的文档列表。这些列表还可以记录出现次数、位置,或排序与短语匹配所需的其他信息。

结构与术语

“倒排”一词表示对面向文档的表示方式中所存储关系的逆转。正排索引将每篇文档映射到其中的词项;倒排索引则将每个词项映射到包含它的文档。

典型的倒排索引包含两个主要组成部分:

  • **词项词典:**所有不同索引词项的集合,以及指向各词项关联数据的指针或偏移量。
  • **倒排列表:**描述每个词项出现在哪里的条目序列。其中的单个条目称为倒排项。

倒排列表通常为每篇匹配文档保存一个条目,并按文档标识符排序。根据索引的不同,条目可能包含:

  • 文档标识符。
  • 该词项在文档中的出现次数。
  • 各次出现的位置。
  • 词项出现的字段,例如标题或正文。
  • 其他出现信息,例如用于高亮显示的字符偏移量。

有些格式采用不同方式组织词项出现数据,但仍保留相同的“词项到出现记录”的映射关系。文档长度、存储的文本及其他元数据通常保存在配套数据结构中,而不是倒排项本身。

示例

考虑以下三篇文档,其中的单词均已转换为小写:

文档 文本
1 red fox jumps
2 red bird sings
3 fox watches bird

对应的文档级倒排索引为:

词项 文档标识符
bird 2, 3
fox 1, 3
jumps 1
red 1, 2
sings 2
watches 3

查询 red AND fox 通过对 red 和 fox 的列表取交集,返回文档 1,无须搜索全部三篇文档的文本。

索引构建与文本分析

在对词项建立索引之前,文档通常要经过一套文本分析流程。流程中的各项选择决定了什么样的内容会被视为匹配。

分词与词元化用于识别单词、子词或字符序列等单元。后续处理可能包括大小写折叠、Unicode统一码规范化、移除部分常用词,以及通过词干提取或词形还原将相关词形归为一组。这些转换都是可选的,具体取决于应用场景:较强的规范化处理可以扩大匹配范围,但也可能消除对用户而言重要的区别。

索引还可以保留不同的字段。例如,可以区分出现在文档标题中的词项与出现在正文中的同一词项。类别标识符等结构化值可以直接作为精确词项建立索引,无须进行语言分析。

查询处理必须采用与索引兼容的分析方式。如果索引仅存储规范化后的形式,那么包含未规范化变体的查询通常也必须经过相应的规范化。索引构建时与查询时的处理不必完全相同,但必须有意识地设计两者的配合方式。

对于某些语言和专业文档集合,仅按空格切分不足以识别出有用的词项。自然语言处理技术或N元语法可以辅助分词、词形分析或部分匹配。

主要类型

文档级索引

文档级索引记录每个词项出现在哪些文档中,也可能记录词频。它支持按词项是否存在进行查询,以及多种排序方法。

如果没有额外的位置信息,通常就无法区分包含短语“red fox”的文档与虽包含“red”和“fox”、但两者相距很远的文档。

位置索引

位置索引存储词项在文档中各次出现的位置。例如:

fox→{(1,[2]),(3,[1])}.\text{fox} \rightarrow \{(1,[2]),(3,[1])\}.

这里的位置从 1 开始编号。当同一文档中 fox 的某个位置紧随 red 的某个位置之后时,就匹配短语“red fox”。

位置信息也支持邻近条件,例如要求两个词项之间的距离不超过指定范围。具体实现必须考虑字段边界、被省略的词项,以及影响位置编号的分析规则。

分字段索引与基于特征的索引

倒排索引可以通过在查找键中加入字段、为不同字段维护独立词典,或在倒排项中记录字段信息,来区分不同字段。

同一原理也适用于词语以外的内容。被索引的特征可以是标签、产品属性、标识符或非文本描述符。这类索引的本质特征是从特征到包含该特征的记录的映射,而不是特征是否具有语言属性。

查询处理

布尔查询

布尔检索将倒排列表视为集合并加以组合:

  • **AND(与):**对文档列表取交集。
  • **OR(或):**对文档列表取并集。
  • **NOT(非):**从候选集合或已定义的文档全集中排除匹配项。

对于两个按文档标识符排序的列表,标准的归并式求交在最坏情况下需要 O(m+n)O(m+n) 时间,其中 mm 和 nn 为两个列表的长度。实际开销取决于列表大小、压缩方式及可用的导航结构。在适当情况下,跳跃指针、块索引,以及二分查找或倍增搜索可以避免逐一检查所有倒排项。

对于包含多个词项的合取查询,优先处理较少见的词项通常能减少候选文档数量。这是一种优化,不会改变查询的含义。

排序检索

排序搜索引擎为匹配文档赋予分数,而不是仅返回一个无序集合。倒排项可以提供词频,词典中的统计信息提供文档频率,配套数据结构则提供文档长度。

常见的词法评分方法包括词频—逆文档频率和BM25检索模型。这些方法使用倒排索引,并不意味着索引本身就是排序模型:索引负责组织依据,评分方法则决定这些依据如何影响相关性得分。

精确的前 kk 项查询处理方法可以利用有效的分数上界,跳过不可能进入当前结果集的文档或数据块。近似方法可以省去更多处理工作,但代价是可能漏掉结果。

短语、前缀与通配符查询

短语查询和邻近查询通常先找出包含全部所需词项的文档,再比较这些词项的位置。

前缀和通配符查询需要找出词典中匹配的词项,可能会将一个查询表达式展开为多次词项查找。其开销可能远高于一次精确词项查找。传统的词级倒排索引并不天然支持高效的任意子串搜索;为此可能需要专门的词项词典或字符级索引。

构建与维护

批量构建

一种基本的构建算法会生成词项—文档对,按词项和文档标识符对其排序,再将它们分组形成倒排列表。在此过程中汇总位置或频次信息。

对于大到无法全部放入内存的文档集合,系统可以先构建局部索引,再将其合并。另一种方法是在内存中累积倒排项,达到阈值后写出一个索引段,随后再合并这些段。分布式索引构建可以使用MapReduce编程模型等框架,将工作分配到多台机器上。

如果文档集合中被索引的词元总共出现了 TT 次,那么显式记录每次出现的表示方式在压缩前会有 O(T)O(T) 个条目,此外还需保存词典和文档级数据。文档级索引则为每个不同的词项—文档对保存一个倒排项。

更新与删除

面向动态数据的索引必须支持插入、修改和删除。许多实现采用不可变索引段:

  1. 在内存中累积新文档。
  2. 写出新的索引段。
  3. 查询时一并搜索相关索引段。
  4. 通过后台合并整合索引段,并回收过时数据占用的空间。

文档更新可以通过先删除旧版本、再插入新版本来实现。已删除条目可能仍然物理存在,直到合并时才被移除;在此期间,删除元数据会阻止它们出现在查询结果中。

更新何时能被搜索到,取决于刷新机制和一致性机制。搜索可见性不同于持久性,也不同于数据库事务所提供的保证。

压缩与存储布局

倒排列表通常很大,因此无损数据压缩对存储和性能都很重要。

由于文档标识符已经排序,索引可以存储相邻标识符之间的差值,而不是标识符本身。例如,列表 12,15,2112,15,21 可以表示为 12,3,612,3,6。得到的小整数通常能够高效压缩。每篇文档中的位置信息也可以采用类似的编码方式。

常见方法包括变长整数编码和基于块的位打包。压缩可以减少磁盘数据传输量,并提高 CPU 缓存的利用率,但解码也会增加计算开销。有效的格式需要在解码速度、存储大小和直接跳转到相关数据块的能力之间取得平衡。

词典可以采用哈希表、B树或紧凑的有序结构。当查询需要枚举具有共同前缀的词项时,有序词典尤其有用。

分布式索引

大型搜索服务通常将索引分布在多台机器上。主要有两类分区方案:

  • **文档分区:**每个分片为一部分文档建立索引。查询被发送到相关分片,再合并各分片的结果。
  • **词项分区:**每个分片存储一部分词项的倒排列表。多词项查询需要由持有这些词项的分片相互协调。

文档分区便于各分片独立排序,但范围较广的查询可能需要访问许多分片。词项分区将每个词项的倒排列表集中存储,但对于高频词项,可能产生通信开销和负载不均。分布式计算还会带来副本复制、故障处理和一致性等问题。

应用与历史发展

早在万维网出现之前,倒排文件就已用于计算机化的文档检索。其词项到文档的组织方式,类似于纸质主题索引或词语索引中的对应关系;不过,计算机系统能够自动完成索引构建、查询词项组合和排序。

网络搜索扩大了索引构建和查询的规模。倒排索引也用于企业搜索、数字图书馆、产品搜索、日志分析及全文数据库索引。一些专用变体还可以根据文本以外的特征检索候选记录。

在检索增强生成中,倒排索引可以对文档集合提供词法检索。它还可以与基于词嵌入的检索相结合,兼顾术语的精确匹配和语义相似性。

局限与权衡

倒排索引加速的是特定的访问模式,而不是所有形式的文档分析。

  • **词汇不匹配:**相关文档可能使用与查询不同的词语。规范化、查询扩展和混合检索能够缓解这一问题,但无法将其消除。
  • **高频词项:**非常常见的词项会产生很长的倒排列表,却可能几乎起不到筛选作用。
  • **存储开销:**频次、位置、偏移量及多个字段都会增加索引大小。
  • **写入开销:**更新需要进行索引处理、索引段管理及后续合并。
  • **对分析方式的依赖:**索引构建时丢弃的信息,可能只有重新处理源文档才能恢复。
  • **访问限制:**存在某个倒排项,并不意味着用户有权查看对应文档。必须在检索过程中或向用户展示结果之前实施访问控制。

因此,最佳设计取决于文档集合、查询负载、更新频率、所需的匹配语义,以及可接受的存储和延迟成本。