首先需要大致知道搜索引擎有大致幾類：1.全文搜索引擎 2.垂直搜索引擎 3.類目搜索引擎等。

1.全文搜索引擎：是全文本覆蓋的，百度，google等都是全文本搜索，就是我搜一個詞項“方圓”，那么這個詞項可以是數(shù)字平方的概念，可以是一個人名，可以是一首歌等，所有的相關分類的概念都會被檢索到。檢索范圍是全覆蓋的，也就是中間涉及到語義的概念。

2.垂直檢索引擎：就是檢索一個詞項，在一個語義范圍內(nèi)檢索，檢索范圍在一個語義內(nèi)的。

3.類目檢索引擎：一般就是我們所見到互聯(lián)網(wǎng)公司建設的搜索引擎，比如電商，一個詞項檢索就是檢索自己所有的商品類目，或者汽車之家，就是檢索所有的汽車類目。

建設搜索引擎，肯定在數(shù)據(jù)量上都是海量數(shù)據(jù)，而且要求數(shù)據(jù)檢索返回速率很快，一般都是秒級返回（通常衡量檢索引擎的指標有1.準確率 BM25/TF-IDF 2.召回率）。我們都知道一個數(shù)據(jù)庫的表要是表中的數(shù)據(jù)幾十億條數(shù)據(jù)，我們select where 條件具有索引，時間也遠不止一秒。所以檢索引擎不是單單索引的建立那么簡單。而且檢索引擎的概念是select *? like;是模糊匹配，不是固定匹配，所以檢索更是范圍巨大，遠不是數(shù)據(jù)庫索引檢索那么簡單。

搜索引擎在原理上很關鍵的幾點，想到大家也會想到，1.數(shù)據(jù)結構的設計 2.索引結構的設計 3.數(shù)據(jù)存儲方面的數(shù)據(jù)壓縮機制（壓縮之后檢索更加高效）。首先我們先了解傳統(tǒng)上數(shù)據(jù)的索引的數(shù)據(jù)結構B-Tree和B+tree.

這是B樹，但是需要普及一個知識點，不然大家不知道樹存儲到磁盤，在讀取的時候涉及到的IO次數(shù)。我們磁盤最小的單元是一個扇區(qū)（512B）,操作系統(tǒng)最小的讀取單位是一簇4KB（8個扇區(qū)）,那么我們在設置每一個樹的節(jié)點也最小是4KB（在mysql中數(shù)據(jù)文件存儲是16KB為一頁，數(shù)據(jù)葉是最小存儲單位）。那么B樹每一個節(jié)點也要存儲數(shù)據(jù)，如果數(shù)據(jù)部分很大，那么每一個節(jié)點上存儲的分支個數(shù)就少了，那么樹的深度自然要加大，那么在便利數(shù)據(jù)的時候，就需要遍歷到一定深度的樹才會檢索到數(shù)據(jù)。每一次檢索一個節(jié)點就是要讀一個全新的數(shù)據(jù)葉，就是一次的IO磁盤讀；那么這樣檢索上就需要很多次IO，效率很有限，因此引入了B+樹：

B+樹呢，每一個節(jié)點不存儲數(shù)據(jù)，數(shù)據(jù)都存儲在葉子節(jié)點上，而且葉子節(jié)點是一個雙向的鏈表進行每一個葉子塊鏈接。這樣每一個節(jié)點數(shù)據(jù)塊上可以存儲的節(jié)點?分支就會多達幾十，那么樹的深度實現(xiàn)大幅度的縮小，遍歷起來也非?？?。

對于檢索引擎，一方面我們肯定把所有的資源信息完整存儲，然后根據(jù)資源提取所有的“詞項”信息，然后搜索引擎會把所有的出現(xiàn)的詞項進行存儲，詞項數(shù)據(jù)多達千億級別，詞項提出越多，搜索引擎檢索準確率也就越高。

