倒排索引基础知识

ElasticSearch的全文搜索是基于Apache Lucene的，Apache Lucene是一个全文搜索库，其核心处理步骤一般是：

1. 获得一个文档，对需要进行全文搜索的字段进行处理(分词、标记过滤、字符映射)。
2. 对最终获得的标记进行词频分析和建立倒排索引，并入库。
3. 当有全文索引请求到来时，查询倒排索引，获得相关文档并评分返回。

本篇重点介绍倒排索引的概念。

1.单词-文档矩阵

单词-文档矩阵是一种表达两者之间包含关系的模型，这种模型非常适合于全文索引的场景。下图中行表示词，列表示文档，
打钩表示某文档包含某词：

一般来讲，我们可以从两个角度来看这个矩阵：

1. 横向角度：表示有哪些文档包含了某词。
2. 纵向角度：表示某个文档包含了哪些词。

搜索引擎中建立的索引可说就是单词-文档矩阵的某种模型，现在应用得比较多的就是倒排索引了。

2.倒排索引的基本概念

1. 文档(Document)：这里文档的概念比较宽泛，所有能被存储的文本信息都可被称为文档。例如网页、XML、Word文件、一封Email、一条微博等等。
2. 文档集合(Document Collection)：由若干文档构成的集合就叫文档集合。
3. 文档编号(Document ID)：搜索引擎会为文档集合中的每个文档赋予一个唯一的内部编号(在它所处的文档集合中是唯一的)，以方便处理。
4. 倒排索引(Inverted Index)：是一种实现单词-文档矩阵的具体方式，通过倒排索引可以通过单词信息快速获取到包含这个单词的所有文档列表。倒排索引主要由两个部分组成：“单词词典”和“倒排文件”。
5. 单词词典(Lexicon)：搜索引擎索引单位一般是单词(或多个单词组合)，单词词典是由文档集合中出现过的所有单词构成的一个字符串集合，单词词典内每条索引项记载着单词本身的信息以及指向倒排列表的指针。
6. 倒排列表(Posting List)：倒排列表记录了出现过某个单词的所有文档的文档列表和改单词在这些文档中出现的位置信息，每条记录称为一个“倒排项”，根据倒排列表，就可以获知有哪些文档包含了某个单词。
7. 倒排文件(Inverted File)：所有单词的倒排列表一般顺序存储在磁盘的某个文件中，这就是倒排文件，倒排文件是存储倒排索引的物理文件。

示例如下图：

3.倒排索引实例

从理论上来解释倒排索引还是比较清晰的，不过还是再来看一个真是的示例。

上图包含5个文档，我们要对这5个文档建立倒排索引。

首先使用分词器、标记过滤器、字符映射器处理文本，得到一个个单词，然后建立如下倒排索引：

更近一步，我们还可以记录每个单词在包含它的文档中出现的次数(词频)，词频对于在搜索排序中计算和查询文档相似度是一个重要的因子，事先将其放在倒排索引中可以方便后续的相关计算。

再进一步，还可以记录文档频率信息(文档集合中有多少个文档包含某个单词)和目标单词在文档中出现的位置信息等。

基本上大部分搜索引擎的倒排索引就是这个结构，只是实现方式有所不同罢了。

一个基本的流程如下：

1. 用户输入某个单词进行搜索。
2. 搜索引擎查询事先准备好的倒排索引，找到对应的倒排文件，获得所有包含查询单词的文档列表。
3. 获得文档列表后，根据单词频率信息、文档频率信息计算相似性并对这些文档排序。
4. 输出给用户。

4.单词词典的实现

比较常见的实现有：

1. 哈希链表
2. B树/B+树

哈希链表：

B+树