一種新型高效全文檢索引擎的設計

關鍵詞：倒排索引;全文檢索;檢索引擎;模糊查詢;字典樹

0 引言（Introduction）

全文檢索是指根據字符串在大量文檔中找到與該字符串匹配的文檔集合，常規文檔管理手段基于文檔遍歷，查詢效率極低，因此全文檢索引擎研究對構建高效、智能的信息檢索系統，提高信息處理能力具有重要的意義。

文檔管理系統通常使用關系型數據庫，模糊查詢使用“like”配合“%”關鍵字，索引類型為“B-樹（Oracle）”“B+樹（MySQL）”等[1]，前者會進行大量磁盤I/O [2]，后者也會進行4次磁盤I/O，并且高并發時會占用大量內存[3]。MySQL內置了N-gram全文檢索插件，用于文本查錯、校對等[4]，但對中文支持較差。目前，主流的全文檢索技術如Lucene、ElasticSearch會先構造詞集，遍歷文檔數據后建立“詞-文檔”數據，該數據稱為“倒排索引”[5-6]，倒排索引常存儲在磁盤中，讀取過程會產生大量磁盤I/O。聶玉峰等[7]將倒排索引存儲介質換成固態硬盤，提高了時間效率，但成本較高。袁琴琴等[8]使用Oracle組件搭建全文檢索系統，但Oracle是收費數據庫，并且搭配組件使用會對服務器運行造成負擔。葛云生等[9]基于Zookeeper分布式資源管理引擎與Lucene搜索引擎搭建分布式檢索系統，由于該系統需要部署集群，所以成本較高。

本文將介紹一種使用網絡小說文本作為處理對象，基于開源框架和技術搭建的高效全文檢索引擎系統的設計與實現，在保持較低內存消耗的情況下實現對文本的高效檢索。

1 問題模型（Problem model）

1.1 傳統文檔數據存儲方式

對于一般的軟件系統，常將文檔本身存儲在磁盤中，將文檔的路徑以及關聯信息存儲到關系型數據庫中，在數據量較小或不需要提供全文檢索的情況下，這種方式只需存儲必要的信息，節省了磁盤空間。但是，當需使用文檔的一部分搜索出文檔信息時，需要遍歷全部的文檔以及每篇文檔中存儲的所有信息，這種搜索算法的時間復雜度為O（MN ），其中M 表示文件總數，N 表示每個文件的平均字符數，通常無法滿足用戶性能需求。傳統索引的存儲結果如表1所示，傳統存儲方式查詢流程如圖1所示。

1.2 系統改進模型

系統會對每篇文章分詞，建立詞-文檔在數據庫中的主鍵集合形式的倒排索引，通過倒排索引搜索文檔的效率極高，為節省提取倒排索引所需的時間，系統將倒排索引數據存放在內存中，最終將主鍵集合作為查詢條件從數據庫中提取數據，當數據庫索引樹為“B+樹”時，查詢時間復雜度為M ×log（N ） ，其中，M 為文檔主鍵個數，N 為數據庫索引樹（B+樹）中頁結點的元素數量[10]。倒排索引的存儲方式如表2所示。系統改進后的查詢流程如圖2所示。

2 系統和算法設計（System and algorithm design）

2.1 總體設計

系統分為9個后端模塊和2個前端模塊，系統結構如圖3所示。

其中，爬蟲模塊、倒排索引模塊必須在服務運行前運行一次。本系統使用的文檔數據、用戶、管理員信息存儲在MySQL中，索引信息存儲在MongoDB中，緩存信息存儲在Redis中，數據庫表及其關系如圖4所示。

2.2 核心功能設計

2.2.1 構建倒排索引與文檔詞頻表

遍歷文檔表，依次獲取文檔的file_code（主鍵）與文本內容，使用jieba庫的lcut_for_search（）方法對文本內容進行分詞，得到列表形式的詞集，記為word_list，使用collections庫中Counter（）方法統計word_list中的元素出現次數，即詞頻，生成字典，記為word_dict，刪除出現頻率低于5的詞，借助哈工大停用詞表[11]，刪除停用詞。將word_dict轉化成json格式存儲到MySQL中，在MongoDB中建立集合，表結構參見圖4中的倒排索引表。遍歷上述word_dict的key，即單詞，若倒排索引集合存在該詞，則將文檔主鍵插入file_code_list，若集合中不存在該詞，則新建以key值為index_name，file_code_list為空列表的文檔，構建倒排索引和詞頻表流程如圖5所示。項目運行時，高效搜索模塊使用字典對象將倒排索引加載到內存中，詞頻統計模塊使用pandas.DataFrame對象將文檔詞頻數據加載到內存中。

2.2.2 構建字典樹內存數據庫

字典樹又稱前綴樹、Trie樹，是一種高效字符串查詢樹，相同的前綴字符共享同一節點，在節省大量存儲空間的同時，提高查詢效率[12]，如存儲詞集[沈陽，沈陽人，沈老師，沈陽房地產，沈陽房屋]，字典樹存儲結構如圖6所示。項目使用字典樹完成文檔名稱和索引詞的搜索提示。項目使用字典類型嵌套實現字典樹，字符串中前一字符作為后一字符的key，并將其封裝進類中，提供插入、刪除、查詢方法。

2.2.3 搜索功能設計

