一種高效的文字檢索系統(tǒng)

王浩鵬

在互聯網中，文字檢索是被廣泛需要的功能。本文采用倒排索引和多級緩存技術，構建一個文字檢索系統(tǒng)。重點在于高效性和經濟性。實現了根據輸入文字進行文檔檢索的功能。

【關鍵詞】檢索；倒排；緩存

1 引言

隨著互聯網的發(fā)展，用戶在不同的需求場景中，對信息檢索的需求也逐漸多樣化和個性化。當前在信息檢索方面已經存在的經典系統(tǒng)，或者性能強大然而對服務器的消耗也十分巨大，又或者只需很少機器但是功能簡陋性能不足。本文設計了一種簡潔的文字檢索系統(tǒng)，旨在利用很少的機器滿足大量的檢索請求，提出既高效又經濟的文字檢索解決方案。

2 整體設計方案

系統(tǒng)分為離線和在線兩個部分。離線部分主要功能是對已有的檢索基礎數據建立索引。在線部分的主要功能是根據用戶輸入的關鍵詞對索引進行檢索。

3 離線索引建立

倒排關系的記錄方式，即倒排索引。在建立倒排關系的過程中，為了方便動態(tài)追加，在內存中采用鏈式結構；存儲到硬盤上時，為了高效讀取，采用順序存儲。我們把倒排索引數據稱之為倒排拉鏈。為了高效建立索引結構，我們主要考慮下面兩個重點：

3.1 分層建立索引

首先，以一定數目的對象為一組建索引，保證對每組對象建索引的過程能夠在內存中完成而不需要存取中間數據到硬盤；然后，將各組結果進行合并，得到最終的倒排索引數據。

3.2 注重內存的使用和硬盤數據的存取

盡量申請足夠的大內存塊，然后在整個進程周期內重復使用。為了方便對各組索引合并，每組數據輸出到硬盤時，將term表排序，索引拉鏈進行順序存儲。合并時，盡量利用輔助結構，避免大塊內存的頻繁復制。讀取索引拉鏈時，按塊讀取。

4 在線檢索

在線檢索需要處理用戶的輸入關鍵詞，然后在索引中檢索符合關鍵詞的內容。涉及到如下幾個過程：

4.1 關鍵詞的切分

在線檢索面臨的第一個問題就是處理用戶輸入（query）。這里用到一個開源的中文分詞工具——FNLP。FNLP是采用線性模型（linear model）分詞。較于對數線性模型（log-linear model）HMM/CRF所不同的是，線性模型沒有歸一化因子而直接建模Score函數。我們使用FNLP工具，將用戶的輸入query切分成多個term。比如query為『周潤發(fā)的眼鏡』，那么會被切分為三個term『周潤發(fā)』『的』『眼鏡』。

4.2 拉鏈歸并

每一個term對應一個倒排拉鏈，這個拉鏈代表著索引內與這個term相關的內容集合。那么對于多個term——即用戶query的變體——我們需要對多個term的拉鏈進行歸并。這里我們使用字典歸并的方式。字典是一個用HASH表實現的數據結構，目的是建立鍵與值之間的映射關系。鍵在這里就是拉鏈文檔id，而值是這個id出現在各個拉鏈中的次數。當id出現在每一個拉鏈中時，就可以認為這個id符合交的要求，可以加入到結果隊列中。理論上可以在O（1）的時間內找到這種映射關系。由于字典本身就是一個無序的數據結構，所以字典歸并不要求待歸并隊列必須有序。

經過拉鏈歸并之后，即可得到一個與query有關的內容拉鏈，可以經過簡單的處理之后返回給用戶展現。

4.3 多級緩存

考慮到文本內容的確定性和用戶query的重合性，尤其是如果用戶群體或者目的較為單一，query的重合概率極高。所以我們設計多級緩存以便減輕后端歸并的請求量，達到節(jié)省機器的目的。多級緩存包括內存緩存、硬盤緩存和集群緩存。

內存緩存直接使用一個map結構進行多線程的存儲共享實現緩存。硬盤緩存采用LRU策略，把磁盤空間分為大小分別為1K， 2K， 4K...多個塊的鏈表來管理，插入緩存時盡量fit，“多余”的塊重新插入。

集群緩存系統(tǒng)采用開源的memcache系統(tǒng)。Memcache是一個基于內存中的hash表實現的分布式緩存系統(tǒng)。我們可以在自己的服務器上面根據需要部署。

在獲取到檢索內容之后，將用戶query作為key，內容拉鏈進行protobuf打包，作為value，存放到內存map表或者硬盤或者memcache中。用protobuf打包目的是節(jié)省緩存的內存和傳輸帶寬。具體存放到哪一級的緩存中，視該query的頻次而定：頻次越高的query，越是向內存中轉移；頻次越低的query，越趨向于存放到集群緩存中。

在收到用戶請求query之后，系統(tǒng)會首先去請求各級緩存，查看緩存中是否存有該query的內容拉鏈，如果有，那么終止對下級緩存的請求并直接獲取并提供給用戶。如果各級緩存都沒有，則進行拉鏈歸并。

5 結論

本文設計了一個簡潔高效經濟的文字檢索系統(tǒng)。用nginx作為web服務器的話，可以支持很高的并發(fā)。同時在線模塊運用緩存系統(tǒng)和字典歸并，能快速處理用戶請求。而離線系統(tǒng)建立的倒排索引，進一步從組織方式上對檢索過程進行了優(yōu)化。

有別于一般的產品驅動的系統(tǒng)設計，本系統(tǒng)屬于性能需求驅動的。故相比于產品類系統(tǒng)堆砌功能，本系統(tǒng)重點在于滿足傳統(tǒng)功能的基礎上，構建一個性能非常出色的系統(tǒng)。故本文的重點在于系統(tǒng)的性能。相較于功能，本文更關注系統(tǒng)的速度、規(guī)模、可用性和擴展性。力求用較小的成本實現最出色的性能。

參考文獻

[1]郭欣著.構建高性能Web站點[M].電子工業(yè)出版社，2012.

[2]Erich Gamma，RichardHelm，RalphJohnson，JohnVlissides著.李英軍，馬曉星，蔡敏，劉建中譯.設計模式：可復用面向對象軟件的基礎[M].機械工業(yè)出版社，2000.

[3]伽瑪著.設計模式[M].機械工業(yè)出版社，2007.

[4]Stanley B.Lippman，JoséeLajoi， Barbara E. Moo著.王剛， 楊巨峰譯.C++ Primer[M].電子工業(yè)出版社，2013.

[5]丁明一著.Linux運維之道[M].電子工業(yè)出版社，2014.

[6]阿爾斯帕瓦/羅賓斯著.網站運維[M].電子工業(yè)出版社，2011.

作者單位

河北省張家口市宣化區(qū)第一中學（高三7班） 河北省張家口市 075100endprint