倒排索引

定义

倒排索引(Inverted index)是一种常见的索引方法，其几乎是文档或信息检索系统中最常用的数据结构，适用于快速的全文搜索。

倒排索引可理解为：关键词——>文档
区分于正排索引：文档——>关键词

一个倒排索引由全部文档集合中所有不重复的单词的列表构成，对每一个单词，通常有一个包含其的文档列表与之对应。

假设有三个候选文档，每个文档的内容如下：

1
2
3

D_0 = {i love hadoop}
D_1 = {i love ruc}
D_2 = {i love ruc and love hadoop}

要创建倒排索引，首先需要将每个文档中的单词拆分为单独的词(token)，并且列出每个单词归属于哪个文档，在实际使用时，还会给单词赋予权重，例如词频，即该单词在文档中的出现次数：

"and":      {2:1}
"hadoop":   {0:1,2:1}
"i":        {0:1,1:1,2:1}
"love":     {0:1,1:1,2:2}
"ruc":      {1:1,2:1}

当键入检索内容"i" "love" "hadoop"时，其结果将对应{0,1,2} ∩ {0,1,2} ∩ {0,2} = {0, 2}，即文档D_0和D_2包含了该索引下的单词。