第二章 倒排索引原理

一 概念

倒排索引(Inverted index) 倒排索引是一种将词项映射到文档的数据结构，这与传统关系型数据库的工作方式不同。你可以把倒排索引当做面向词项的而不是面向文档的数据结构。

二 倒排索引实例

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

• (1) 中文和英文等语言不同，单词之间没有明确分隔符号，所以首先要用分词系统将文档自动切分成单词序列。这样每个文档就转换为由单词序列构成的数据流，为了系统后续处理方便，需要对每个不同的单词赋予唯一的单词编号，同时记录下哪些文档包含这个单词，在如此处理结束后，我们可以得到最简单的倒排索引。在下图中，“单词ID”一栏记录了每个单词的单词编号，第二栏是对应的单词，第三栏即每个单词对应的倒排列表。比如单词“谷歌”，其单词编号为1，倒排列表为{1,2,3,4,5}，说明文档集合中每个文档都包含了这个单词。

  
  

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

  
  倒排索引详解可以参考csdn博客 倒排索引

三 倒排索引数据结构与核心算法

倒排索引分为倒排表(posting_list)、词项字典(term dictionary)、词项索引(term index)三部分组成 其中倒排表是一个int类型的有序数组 存储了匹配某个term(词汇)的所有文档的id 词项字典分为三部分组成 tip、tim、doc(各个部分的含义如上图)

四 倒排索引的核心算法

• 倒排表的压缩算法
  • FOR(Frame Of Reference)
  • RBM(RoaringBitmap)
• 词项索引的检索原理
  • FST(Finit state Transducers)

4.1 FOR(Frame Of Reference)

Frame Of Reference 又叫增量编码压缩, 首先Elasticsearch要求倒排索引是有序的(也就是文档id是有序排列的) 如下图所示

• 第一步 压缩前 文档id列表为 73 300 302 332 343 372 这样的一个有序的文档id集合
• 第二步 然后es会先将这些文档id的delta(也就是差值)的值计算出来。227 = 300 - 73 2 = 302 - 300 依次类推 这样做的好处是可以缩小int的数值。
• 第三步 将第二步计算出来的值进行分块 每一个小块(73 227 2 为一个块 30 11 29 为另一个块) 取最大值 如第一个块最大的值是227 而2的8次方为256>227 所以这一个块中的(73 227 2) 每一个数字都可以用8个bit位来存储，另外还需要一个字节来标识 每一个数据块是用多少bit位来存储一个数字的(绿色标识的位置 这个标志位固定8个bit是为了解压缩的时候 能够方便的知道每一个数据块是用多少bit位来存储一个数)
• 压缩后一共大约是7个字节的样子 而没压缩之前是6*8=24个字节

4.2 RBM压缩算法

RBM压缩算法也叫RoaringBitmap算法 将一个32位无符号整数按照高16位分块处理，其中高16位作为索引存储在short数组中，低16位作为数据存储在某个特定的Container数组中。存储数据时，先根据高16位找到对应的索引key（二分查找），由于key和value是一一对应的，即找到了对应的Container。若key存在则将低16位放入对应的Container中，若不存在则创建一个key和对应的Container，并将低16位放入Container中 如下图

其中container又分为 ArrayContainer、BitmapContainer、RunContainer三钟

• ArrayContainer ArrayContainer采用简单的short数组存储低16位数据，content始终有序且不重复，方便二分查找
  可以看出，ArrayContainer并没有采用任何的压缩算法，只是简单的将低16存储在short[]中 short为2字节，因此n个数据为2n字节
  随着数据量的增大，ArrayContainer占用的内存空间逐渐增多，且由于是二分查找，时间复杂度为O(logn)，查找效率也会大打折扣，因此ArrayContainer规定最大数据量是4096，即8kb
• BitmapContainer BitmapContainer采用long数组存储低16位数据，这就是一个未压缩的普通位图，每一个bit位置代表一个数字。我们上面说过每一个Container最多可以处理216个数字，基于位图的原理，我们就需要216个bit，每个long是8字节64bit，所以需要216/64=1024个long BitmapContainer构造方法会初始化一个长度为1024的long数组，因此BitmapContainer无论是存1个数据，10个数据还是最大65536个数据，都始终占据着8kb的内存空间。
• RunContainer 在RBM创立初期只有以上两种容器，RunContainer其实是在后期加入的。RunContainer是基于之前提到的RLE算法进行压缩的，主要解决了大量连续数据的问题。举例说明：3,4,5,10,20,21,22,23这样一组数据会被优化成3,2,10,0,20,3，原理很简单，就是记录初始数字以及连续的数量，并把压缩后的数据记录在short数组中显而易见，这种压缩方式对于数据的疏密程度非常敏感，举两个最极端的例子：如果这个Container中所有数据都是连续的，也就是[0,1,2.....65535]，压缩后为0,65535，即2个short，4字节。若这个Container中所有数据都是间断的（都是偶数或奇数），也就是[0,2,4,6....65532,65534]，压缩后为0,0,2,0.....65534,0，这不仅没有压缩反而膨胀了一倍，65536个short，即128kb 因此是否选择RunContainer是需要判断的，RBM提供了一个转化方法runOptimize()用于对比和其他两种Container的空间大小，若占据优势则会进行转化

4.3 FOR压缩算法与RBM算法的适用场景

For算法是一种增量编码压缩算法 所以它适合处理的是数据分布比较致密的数组(也就是说数组相邻元素之间的差值不能太大 如果值太大则压缩效果不好) 而RBM算法则没有这种要求。如果在数据量比较大的时候采用bitmapContainer则会极大的减少存储空间

4.4 字典树(trie树)

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

• 前缀树的3个基本性质

  1、根节点不包含字符，除根节点外每一个节点都只包含一个字符
  2、从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
  3、每个节点的所有子节点包含的字符都不相同