【推荐系统】倒排索引_faiss 倒排

之前看faiss的时候，倒排索引这里总是没有一个清晰的概念。这次做下记录。

目录

1、概念

2、倒排索引简单实例

1）原始文档内容

2）最简单的倒排索引

3）相对复杂些的倒排索引

4）更加实用的倒排索引

---

1、概念

由属性值来确定记录的位置，因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件，简称倒排文件(inverted file)。

  倒排索引(Inverted Index)：倒排索引是实现“单词-文档矩阵”的一种具体存储形式，通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成：“单词词典”和“倒排文件”。

       单词词典(Lexicon)：搜索引擎的通常索引单位是单词，单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。

       倒排列表(PostingList)：倒排列表记载了出现过 某个单词的所有文档的文档列表 及单词在该文档中出现的位置信息，每条记录称为一个倒排项(Posting)。根据倒排列表，即可获知哪些文档包含某个单词。

       倒排文件(Inverted File)：所有单词的倒排列表往往顺序地存储在磁盘的某个文件里，这个文件即被称之为倒排文件，倒排文件是存储倒排索引的物理文件。

 具体一些（竖着看上图），例如某个单词apple的倒排索引：

以上概念都可以从这个图中看到。 

 

2、倒排索引简单实例

1）原始文档内容

假设文档集合包含五个文档，每个文档内容如下图所示，在图中最左端一栏是每个文档对应的文档编号。我们的任务就是对这个文档集合建立倒排索引。

2）最简单的倒排索引

“单词ID”一栏记录了每个单词的单词编号，第二栏是对应的单词，第三栏即每个单词对应的倒排列表。比如单词“谷歌”，其单词编号为1，倒排列表为{1,2,3,4,5}，说明文档集合中每个文档都包含了这个单词。

3）相对复杂些的倒排索引

与基本索引系统比，在单词对应的倒排列表中不仅记录了文档编号，还记载了单词频率信息（TF），即这个单词在某个文档中的出现次数，之所以要记录这个信息，是因为词频信息在搜索结果排序时，计算查询和文档相似度是很重要的一个计算因子，所以将其记录在倒排列表中，以方便后续排序时进行分值计算。在下图的例子里，单词“创始人”的单词编号为7，对应的倒排列表内容为：（3:1），其中的3代表文档编号为3的文档包含这个单词，数字1代表词频信息，即这个单词在3号文档中只出现过1次。

4）更加实用的倒排索引

实用的倒排索引还可以记载更多的信息，下图索引系统除了记录文档编号和单词频率信息外，额外记载了两类信息，即每个单词对应的“文档频率信息”（TF）以及在倒排列表中 记录单词在某个文档出现的位置信息（<POS>）。

单词ID：记录每个单词的单词编号；
单词：对应的单词；
文档频率：代表文档集合中有多少个文档包含某个单词
倒排列表：包含单词ID及其他必要信息
DocId：单词出现的文档id
TF：单词在某个文档中出现的次数
POS：单词在文档中出现的位置

以单词“加盟”为例，其单词编号为6，文档频率为3，代表整个文档集合中有三个文档包含这个单词，对应的倒排列表为{(2;1;<4>),(3;1;<7>),(5;1;<5>)}，含义是在文档2，3，5出现过这个单词，在每个文档的出现过1次，单词“加盟”在第一个文档的POS是4，即文档的第四个单词是“加盟”。

 

总结

倒排索引主要由两个部分组成：“单词词典”和“倒排文件”。

注意是2个部分！不仅仅只有index。

 

 

转自：什么是倒排索引？