正排索引与倒排索引

什么是正排索引（forward index）？

由key查询实体的过程，是正排索引.

在搜索引擎中每个文件都对应一个文件ID，文件内容被表示为一系列关键词的集合（实际上在搜索引擎索引库中，关键词也已经转换为关键词ID）。简单的，正排索引可以理解为(文件内容会对应一个分词后的集合list<< item >>)Map>，能够由id快速（时间复杂度O(1)）找到内容的一个数据结构。

什么是倒排索引（inverted index）？

由item查询key的过程，是倒排索引。

倒排索引可以理解为Map<item, list< id>>，能够由查询词快速（时间复杂度O(1)）找到包含这个查询词的文件的数据结构。

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

分词之后的正排索引Map<id, list< item>>

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

分词后倒排索引

  • 简单的倒排索引Map>
编号 单词（item） 倒排列表(list< id>)
1 我 1,2,3
2 喜欢 1,2
3 数学 1,3
4 编程 2,4
5 考试 3
6 成绩 3
7 很好 3
8 太难了 4

  • 有单词频率信息（TF）的倒排索引Map>

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

编号 单词（item） 倒排列表(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)
  • 有单词频率和出现位置(pos)信息的倒排索引Map)>>
编号 单词（item） 倒排列表(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>)

用户检索过程？

简单来讲：先分词，再找到每个item对应的list< id>,最后进行集合求交集的过程。
分词和倒排查询时间复杂度都是O(1)，整个搜索的时间复杂度取决于“求list的交集”，因此实际上问题也变成了求两个集合的交集。

版权声明：本文为Onlywjy原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/Onlywjy/p/8372452.html