搜索引擎之倒排索引及其底层算法

时间：2023-03-20 06:40:01 | 来源：电子商务

时间：2023-03-20 06:40:01 来源：电子商务

那个本站的格式似乎跟有道云差的有点远啊，附上有道云的地址：有道云笔记

一、搜索引擎

1、什么是搜索引擎？

搜索引擎就是根据用户需求与一定算法，运用特定策略从互联网检索出制定信息反馈给用户的一门检索技术。如网络爬虫技术、检索排序技术、网页处理技术、大数据处理技术、自然语言处理技术等。[百度百科]

2、搜索引擎的分类

搜索引擎分类一般是按搜索方式分类的：

• 全文搜索引擎：一般是在没有明确检索意图情况下进行的索引，这种搜索方式方便、简捷，并容易获得所有相关信息，但搜索到的信息过于庞杂。例如：百度、搜狗、谷歌等
• 元搜索引擎：不同的搜索引擎性能及其信息反馈能力各有不同。而元搜索引擎就是利用其他搜索引擎之间的优势互补进行搜索的。
• 垂直搜索引擎：有明确搜索意图的情况下进行的检索。例如：汽车之家、小米有品。
• 目录搜索引擎：一般是网站内部常用的检索方式。

3、常用的搜索引擎

对于程序员来说，搜索引擎可是开发面试中经常碰到的。例如：Lucene、Nutch、ElasticSearch、Solandra、IndexTank、Compass、Solr、 LIRE、Egothor等等。

4、搜索引擎的特点：

• 快：他们都有高效的压缩算法，能够快速编码解码。
• 准确：查询的信息准确率比较高。
• 召回率高

*底层算法采用了FOR压缩算法跟RBM算法。解决了速度问题。

底层采用了使用了BM25和TF-IDF算法。提高了准确率和召回率。

例如：ElasticSearch、Lucene使用了倒排索引，最底层的算法是FOR压缩算法跟RBM算法。

二、倒排索引

1、简介

倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。[百度百科]

啥意思？意思是，倒排索引是专门用来通过文件或字符串进行定位文件位置的索引。也就是通过字符串或者是文件内容来搜索文件的索引。

2、为什么倒排索引不用B+树

说起这个，就要不得不提一下数据库的索引，数据库的索引大家都知道，底层数据结构大都是B树或者是B+树。

拿mysql为例，一张数据表：

id	goods_name	……
1	小米	……
2	小米至尊纪念版	……
3	小米 NFC 手机	……
4	蓝牙耳机	……
5	小米耳机	……

1、创建时间长，文件大。分别以id建立索引和goods_name建立索引。通过B+的数据结构，能够发现，B+树存储索引信息了，当咱们以goods_name建立索引就会发现，索引文件会特大。当咱们的索引字段数据越多那索引文件就会越大。建立索引时间也就越长。

别忘了，goods_name这只是咱们制造的数据，一般倒排索引建立索引的字段都是大型文本。

2、其次，树深，IO次数可怕。随着数据越多，比起规律的id字段，goods_name字段数据长度不一致，为了不增加索引树的深度，也就意味，需要增加分支数量。分支数量一多，那就意味每层树的IO判断增加，效率反而下降。极端下，可能会出现层数N*分支数量M的次数IO读写。

3、索引可能会失效。

4、精准度差。

由此可见，大本文的字段直接使用B+树作为底层数据结构建立索引是不合理的。

4、倒排索引

大本文的字段直接使用B+树建立索引是不合理的，那如何优化话呢？

ElasticSearch是这样优化的，生成一张倒排表（Term），四个组成字段：

• Term :单词
• Term Index :数据（单词）索引
• Term Dictionary：数据（单词）字典。数据字典记录单词term
• Posting List：倒排列表。倒排列表记录了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息，每条记录称为一个倒排项(Posting)。根据倒排列表，即可获知哪些文档包含某个单词。

