倒排索引原理

倒排索引这个词这几年特别流行,那么什么是倒排索引呢,为什么倒排索引的查询速度就快呢。
这里我根据自己的学习和理解,简单总结下。
会有些专业术语,不过少量的大白话并结合一些例子,应该可以理解了。

一、我用过的场景

  • Lucene
  • Elasticsearch

二、术语

  索引(index)是一种数据结构,广泛应用在数据检索领域。
  索引就像一本书的目录一样,可以帮助我们快速检索想要的信息。
  
  分词器将文本进行切割,得到一系列最小搜索单元,即词项(Term);
  词项的值称为词汇单元(token),简称词元;
  词项中还携带了各种额外的信息,例如词元在原始文本中的位置、词元的长度等。

三、正向索引(forward index)

1. 概念

  正排表是以文档的ID为关键字,表中记录文档中每个Term的位置信息,查找时扫描表中每个文档中Term的信息直到找出所有包含查询关键字的文档。
  因为索引是基于文档建立的,若是有新的文档加入,直接为该文档建立一个新的索引块,挂接在原来索引文件的后面。若是有文档删除,则直接找到该文档号文档对应的索引信息,将其直接删除。但是在查询的时候需对所有的文档进行扫描以确保没有遗漏,这样就使得检索时间大大延长,检索效率低下。

2. 正排表举例

  正排索引(一个doc对应许多关键词):
  Doc1: [Term1, Pos1], [Term2, Pos2], …
  Doc2: [Term1, Pos1], [Term2, Pos2], …
  原文档

文档编号(id) 文档内容
1 我喜欢数学
2 我喜欢编程
3 我考试数学成绩很好
4 编程太难了

  分词之后的正排索引Map<id, list>,Term中包含出现位置、出现次数

文档编号(id) 分词后的词项集合(list
1 {我,喜欢,数学}
2 {我,喜欢,编程}
3 {我,考试,数学,成绩,很好}
4 {编程,太难了}

3. 检索过程

  由id查询Term的过程,是正排索引。
  在搜索引擎中每个文件都对应一个文件ID,文件内容被表示为一系列关键词的集合(实际上在搜索引擎索引库中,关键词也已经转换为关键词ID。简单的,正排索引可以理解为(文件内容会对应一个分词后的集合list<< Term>>) Map< id,list< Term>>,能够由id快速(时间复杂度O(1))找到内容的一个数据结构。
  假设使用正向索引,那么当你搜索一个Term的时候,搜索引擎必须检索网页中的每一个关键词,假设一个doc中包含成千上百个关键词,可想而知,会造成大量的资源浪费。于是倒排索引应运而生。

四、倒排索引(inverted index)

1. 概念

  纠正一个概念:倒排索引这个名字是典型的“渣翻译”,容易造成理解误区。我觉得叫反向索引更合适。不过网上大都叫倒排索引叫习惯了,所以下面我们也这么引用这个名称。
  一个倒排索引由文档中所有不重复词的列表构成,对于其中每个词,有一个包含它的Term列表。

2. 倒排表举例

  倒排索引(一个关键词对应许多doc):
  Term1: [Doc1, Pos1], [Doc2, Pos2], …
  Term2: [Doc1, Pos1], [Doc2, Pos2], …
  原文档(和上面正向索引的原文档一样)

文档编号(id) 文档内容
1 我喜欢数学
2 我喜欢编程
3 我考试数学成绩很好
4 编程太难了

  a) 分词之后的简单的倒排索引Map<token,list< id>>

编号 词元(token) 倒排列表(list< id>)
1 1,2,3
2 喜欢 1,2
3 数学 1,3
4 编程 2,4
5 考试 3
6 成绩 3
7 很好 3
8 太难了 4

  b) 有单词频率信息(TF)的倒排索引Map<item,list< (id;TF)>>
  在单词对应的倒排列表中不仅记录了文档编号,还记载了词元频率信息,即这个词元在某个文档中的出现次数。之所以要记录这个信息,是因为词频信息在搜索结果排序时,计算查询和文档相似度是很重要的一个计算因子,将其记录在倒排列表中,以方便后续排序时进行分值计算。

编号 词元(token) 倒排列表(list< (id;TF)>)
1 (1;1),(2;1),(3;1)
2 喜欢 (1;1),(2,1)
3 数学 (1;1),(3;1)
4 编程 (2;1),(4;1)
5 考试 (3;1)
6 成绩 (3;1)
7 很好 (3;1)
8 太难了 (4;1)

  c) 有词元频率和出现位置(pos)信息的倒排索引Map<Term,list<(id;TF;< pos>)>>

编号 词元(token) 倒排列表(list<(id;TF;< pos>)>)
1 (1;1;<1>),(2;1;<1>,(3;1;<1>)
2 喜欢 (1;1;<2>),(2;1;<2>)
3 数学 (1;1;<3>),(3;1;<3>)
4 编程 (2;1;<3>),(4;1;<1>)
5 考试 (3;1;<3>)
6 成绩 (3;1;<4>)
7 很好 (3;1;<5>)
8 太难了 (4;1;<2>)

3. 检索过程

  由Term查询id的过程,是倒排索引。
  倒排索引可以理解为Map<Term, list< id>>,能够由查询词快速(时间复杂度O(1))找到包含这个查询词的文件的数据结构。
  简单来讲:先分词,再找到每个Term对应的list< id>,最后进行集合求交集的过程。
  分词和倒排查询时间复杂度都是O(1),整个搜索的时间复杂度取决于“求list< id>的交集”,因此实际上问题也变成了求两个集合的交集。
  比如你搜索“喜欢”,搜索引擎可以快速检索出包含“喜欢”搜索词的位置,为后续的相关度和权重计算奠定基础,从而大大加快了返回搜索结果的速度。


  转载请注明: 文渊博客 倒排索引原理

  目录