倒排索引基本概念

文档（Document）

一般搜索引擎的处理对象是互联网网页，而文档这个概念更要宽泛一些，代表以文本形式存在的存储对象。相比于网页来说，涵盖更多形式，比如Word、PDF、html、XML等不同格式的文件都可以称为文档，再比如一封邮件、一条短信、一条微博也可以称为文档。

文档集合（Document Collection）

由若干文档构成的集合称为文档集合。比如海量的互联网网页或者大量的电子邮件，都是文档集合的具体例子。

文档编号（Document ID）

在搜索引擎内部，会为文档集合內每个文档赋予一个唯一的内部编号，以此编号作为这个文档的唯一标识，这样方便内部处理。

单词编号（Word ID）

与文档编号类似，搜索引擎内部以唯一的编号来表征某个单词，单词编号可以作为某个单词的唯一表征。

倒排索引（Inverted Index）

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

单词词典（Lexicon）

搜索引擎通常的索引单位是单词，单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典內每条索引项记载单词本身的一些信息及指向倒排列表的指针。所以在用户进行查询的时候，搜索引擎根据用户的查询词，去单词词典里查询，就能够获得相应的倒排列表，并以此作为后续排序的基础。
　　对于一个规模很大的文档集合来说，可能包含几十万甚至上百万不同的单词，能否快速定位某个单词，这直接影响搜索时的相应速度，常用的数据结构包括哈希加链表结构和树形词典结构。

倒排列表（PostingList）

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

倒排文件（Inverted File）

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

倒排索引基本组成

建立倒排索引的步骤：

1.用分词系统将文档自动切分成单词序列。
2.对每个不同的单词赋予唯一的单词编号，并记录下哪些文档包含这个单词。
3.还可以记录单词频率（TF），代表这个单词在某个文档中出现的次数。因为词频信息在搜索结果排序时，是计算查询和文档相似度的一个很重要的计算因子。
4.实用的倒排索引还可以额外记录两类信息：每个单词对应的文档频率信息（DF，文档集合中有多少个文档包含了这个单词），及单词在某个文档中出现的位置信息（POS）。

文档集合 最简单的倒排索引 带有TF、IDF、POS的倒排索引

参考文献:
[1] 张俊林. 这就是搜索引擎[M]. 电子工业出版社, 2012.