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

0 引言（Introduction）

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

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

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

1 問題模型（Problem model）

1.1 傳統(tǒng)文檔數(shù)據(jù)存儲方式

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

1.2 系統(tǒng)改進模型

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

2 系統(tǒng)和算法設計（System and algorithm design）

2.1 總體設計

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

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

2.2 核心功能設計

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

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

2.2.2 構建字典樹內(nèi)存數(shù)據(jù)庫

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

2.2.3 搜索功能設計

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

2.2.4 排序功能設計

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

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

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

開發(fā)環(huán)境：PyCharm 2021，WebStorm 2021，Python 3，Vue 3，F(xiàn)lask 1.1.2。

運行環(huán)境：Inter i7-7700HQ CPU，RAM 16.0 GB，Windows10 x64。

3.1 系統(tǒng)性能測試

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

3.2 與ElasticSearch的對比測試

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

4 結論（Conclusion）

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