?這是基本的詞項存儲列表，詞項在存儲的時候，是根據(jù)id進行k-v Map形式存儲，而且存儲也是分布式的，根據(jù)id hash計算處對應存儲的key,然后知道對應存儲的卡槽和卡槽所在的計算機節(jié)點（redis和kafka的類似思維的結合）。然后呢，搜索引擎還根據(jù)詞項字典建立了對應的詞項字典索引，加快map塊的遍歷。上述的詞項屬性中有一個詞項的資源列表的概念，這里是一個倒序排列的出現(xiàn)該詞項的所有的資源id的列表（int 列表），為了能很好檢索出來詞項對應的資源，對應的資源列表信息肯定需要存儲的，這是必不可少的存儲的數(shù)據(jù)單元。普通來說資源數(shù)據(jù)量在千億級以上，那么出現(xiàn)該詞項的條件假如有100萬條，那么100萬 int列表就是400萬B=4MB.千億級資源至少也有其百倍的詞項，就是100*千億=10w億，那僅僅詞項的倒排資源列表就是巨大的，甚至達到不可有效存儲的概念。所以搜索引擎中的壓縮算法是必不可少的，根據(jù)壓縮后的邏輯遍歷數(shù)據(jù)，從而使得檢索更快。搜索引擎通常使用的壓縮算法有FOR(Frame of Reference),Boaring BitMap算法，至少elasticSearch（lucence引擎）使用該壓縮算法。

1.FOR(Frame of Reference)算法，很簡單就是對數(shù)據(jù)列表取差值，存儲初始值和所有的差值即可。比如 一列數(shù)據(jù)，10000，10001，10002，10003...... 1000101;取完差值（第一個值保留原值）列表就是10000，1,1,1,1,1......;我們使用幾個bit存儲所有的差值即可（這里差值是1），之前存儲所有的數(shù)據(jù)是靠整型存儲，現(xiàn)在依靠bit存儲差值。實現(xiàn)很好的壓縮，對于該類壓縮還經(jīng)常使用到文本信息壓縮，尤其全英文的或者全中文文字壓縮，因為存儲的都是ASCII碼，范圍在一個區(qū)間內(nèi)（比較緊湊）,那記錄差值很簡單。FOR壓縮很緊湊的數(shù)據(jù)效率很好。

2.Boaring BitMap算法（位圖算法），對于非緊湊的數(shù)據(jù)序列使用FOR壓縮就不行了，如1，30，200，400，750，900，1030，... 差值和原值沒有大幅度縮小，所以使用BM算法。一個bit列 1000100001...每一個位就是一個bit,每一個位對應的位置號就是1，2，3，4，5，6....;那么在對應的位置上的bit要是1就代表有該序號的數(shù)值存在。.........00101010..... 假如這是一列數(shù)前面有10000bit位省略了，那么第一個位置代表一萬零一，這一串bit代表就是存儲了1萬零三，1萬零五，1萬零七三個數(shù)據(jù)，所以可以見的一串bit的位置是記錄的數(shù)據(jù)大小，所以存儲的數(shù)據(jù)列一定是不可以重復的，不重復的數(shù)據(jù)這樣記錄存儲可以極大的壓縮，要是資源id在幾萬幾十萬區(qū)間內(nèi)或者上億區(qū)間內(nèi)，那么這樣就是1百bit存儲一百個大小一億以上的數(shù)據(jù)（大小：4B*100）數(shù)據(jù)，同時我們記錄設置初始位置記為1億（就是bit列第一位置就是1億）100bit=12.5B存儲了400B，實現(xiàn)了幾百倍上千倍的壓縮。

對于關鍵詞（Term）字典結構的存儲，采用復用的思想；就是關鍵詞都是由多個字符組成的，（中文是雙字節(jié)的字符）那么在整個字典結構保存的時候，采用保存一個個的字符，字符之間通過有向的索引來進行串聯(lián)起來。這就是前綴樹結構，Trie-樹結構（如下圖所示，數(shù)字標記的圓就是一個字符節(jié)點）。

那為什么采用這個復用的思想呢？直接通過散列映射k-v,hashMap結構把所有的關鍵詞都存儲起來，遍歷也十分迅速，為什么采用這種復用的結構呢？一般搜索服務里面包含幾十億上百億的資源，然后后臺的服務會將這些資源文件中的文本進行解析，提取其中的關鍵詞（或者關鍵句），一般一個資源文件中包含的關鍵詞有幾十到幾百，考慮到關鍵詞的重復，那么所有資源包含的關鍵詞?也有百億甚至更大的數(shù)量級別。那么將這些關鍵詞（關鍵句）存儲起來將是非常大的空間，大致計算下，加入平均每一個關鍵詞是8個字符，那么百億關鍵詞就是100GB的大小的字典結構（這還是很保守的估算）。如果通過字符共用+有向拼接的思想，實現(xiàn)這個結構千倍、萬倍的壓縮，那么直接可以將這個字典結構放在內(nèi)存中，那么就不需要每次檢索去IO文件，性能表現(xiàn)也完全不一樣。

