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

時(shí)間：2023-03-20 06:40:01 | 來(lái)源：電子商務(wù)

時(shí)間：2023-03-20 06:40:01 來(lái)源：電子商務(wù)

那個(gè)本站的格式似乎跟有道云差的有點(diǎn)遠(yuǎn)啊，附上有道云的地址：有道云筆記

一、搜索引擎

1、什么是搜索引擎？

搜索引擎就是根據(jù)用戶需求與一定算法，運(yùn)用特定策略從互聯(lián)網(wǎng)檢索出制定信息反饋給用戶的一門(mén)檢索技術(shù)。如網(wǎng)絡(luò)爬蟲(chóng)技術(shù)、檢索排序技術(shù)、網(wǎng)頁(yè)處理技術(shù)、大數(shù)據(jù)處理技術(shù)、自然語(yǔ)言處理技術(shù)等。[百度百科]

2、搜索引擎的分類

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

• 全文搜索引擎：一般是在沒(méi)有明確檢索意圖情況下進(jìn)行的索引，這種搜索方式方便、簡(jiǎn)捷，并容易獲得所有相關(guān)信息，但搜索到的信息過(guò)于龐雜。例如：百度、搜狗、谷歌等
• 元搜索引擎：不同的搜索引擎性能及其信息反饋能力各有不同。而元搜索引擎就是利用其他搜索引擎之間的優(yōu)勢(shì)互補(bǔ)進(jìn)行搜索的。
• 垂直搜索引擎：有明確搜索意圖的情況下進(jìn)行的檢索。例如：汽車之家、小米有品。
• 目錄搜索引擎：一般是網(wǎng)站內(nèi)部常用的檢索方式。

3、常用的搜索引擎

對(duì)于程序員來(lái)說(shuō)，搜索引擎可是開(kāi)發(fā)面試中經(jīng)常碰到的。例如：Lucene、Nutch、ElasticSearch、Solandra、IndexTank、Compass、Solr、 LIRE、Egothor等等。

4、搜索引擎的特點(diǎn)：

• 快：他們都有高效的壓縮算法，能夠快速編碼解碼。
• 準(zhǔn)確：查詢的信息準(zhǔn)確率比較高。
• 召回率高

*底層算法采用了FOR壓縮算法跟RBM算法。解決了速度問(wèn)題。

底層采用了使用了BM25和TF-IDF算法。提高了準(zhǔn)確率和召回率。

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

二、倒排索引

1、簡(jiǎn)介

倒排索引源于實(shí)際應(yīng)用中需要根據(jù)屬性的值來(lái)查找記錄。這種索引表中的每一項(xiàng)都包括一個(gè)屬性值和具有該屬性值的各記錄的地址。由于不是由記錄來(lái)確定屬性值，而是由屬性值來(lái)確定記錄的位置，因而稱為倒排索引(inverted index)。[百度百科]

啥意思？意思是，倒排索引是專門(mén)用來(lái)通過(guò)文件或字符串進(jìn)行定位文件位置的索引。也就是通過(guò)字符串或者是文件內(nèi)容來(lái)搜索文件的索引。

2、為什么倒排索引不用B+樹(shù)

說(shuō)起這個(gè)，就要不得不提一下數(shù)據(jù)庫(kù)的索引，數(shù)據(jù)庫(kù)的索引大家都知道，底層數(shù)據(jù)結(jié)構(gòu)大都是B樹(shù)或者是B+樹(shù)。

拿mysql為例，一張數(shù)據(jù)表：

id	goods_name	……
1	小米	……
2	小米至尊紀(jì)念版	……
3	小米 NFC 手機(jī)	……
4	藍(lán)牙耳機(jī)	……
5	小米耳機(jī)	……

1、創(chuàng)建時(shí)間長(zhǎng)，文件大。分別以id建立索引和goods_name建立索引。通過(guò)B+的數(shù)據(jù)結(jié)構(gòu)，能夠發(fā)現(xiàn)，B+樹(shù)存儲(chǔ)索引信息了，當(dāng)咱們以goods_name建立索引就會(huì)發(fā)現(xiàn)，索引文件會(huì)特大。當(dāng)咱們的索引字段數(shù)據(jù)越多那索引文件就會(huì)越大。建立索引時(shí)間也就越長(zhǎng)。