搜索為項目的核心功能，即通過用戶輸入的信息，查詢出匹配的文檔集合。用戶在前端的搜索框中輸入字符串，該字符串不一定是完整的索引詞或文檔名稱，此時前端會調用后端字典樹模塊的接口，輸出以該字符串為前綴的文檔名稱和索引詞集合（圖7），當用戶點擊目標文檔名稱時，調用后端Redis模塊的接口，獲取該文檔的主鍵，在MySQL數據庫中查詢該文檔的信息輸出到前端頁面;當用戶點擊目標索引詞時，調用后端高效搜索模塊的接口，獲取包含該詞的文檔的主鍵集合，構造SQL語句，將主鍵集合作為where條件從MySQL數據庫中查詢數據并輸出到前端;當用戶點擊回車鍵時，判定該字符串為句子，調用后端高效搜索模塊的接口，對該句子進行分詞生成詞集，對該詞集的每個詞對應的文檔主鍵集合進行合并、去重，生成新的主鍵集合，后續操作依次按照搜索詞的方式進行。搜索功能流程如圖8所示。

2.2.4 排序功能設計

當系統的文本量足夠大時，同一query通常會查詢出大量的文檔，用戶很難從眾多的文檔中篩選出匹配度最高的文檔，因此需要一種幫助用戶篩選高匹配度文檔的方法，系統使用TF-IDF（Term Frequency-Inverse Document Frequency）算法[13]計算query與文檔的相關度，依照相關度對文檔排序并逆序輸出。用戶點擊搜索結構頁面的排序按鈕，前端將用戶輸入的query和所有查詢結果的文檔主鍵提交給高效搜索模塊，高效搜索模塊不斷地向詞頻統計模塊發送請求，依次得到每篇文檔的總詞數，記為word_count，每篇文檔中query詞出現次數占該篇文檔中所有詞數的比重，記為TF，隨后計算出包含query詞的文檔數占總文檔數的比重，記為IDF，生成哈希表（字典）數據，其中key為文檔主鍵，value為該篇文檔按照TF 與IDF 的乘積逆序排序后的位置，將其以json格式返回給前端。前端收到json數據后，將其解析為JavaScript中對象類型，依照該對象對文檔信息進行排序。使用這樣的排序算法，前端只需要向后端返回文檔主鍵的集合，不需要將文檔信息返回，減輕了系統的壓力。排序算法流程如圖9所示。

3 實驗及結果分析（Experiment and results analysis）

為了分析系統效率，梯度增加測試的詞集長度，并與主流的同類產品ElasticSearch（7.17.4版本）對比，開展系統壓力測試和性能測試。

開發環境：PyCharm 2021，WebStorm 2021，Python 3，Vue 3，Flask 1.1.2。

運行環境：Inter i7-7700HQ CPU，RAM 16.0 GB，Windows10 x64。

3.1 系統性能測試

使用爬蟲模塊抓取“愛九九小說網”的17 919篇文檔，將其作為測試文檔，將測試文檔信息存儲到MySQL中，從倒排索引的key中隨機提取10 000個索引詞，依次截取前10、100、1 000、5 000、10 000個詞作為輸入數據，詞集的形式如[‘風有’，‘回母’，‘合個’，‘小梨窩’，‘那臉’，……]，向系統輸入詞集，返回包含該詞集中任意一詞的文檔的名稱與主鍵。本文設計的系統性能測試結果如表3所示。從表3可以看出，測試數據量與總耗時成正比，符合對數函數曲線，平均每次搜索耗時隨著數據量的增長而降低，這是因為一個索引詞往往對應多篇文檔，系統在內存中已經對重復的文檔進行去重，保證在數據庫中不會有重復的磁盤I/O操作。

3.2 與ElasticSearch的對比測試

在ElasticSearch 中使用同樣的詞集進行測試，ElasticSearch性能測試如表4所示。對比表3和表4可以看到，ElasticSearch的各項數據之間的關系與本文設計的系統相同，但效率遠遠低于本系統，隨著測試數據量的變化，即數據量從10～10 000增加時，本文系統效率優勢相對ElasticSearch逐漸降低，呈現反比例變化關系。但優勢仍較明顯，兩者效率差為80～1 200倍，原因主要為ElasticSearch是基于磁盤的存儲軟件且索引結構為字典樹，設字符串的長度為n，單次查詢需要n 次磁盤I/O，當數據量過大時，需要的磁盤I/O次數也會非常多[14]，而本文設計的系統將索引文件提取到內存中，只有向數據庫中提取數據時才會進行磁盤I/O，在內存中的數據以哈希表形式存儲，時間復雜度為O（1），選用MySQL數據庫，其索引結構為B+樹，設一頁節點的長度為n，改善查詢語句以充分發揮MySQL性能，查找時間復雜度為O（log（n）） [15]。

4 結論（Conclusion）

本文設計了一種高效的全文檢索引擎系統，該系統的核心設計思想為對文本建立倒排索引，將索引數據提取到內存中，以少部分內存空間為代價大大降低了磁盤I/O量，系統的搜索效率提升十分可觀，單次搜索的平均時間遠小于ElasticSearch，在17 919條文檔的情況下，內存占用也不超過2.5 GB，適合大型企業作為對海量文檔的搜索引擎，并且系統內置了對文檔的增、刪、改、查功能，因此也適合個人用戶作為對文檔的管理系統。由于系統依賴的模塊較多且沒有做分布式的優化，因此后期工作將圍繞減少模塊依賴，增強系統的可移植性，去中心化以便分布式搭建，減少重復數據以減輕內存占用等方面做進一步優化。