為了實現(xiàn)前綴復用樹（字典）結構能根據(jù)有向鏈接輸出想要查詢的Term（關鍵詞），需要標記具體節(jié)點的狀態(tài)，例如是不是某一個要查詢的Term最后一個字符，某一個節(jié)點有幾個輸出的子節(jié)點、子結點個數(shù)、是否是最后的子節(jié)點（子節(jié)點的個數(shù)記為某一個節(jié)點的出度，有些文章把輸出子節(jié)點直接叫成出度，這純屬概念混淆）等。既然節(jié)點有狀態(tài)，且通過有向鏈接，那么就是有限狀態(tài)機的概念（Finit state Machine? FSM）。如下圖：

由此可見有限有序狀態(tài)機其實是一個圖結構，只是每一個節(jié)點有標記狀態(tài)的數(shù)據(jù)。那么存儲Term(關鍵詞)字典結構肯定也是一個有向圖結構，而且還是節(jié)點狀態(tài)標記的圖結構。只是每一次節(jié)點存儲的是字符和節(jié)點狀態(tài)等信息，而且Term存儲結構還加入了起始點和終止節(jié)點，目的就是在遍歷的時候單向有限，而且要求盡量去復用節(jié)點，這就是FSA(Finit state Accepter 有限狀態(tài)接收器)的概念。如下圖：

上圖中0是起始節(jié)點，7是終止節(jié)點?；而且在有向路線上盡量復用節(jié)點。那么如何實現(xiàn)復用呢？這是最為核心的算法，也是關鍵詞存儲和檢索的核心算法。很多博客上或者視頻講解中只是提到FSA具備線路輸出值（或者權重）特征，有點類似哈夫曼樹（也叫霍夫曼），盡量使得所有線路的權重值求和結果最小，而且一般要求FSA中相同的始末節(jié)點線路輸出值是一致的（heap和area中a->e的線路輸出值一致）。那么在所有字典節(jié)點確認好了之后，來檢查線路輸出值，相同的要進行合并，這樣就容易達到公用線路的算法。如下圖：

線路遍歷之后，合并線路：

在FSA的建立之后，我們還需要對term存儲的字典結構中存儲每一個term的value,term字符串就是key,還需要像hashmap那樣存儲對應的value.所以我們又創(chuàng)造了每一個term結束字符節(jié)點的時候輸出一個value,記為outputValue.這就是FST finit state transsioner.對于一系列的term,需要構造FST結構存儲，事先就確定了每一個term的value，構建FST數(shù)據(jù)結構的一系列算法的集合?叫做FST構造器。構造器的構造過程如下：

所有的關鍵詞term字符節(jié)點都被放置在一個叫做frontier的列表里面，去構建FST的時候，首先創(chuàng)造uncomplied[]?存儲即將構建的term的字符，然后創(chuàng)建一個初始節(jié)點entry,然后?依次從uncomplied[]（也叫做current[]）中獲取每一個term的起始節(jié)點，然后按照每一個term將其他的節(jié)點依次掛進去，并記為pendingEntry。如果一個節(jié)點掛載的pendingEntry較多的時候，就會合并在一起形成pendingblock,并將該隊列中最后一個entry的線路值作為pendingblock的線路值。如果形成的pendingblock持續(xù)增長，長度達到一個條件，就會轉換成兩個floorblock掛載在該block下面，形成層級結構，每一個floorblock的第一個entry節(jié)點的線路值作為floorblock的線路輸出值。這樣就形成了組織架構，這樣也是為了方便將term的字典樹結構搭建起來，然后所有的term節(jié)點掛載完成之后，然后根據(jù)term最后的節(jié)點來鏈接到終止節(jié)點，接著根據(jù)終止節(jié)點來倒著掃描末尾節(jié)點的狀態(tài)和輸出線路值。逐個的將floorblock和pendingblock中的entry逐個的確定和隔離開來，形成確定的節(jié)點參數(shù)信息和線路值。