将大文本字段数据组成一个字段去重，组成Term Dictionary，记录每个字段在文本中的位置，组成PostListing，最后以单词信息建立索引(Term Index)，如下图所示。

其数据结构如下：

经过此优化后，由字典索引作为索引，也就是Trie Trees树的节点信息。然后指向最底层的单词形成链表，链表内存储单词对应倒排项列表。倒排项记录了单词在文本中的位置，最后指向文本。

*注意：

1. Trie Trees数据结构，简称字典树/单词查找树/键树。
2. 倒排索引底层的数据结构很多，Trie Trees只是倒排索引中词项索引的数据结构

文件对应结构：

三、算法

1、Term Index的算法

上图大家可能没看懂，他是怎么通过索引找到的单词。这就涉及到一个算法——FST（Finite-State Transducer）算法。

实际上他是通过单词前缀，找到了Term Index，在通过索引编号，确认路径找到了底层链表。

FST中存储的是<单词前缀，以该前缀开头的所有Term的压缩块在磁盘中的位置>，即为前文提到的从 term index 查到对应的 term dictionary 的 block 位置之后，再去磁盘上找 term，大大减少了磁盘的 random access 次数。

打个比方：Term Dictionary 就是新华字典的正文部分包含了所有的词汇，Term Index 就是新华字典前面的索引页，用于表明词汇在哪一页。

具体的树构建过程，举个例子：（下面简单描述下FST的构造过程）

目前有五个单词{"cat","deep","do","dog","dogs"}，这5个单词进行插入构建FST

1）插入“cat”

插入cat，每个字母形成一条边，其中t边指向终点。

2）插入“deep”

与前一个单词“cat”进行最大前缀匹配，发现没有匹配则直接插入，P边指向终点。

3）插入“do”

与前一个单词“deep”进行最大前缀匹配，发现是d，则在d边后增加新边o，o边指向终点。

4）插入“dog”

与前一个单词“do”进行最大前缀匹配，发现是do，则在o边后增加新边g，g边指向终点。

5）插入“dogs”

与前一个单词“dog”进行最大前缀匹配，发现是dog，则在g后增加新边s，s边指向终点。

6）最后构成的图

2 PostingList的算法

为什么要用到压缩算法？

大家可以想一下PostingList，他是指向的单词所在文件位置的集合。可以想象PostingList是如何庞大。

数据说话，假设PostingList存储的数据为{1,2,3,4,5,……,100w}(实际的指针地址是16进制的，不好换算，使用10进制作为例子)

因为都是int数值，所以无论数值多大都是开辟int大小的空间进行存储。100w个数，也就是100w个int。

众所周知int取值范围 -2^31< int <2^31-1,所以int数值存储为31bit，int是有正负值，还有1bit数值位。1int = 32bit = 4Bytes

那么PostingList指针集合存储空间为 100w*4Bytes=400wBytes≈4MB。

大家别忘了，能用到搜索引擎的，数据上百万可是小问题啊！由此可见，必须使用压缩算法，要不计算机磁盘早就爆了。

PostingList用的两种算法

• FOR压缩算法（Frame Of Reference）
• RBM算法（Roaring bitmaps）

FOR压缩算法（Frame Of Reference）如下图：

解释：

1. 假设PostingList 存储的指针位置集合为{73,300,302,332,343,372}
2. 根据上面的演示算法，如果直接存储指针集合需要的内存为24Bytes，占用空间太多，位置在磁盘空间中的位置不确定，太过零碎化。所以还需要优化。
3. 第一次优化：由原先的指针集合改为差值集合，73-0，300-73,302-300……，最后得到差值集合{73,227,2,30,11,29}，在磁盘中占用空间还是为24Bytes。
4. 第二次优化：切分成blocks，数组分开，计算出合适占用最小空间数量的blocks。注意：计算blocks，这块决定了后面的最快压缩和最小压缩两种压缩方式。
5. 上图切成两个blocks：[{73,227,2},{30,11,29}]。blocks-1，最大值为227，227<2^8,所以按照最大数227的8bit开辟空间，为3个8bit的空间来存储{73,227,2}。blocks-2，最大值为30，30<2^5,所以按照最大数30的5bit开辟空间，为3个8bit的空间来存储{30,11,29},为了后期计算压缩包大招，blocks前端加入4bit=1Byte空间存储blocks里面每个数值的占用的空间大小。
6. 最后24bytes压缩为7bytes