別忘了，goods_name這只是咱們制造的數(shù)據(jù)，一般倒排索引建立索引的字段都是大型文本。

2、其次，樹(shù)深，IO次數(shù)可怕。隨著數(shù)據(jù)越多，比起規(guī)律的id字段，goods_name字段數(shù)據(jù)長(zhǎng)度不一致，為了不增加索引樹(shù)的深度，也就意味，需要增加分支數(shù)量。分支數(shù)量一多，那就意味每層樹(shù)的IO判斷增加，效率反而下降。極端下，可能會(huì)出現(xiàn)層數(shù)N*分支數(shù)量M的次數(shù)IO讀寫(xiě)。

3、索引可能會(huì)失效。

4、精準(zhǔn)度差。

由此可見(jiàn)，大本文的字段直接使用B+樹(shù)作為底層數(shù)據(jù)結(jié)構(gòu)建立索引是不合理的。

4、倒排索引

大本文的字段直接使用B+樹(shù)建立索引是不合理的，那如何優(yōu)化話呢？

ElasticSearch是這樣優(yōu)化的，生成一張倒排表（Term），四個(gè)組成字段：

• Term :單詞
• Term Index :數(shù)據(jù)（單詞）索引
• Term Dictionary：數(shù)據(jù)（單詞）字典。數(shù)據(jù)字典記錄單詞term
• Posting List：倒排列表。倒排列表記錄了出現(xiàn)過(guò)某個(gè)單詞的所有文檔的文檔列表及單詞在該文檔中出現(xiàn)的位置信息，每條記錄稱為一個(gè)倒排項(xiàng)(Posting)。根據(jù)倒排列表，即可獲知哪些文檔包含某個(gè)單詞。

將大文本字段數(shù)據(jù)組成一個(gè)字段去重，組成Term Dictionary，記錄每個(gè)字段在文本中的位置，組成PostListing，最后以單詞信息建立索引(Term Index)，如下圖所示。

其數(shù)據(jù)結(jié)構(gòu)如下：

經(jīng)過(guò)此優(yōu)化后，由字典索引作為索引，也就是Trie Trees樹(shù)的節(jié)點(diǎn)信息。然后指向最底層的單詞形成鏈表，鏈表內(nèi)存儲(chǔ)單詞對(duì)應(yīng)倒排項(xiàng)列表。倒排項(xiàng)記錄了單詞在文本中的位置，最后指向文本。

*注意：

1. Trie Trees數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)稱字典樹(shù)/單詞查找樹(shù)/鍵樹(shù)。
2. 倒排索引底層的數(shù)據(jù)結(jié)構(gòu)很多，Trie Trees只是倒排索引中詞項(xiàng)索引的數(shù)據(jù)結(jié)構(gòu)

文件對(duì)應(yīng)結(jié)構(gòu)：

三、算法

1、Term Index的算法

上圖大家可能沒(méi)看懂，他是怎么通過(guò)索引找到的單詞。這就涉及到一個(gè)算法——FST（Finite-State Transducer）算法。

實(shí)際上他是通過(guò)單詞前綴，找到了Term Index，在通過(guò)索引編號(hào)，確認(rèn)路徑找到了底層鏈表。

FST中存儲(chǔ)的是<單詞前綴，以該前綴開(kāi)頭的所有Term的壓縮塊在磁盤(pán)中的位置>，即為前文提到的從 term index 查到對(duì)應(yīng)的 term dictionary 的 block 位置之后，再去磁盤(pán)上找 term，大大減少了磁盤(pán)的 random access 次數(shù)。

打個(gè)比方：Term Dictionary 就是新華字典的正文部分包含了所有的詞匯，Term Index 就是新華字典前面的索引頁(yè)，用于表明詞匯在哪一頁(yè)。

具體的樹(shù)構(gòu)建過(guò)程，舉個(gè)例子：（下面簡(jiǎn)單描述下FST的構(gòu)造過(guò)程）

目前有五個(gè)單詞{"cat","deep","do","dog","dogs"}，這5個(gè)單詞進(jìn)行插入構(gòu)建FST

1）插入“cat”

插入cat，每個(gè)字母形成一條邊，其中t邊指向終點(diǎn)。

