使用百度文心一格生成的图

在正式介绍倒排索引之前，先看一个问题吧！请列出一句或多句包含圆的古诗词

正常情况下，没有经过特别训练，一下就能想出有点难度。

那么我给点提示呢，王维的《使至塞上》、苏轼的《水调歌头》，或许你稍微想一下，就能知道答案了！

这种通过作者和题目就能想到古诗句，这种我们称之为正向索引。正向索引应用广泛，能在海量的数据中精确定位到你想要的数据。

那么通过指定关键字来搜寻古诗词句，如果用正向索引，他的效率就会很低下，那么有没有一种有效的方案策略呢？我们使用的百度搜索，他们是怎么做到的呢？答案就是今天要展开的倒排索引

还是借用上面的问题，我们将古诗词句进行关键字拆分并存储

大漠孤烟直，长河落日圆，我可以拆分成几个关键字圆、直

人有悲欢离合，月有阴晴圆缺，此事古难全可以拆成几个关键字，圆、月

那么回到问题的开始，请列出一句或多句包含圆的古诗词，那么你是不是可以使用关键字圆进行检索，然后检索到了对应的古诗词编号1和2，然后使用正向索引，一下就能找到对应的古诗词句。

这个就是倒排索引的妙用。倒排索引创建的过程大致包含四个步骤。

第一，切词，顾名思义就是将一整句话拆分成几个关键词，怎么拆你可以不用管，因为已经有很多成熟的分词器了，使用不同的分词器效果有所不同

第二，规范化，规范化就是去掉一些语气词，统一大小写、去分词。比如CAR、car这两个是同一个词，会统一规范，还比如中文中的地得等词，没有特殊含义，会直接去掉，比如have、had、having，这三个词本身也是同一个词，会统一规范

第三，去重，也就是这个关键字不会重复

第四，字典化，这个也很简单，就是格式化存储。

那么倒排索引有什么问题吗？我认为最主要的问题就是切词后数据量倍增增加，比如大漠孤烟直，长河落日圆，实际情况下，我可能需要拆分成圆、直、大漠、烟、落日等，相当于这一条数据，我需要创建的字典就有5条明细。

这个对于存储来说是一件不可控的事情！那么，官方有没有解决方案呢？

既然倒排索引使用广泛，那肯定是有方案解决的，答案就是数据压缩。

倒排索引分为三部分，倒排表（Posting List）、词项字典（term dictionary）、词项索引（term index），上图中的关键字就是词项字典，对应的古诗词编号就是倒排表，这里我们只讨论倒排表的数据压缩。

倒排表的数据压缩算法有两种，FOR（Frame Of Reference）算法和RBM算法(RoaringBitMap)，因为篇幅原因，这里先介绍FOR压缩算法。

词项字典中的数据是一个int数组，并且是已经排序好的。我们都知道int是占用4个字节来存储数据的，1Byte=8bit，也就是一个int数字需要占4*8=32个bit，也就是32个二进制位，去掉首位表示符号位，int最大值是2^31

从网上扒来一张图，来很好的说明这个压缩算法

原始数组是[73,300,302,332,343,372]，不使用压缩算法，就是6*4Byte=24Byte

使用FOR算法的步骤如下

第一步，将数组的每一项减去前一项，得到一个新数组[73,227,2,30,11,29]，用这个新数组也能很快的复原原始数组

第二步，将数据分组，这里将73,227,2前三个数据分为一组，后三个30,11,29数据分为一组

第三步，压缩。可以看到前三个数据中最大的是227，小于2的8次幂256，说明可以定义一种新的数据类型，这个类型用8个bit来表示一个数字，累计就是8*3=24bit为3Byte，再加上定义这个新的数据类型需要一个Byte，也就是前三个数据需要4Byte，同理后面三个数字需要用3Byte，压缩后整个数组就是需要7Byte，相比不压缩的24Byte，存储空间下降了70.83%

可以看到，使用这个压缩算法，在数据分布比较均匀的情况下，压缩比率是惊人的。但假如数据分布不均匀，前后的数字相差依然很大，这种数据分布使用FOR压缩算法效果就不明显了，这种情况下，就需要使用RBM了。

RBM算法的介绍，将放在下一篇，未完待续！