RBM算法（Roaring bitmaps)如下图：

解释：

1. 假设PostingList 存储的指针位置集合为{1000,62101,131385,132052,191173,196658}
2. 大家观察会发现数值比较大，而且数值比较散列，就是使用差值，意味差值相差也比较大。最最重要的是数值大于65535。不适合使用FOR算法。
3. 将数值%65535，得到商值与膜值（余数），使用商值+膜值（余数）作为重构集合{(0,1000),(0,62101),(2,313),(2,980),(2,60101),(3,50)}
4. 将新的集合拆分成blocks。假设商值为key，膜值为value，相同key的value构成一个block。
5. 将block存储到容器中。目前有三种容器:

ArrayContainer:存储位数低于16位的value，使用16bit的short数组存储，也就是2Bytes。BitmapContainer：底层为216bits的BitMap数据结构，容器大小固定为8KB。blocks里的元素数量大于4096更换容器为BitmapContainerRunContainer：Lucene5新增的特性，容器为8Bytes。底层为Run-Length Encoding算法以上可以看到数量明显小于<4096，而且数值都小于<65535，使用ArrayContainer进行存储，最后压缩为12bytes

容器转换总结

• ArrayContainer：

如果插入值后容量超过4096，则自动转换为BitmapContainer。因此正常使用的情况下不会出现容量超过4096的ArrayContainer。调用runOptimize()方法时，会比较和RunContainer的空间占用大小，选择是否转换为RunContainer。

• BitmapContainer：

如果删除某值后容量低至4096，则会自动转换为ArrayContainer。因此正常使用的情况下不会出现容量小于4096的BitmapContainer。调用runOptimize()方法时，会比较和RunContainer的空间占用大小，选择是否转换为RunContainer。

• RunContainer：

只有在调用runOptimize()方法才会发生转换，会分别和ArrayContainer、BitmapContainer比较空间占用大小，然后选择是否转换。

*注意：

1、为什么要除以65535

将0-32-bit [0, n) 内的数据劈成 高16位和低16位两部分数据。所以需要%2^16，也就是%65535

2、为什么使用两种数据结构来存储低16位的值：

　　　　short数组：2bit * 4096 = 8KB

　　　　BitMap：存储16位范围内数据 65536/8 = 8192b，

　　所以低于 4096个数，short 数组更省空间。

解释一下：（上图跟下图是一个图，只是轴的数据样式不一样）

上图中的两个函数线。蓝函数线为ArrayContainer,黄函数线为BitmapContainer

上图中的两个函数线。红函数线为ArrayContainer,蓝函数线为BitmapContainer

bitmap存储空间恒定为8K，最大的基数可达到8*1024*8=65536个(bit)

array的基数与存储空间成正比，即基数越大，占用空占越多

通过以上两点我们取两者交相交的点为平衡点，即小于该点array更省空间，大于该点bitmap更省空间。

ArrayContainer函数解释：每个元素给与2Bytes的空间进行存储，随着元素的个数的增多，空间占用逐渐增大

y(占用空间)=x(docsNumbers) * 2bytes

参考网站：

Finite State Transducers：https://www.cnblogs.com/jiu0821/p/7688669.html

es 索引压缩算法：http://xytschool.com/resource/263.html

数据结构与算法-BitMap和RoaringBitmap：https://www.cnblogs.com/ytwang/p/13965856.html

精确去重和Roaring BitMap （咆哮位图）：https://www.jianshu.com/p/b09bb3e7652e

Elasticsearch为啥这么快：https://www.jianshu.com/p/b50d7fdbe544