2）插入“deep”

與前一個(gè)單詞“cat”進(jìn)行最大前綴匹配，發(fā)現(xiàn)沒(méi)有匹配則直接插入，P邊指向終點(diǎn)。

3）插入“do”

與前一個(gè)單詞“deep”進(jìn)行最大前綴匹配，發(fā)現(xiàn)是d，則在d邊后增加新邊o，o邊指向終點(diǎn)。

4）插入“dog”

與前一個(gè)單詞“do”進(jìn)行最大前綴匹配，發(fā)現(xiàn)是do，則在o邊后增加新邊g，g邊指向終點(diǎn)。

5）插入“dogs”

與前一個(gè)單詞“dog”進(jìn)行最大前綴匹配，發(fā)現(xiàn)是dog，則在g后增加新邊s，s邊指向終點(diǎn)。

6）最后構(gòu)成的圖

2 PostingList的算法

為什么要用到壓縮算法？

大家可以想一下PostingList，他是指向的單詞所在文件位置的集合?？梢韵胂驪ostingList是如何龐大。

數(shù)據(jù)說(shuō)話，假設(shè)PostingList存儲(chǔ)的數(shù)據(jù)為{1,2,3,4,5,……,100w}(實(shí)際的指針地址是16進(jìn)制的，不好換算，使用10進(jìn)制作為例子)

因?yàn)槎际莍nt數(shù)值，所以無(wú)論數(shù)值多大都是開(kāi)辟int大小的空間進(jìn)行存儲(chǔ)。100w個(gè)數(shù)，也就是100w個(gè)int。

眾所周知int取值范圍 -2^31< int <2^31-1,所以int數(shù)值存儲(chǔ)為31bit，int是有正負(fù)值，還有1bit數(shù)值位。1int = 32bit = 4Bytes

那么PostingList指針集合存儲(chǔ)空間為 100w*4Bytes=400wBytes≈4MB。

大家別忘了，能用到搜索引擎的，數(shù)據(jù)上百萬(wàn)可是小問(wèn)題?。∮纱丝梢?jiàn)，必須使用壓縮算法，要不計(jì)算機(jī)磁盤(pán)早就爆了。

PostingList用的兩種算法

• FOR壓縮算法（Frame Of Reference）
• RBM算法（Roaring bitmaps）

FOR壓縮算法（Frame Of Reference）如下圖：

解釋：

1. 假設(shè)PostingList 存儲(chǔ)的指針位置集合為{73,300,302,332,343,372}
2. 根據(jù)上面的演示算法，如果直接存儲(chǔ)指針集合需要的內(nèi)存為24Bytes，占用空間太多，位置在磁盤(pán)空間中的位置不確定，太過(guò)零碎化。所以還需要優(yōu)化。
3. 第一次優(yōu)化：由原先的指針集合改為差值集合，73-0，300-73,302-300……，最后得到差值集合{73,227,2,30,11,29}，在磁盤(pán)中占用空間還是為24Bytes。
4. 第二次優(yōu)化：切分成blocks，數(shù)組分開(kāi)，計(jì)算出合適占用最小空間數(shù)量的blocks。注意：計(jì)算blocks，這塊決定了后面的最快壓縮和最小壓縮兩種壓縮方式。
5. 上圖切成兩個(gè)blocks：[{73,227,2},{30,11,29}]。blocks-1，最大值為227，227<2^8,所以按照最大數(shù)227的8bit開(kāi)辟空間，為3個(gè)8bit的空間來(lái)存儲(chǔ){73,227,2}。blocks-2，最大值為30，30<2^5,所以按照最大數(shù)30的5bit開(kāi)辟空間，為3個(gè)8bit的空間來(lái)存儲(chǔ){30,11,29},為了后期計(jì)算壓縮包大招，blocks前端加入4bit=1Byte空間存儲(chǔ)blocks里面每個(gè)數(shù)值的占用的空間大小。
6. 最后24bytes壓縮為7bytes

RBM算法（Roaring bitmaps)如下圖：

解釋：