Arc：描述FST構建的重要類型，其中我們要著重理解的包括label、output、target和flags四個屬性，其他屬性我這里都已經(jīng)做了詳細的中文注釋，這里我們來把剛才說的四個屬性重點講解一下。

label：描述當前輸入詞項中的一個字符，F(xiàn)ST最終存儲的是label對應字符的ASCLL的二進制。

output：存儲Arc對象的附加值或者叫做輸出值，output和finalOutput都屬于output。

target：如果當前的祖父不是輸入值的最后一個字符，target會存儲當前字符的下一個字符在current數(shù)組中的flag值在current數(shù)組中的index即索引值。

flags：通用最小化算法要求任何對數(shù)據(jù)的壓縮都要可以逆向運算，即數(shù)據(jù)可編碼解碼，因此在對于FST進行壓縮的時候，flags的作用是以最小的代價標記若干個狀態(tài)值，這里采用了一種位移算法，以實現(xiàn)其通用最小化的目的。這里label和output都很容易理解，但是target和flags相對難以理解。target的含義我們在FST的寫入過程中給大家做詳細介紹，但是這flags的含義我們有必要在這里展開來詳細的講解一下。

lastFrozenNode：當節(jié)點從frontier[]數(shù)組中摘下來的時候，節(jié)點和它包含的Arcs信息會被寫入到current[]數(shù)組中，lastFrozenNode會記錄當前被處理的節(jié)點的第一個Arc在current數(shù)組中的起始坐標，即flag的坐標。如果當前節(jié)點是終止節(jié)點，因為終止節(jié)點沒有出度Arc，因此lastFrozenNode會輸出-1。當lastFrozenNode的值和當前處理的Arc指向的target node在current數(shù)組的起始坐標不相同并且當前處理的Arc的target node不是Stop node（因為沒有出度Arc）的時候，也就意味著最終構建的FST對象存儲的current[]數(shù)組在讀取的時候，當前Arc對應的label在數(shù)組中的下一個Arc不是當前term的下一個label，就需要記錄當前Arc的下一個Arc在current數(shù)組中的坐標，此時flag就不會標記BIT_TARGET_NEXT值。

把該末尾節(jié)點輸出線路值記為一個合理的數(shù)值out1,該term對應的數(shù)值是value,往前所有的線路輸出值總和為value-out1;如果out1值被之前掃描到的term線路已經(jīng)賦值了，那么：1.如果out1<=value;則其向前線路和為value-out1; 2.如果out1>value;則令out1=value;記temp=out1-value;temp的數(shù)值可能需要被其他term向前的其他線路作為補償值，且該term向前的線路暫不輸出值（不輸出值標記為0）。這樣倒向逐個確定節(jié)點的線路輸出值，然后最后相同的線路進行掃描合并，確定每一個節(jié)點的出度和狀態(tài)參數(shù)信息，從而達到固化的目的。然后再倒序掃描固化的節(jié)點，執(zhí)行freezeTail加固話的節(jié)點信息存儲到compiled array數(shù)組中，依次從數(shù)組的最前面開始放置。這樣放置完成之后，發(fā)現(xiàn)數(shù)組最后的位置存儲的term字典樹的開始位置節(jié)點信息，類似一個棧結構；這也是為什么叫做倒排索引的原因。

flags在FST結構讀取的時候起著關鍵作用，flags是有幾種有限的固定值的。

flags是這幾種狀態(tài)值的和，1，2，4，8，16，32者六種數(shù)值的幾種組合，所以我們可以很輕松從flag的數(shù)值推斷出來是哪幾種狀態(tài)值的累加。根據(jù)flag,我們在讀取的時候很容易知道該節(jié)點在FST中的狀態(tài)和位置。?

按照網(wǎng)上給的一個例子，圖中紅框內(nèi)是term和對應的value數(shù)值，也就是k-v列表信息：

然后圖中左邊部分是要計算每一個節(jié)點的flags,和右邊確定的FST節(jié)點的拓撲結構信息，可以動手大家畫一下，很容易就可以畫出來的。下面是輸出的最終FST數(shù)組結構：

文章來源地址http://www.zghlxwxcb.cn/news/detail-402964.html

到了這里，關于搜索引擎（大數(shù)據(jù)檢索）論述[elasticsearch原理相關]的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！