1. 假設(shè)PostingList 存儲(chǔ)的指針位置集合為{1000,62101,131385,132052,191173,196658}
2. 大家觀察會(huì)發(fā)現(xiàn)數(shù)值比較大，而且數(shù)值比較散列，就是使用差值，意味差值相差也比較大。最最重要的是數(shù)值大于65535。不適合使用FOR算法。
3. 將數(shù)值%65535，得到商值與膜值（余數(shù)），使用商值+膜值（余數(shù)）作為重構(gòu)集合{(0,1000),(0,62101),(2,313),(2,980),(2,60101),(3,50)}
4. 將新的集合拆分成blocks。假設(shè)商值為key，膜值為value，相同key的value構(gòu)成一個(gè)block。
5. 將block存儲(chǔ)到容器中。目前有三種容器:

ArrayContainer:存儲(chǔ)位數(shù)低于16位的value，使用16bit的short數(shù)組存儲(chǔ)，也就是2Bytes。BitmapContainer：底層為216bits的BitMap數(shù)據(jù)結(jié)構(gòu)，容器大小固定為8KB。blocks里的元素?cái)?shù)量大于4096更換容器為BitmapContainerRunContainer：Lucene5新增的特性，容器為8Bytes。底層為Run-Length Encoding算法以上可以看到數(shù)量明顯小于<4096，而且數(shù)值都小于<65535，使用ArrayContainer進(jìn)行存儲(chǔ)，最后壓縮為12bytes

容器轉(zhuǎn)換總結(jié)

• ArrayContainer：

如果插入值后容量超過(guò)4096，則自動(dòng)轉(zhuǎn)換為BitmapContainer。因此正常使用的情況下不會(huì)出現(xiàn)容量超過(guò)4096的ArrayContainer。調(diào)用runOptimize()方法時(shí)，會(huì)比較和RunContainer的空間占用大小，選擇是否轉(zhuǎn)換為RunContainer。

• BitmapContainer：

如果刪除某值后容量低至4096，則會(huì)自動(dòng)轉(zhuǎn)換為ArrayContainer。因此正常使用的情況下不會(huì)出現(xiàn)容量小于4096的BitmapContainer。調(diào)用runOptimize()方法時(shí)，會(huì)比較和RunContainer的空間占用大小，選擇是否轉(zhuǎn)換為RunContainer。

• RunContainer：

只有在調(diào)用runOptimize()方法才會(huì)發(fā)生轉(zhuǎn)換，會(huì)分別和ArrayContainer、BitmapContainer比較空間占用大小，然后選擇是否轉(zhuǎn)換。

*注意：

1、為什么要除以65535

將0-32-bit [0, n) 內(nèi)的數(shù)據(jù)劈成 高16位和低16位兩部分?jǐn)?shù)據(jù)。所以需要%2^16，也就是%65535

2、為什么使用兩種數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)低16位的值：

　　　　short數(shù)組：2bit * 4096 = 8KB

　　　　BitMap：存儲(chǔ)16位范圍內(nèi)數(shù)據(jù) 65536/8 = 8192b，

　　所以低于 4096個(gè)數(shù)，short 數(shù)組更省空間。

解釋一下：（上圖跟下圖是一個(gè)圖，只是軸的數(shù)據(jù)樣式不一樣）

上圖中的兩個(gè)函數(shù)線。藍(lán)函數(shù)線為ArrayContainer,黃函數(shù)線為BitmapContainer

上圖中的兩個(gè)函數(shù)線。紅函數(shù)線為ArrayContainer,藍(lán)函數(shù)線為BitmapContainer

bitmap存儲(chǔ)空間恒定為8K，最大的基數(shù)可達(dá)到8*1024*8=65536個(gè)(bit)

array的基數(shù)與存儲(chǔ)空間成正比，即基數(shù)越大，占用空占越多

通過(guò)以上兩點(diǎn)我們?nèi)烧呓幌嘟坏狞c(diǎn)為平衡點(diǎn)，即小于該點(diǎn)array更省空間，大于該點(diǎn)bitmap更省空間。

ArrayContainer函數(shù)解釋：每個(gè)元素給與2Bytes的空間進(jìn)行存儲(chǔ)，隨著元素的個(gè)數(shù)的增多，空間占用逐漸增大

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

參考網(wǎng)站：

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

es 索引壓縮算法：http://xytschool.com/resource/263.html

數(shù)據(jù)結(jié)構(gòu)與算法-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