李高鵬 艾山·吾買爾 鄭炅 王路路

摘? 要： 隨著信息化的發(fā)展，互聯(lián)網(wǎng)上出現(xiàn)了越來越多的文檔信息，如何根據(jù)用戶的需要從海量的文檔中快速獲取相關(guān)信息成為了研究的熱點。采用Python編程語言、Django Web應(yīng)用框架、UWSGI Web服務(wù)器、Nignx代理服務(wù)器，基于TextRank關(guān)鍵詞提取算法、倒排索引結(jié)構(gòu)、Jaccard相似度計算以及MySQL數(shù)據(jù)庫技術(shù)構(gòu)建了漢英文本信息檢索系統(tǒng)。該系統(tǒng)包含文本注冊、文本檢索和文本注銷三個模塊，可實現(xiàn)千萬量級文本數(shù)量上的快速注冊和快速檢索功能，為構(gòu)建輿情分析系統(tǒng)提供服務(wù)，并可根據(jù)人們特定的需求，擴展文本檢索服務(wù)。

關(guān)鍵詞： 信息檢索; 算法介紹; 倒排索引; 檢索系統(tǒng)構(gòu)建; 快速注冊; 快速檢索

中圖分類號： TN911.2?34; TP391? ? ? ? ? ? ? ? ? ? ?文獻標識碼： A? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2019）16?0062?05

0? 引? 言

隨著信息技術(shù)的飛速發(fā)展和我國人民生活水平的提高，互聯(lián)網(wǎng)已經(jīng)成為人們?nèi)粘Ｉ顚W(xué)習(xí)的一部分。我國已經(jīng)進入了知識爆炸的時代，互聯(lián)網(wǎng)上的漢語、英語相關(guān)的文檔數(shù)量不斷增加，并且未來還會繼續(xù)增多。如何幫助用戶快速有效地從海量的文本數(shù)據(jù)中找到需要的文本信息，成為學(xué)者們研究的重要課題。文本檢索是指根據(jù)用戶輸入的信息從大量的文本集合中查找出相關(guān)文本的一種技術(shù)。文本檢索作為信息檢索[1]的一種，常用于搜索引擎、數(shù)字圖書館、輿情系統(tǒng)等領(lǐng)域。文本檢索已經(jīng)成為信息處理領(lǐng)域中不可獲取的工具。常用的文本檢索模型[2]可以分為三類：基于集合論的檢索模型、基于代數(shù)的檢索模型和基于概率論的檢索模型。其主要包括布爾模型、向量空間模型、概率模型、引用分析模型等。

文本檢索[3]是當代網(wǎng)絡(luò)技術(shù)中的主流技術(shù)之一。文本檢索[4]的過程一般分為兩個步驟：索引的建立和索引的搜索，索引的建立是指對結(jié)構(gòu)化文本和非結(jié)構(gòu)化文本（一般將非結(jié)構(gòu)化文本轉(zhuǎn)換為結(jié)構(gòu)化文本）進行特征抽取，建立索引的過程;索引的搜索是指將用戶的請求作為檢索對象，根據(jù)請求文本的特征，搜索數(shù)據(jù)庫，返回結(jié)果的過程。雖然Google、百度等公司的搜索技術(shù)[5]已經(jīng)相當成熟，但針對不同用戶特定的需求，這些搜索引擎并不能很好的滿足，也不方便用戶根據(jù)需要進行擴展。

基于以上現(xiàn)象和問題，本文基于TextRank關(guān)鍵詞提取算法、倒排索引結(jié)構(gòu)、Jaccard相似度計算方法及MySQL數(shù)據(jù)庫技術(shù)等構(gòu)建了漢英文本信息檢索系統(tǒng)，實現(xiàn)了千萬量級文本下的快速檢索，并且用戶可根據(jù)不同需求進行文本的注冊、注銷，滿足用戶特點的需求，實現(xiàn)個性化搜索，幫助用戶從海量文本數(shù)據(jù)完成檢索任務(wù)，為輿情分析系統(tǒng)的構(gòu)建提供服務(wù)，另外本文構(gòu)建的系統(tǒng)同樣適用于其他語言。

1? 算法介紹

1.1? TextRank算法

TextRank[6]算法來源于Google的網(wǎng)頁排名算法PageRank[7]，是一種基于圖的排序，可用于關(guān)鍵詞提取、短語提取和摘要提取。TextRank算法在進行關(guān)鍵詞提取時，首先對于文本分句，過濾掉停用詞，去除標點亂碼等無意義的字符，再結(jié)合詞性標注方法篩選出名詞、動詞、形容詞等重要詞匯作為關(guān)鍵詞候選詞匯。利用篩選出的詞匯構(gòu)建關(guān)鍵詞圖，每個單詞作為圖中的一個節(jié)點，把具有共現(xiàn)關(guān)系的詞進行連接，迭代確定各個節(jié)點的權(quán)重，直到權(quán)重收斂為止，之后對各個節(jié)點進行排序，根據(jù)需要輸出最重要的前n個詞作為提取出的文本的關(guān)鍵詞。TextRank算法中可將文本看作是一個無向加權(quán)圖[G=（V，E）]，[V]表示關(guān)鍵詞的集合，[E]表示邊的集合，TextRank的核心公式為：

[WS（Vi）=（1-d）+d·Vj∈In（Vi）ωjiVk∈Out（Vj）ωjkWS（Vj）]? （1）

式中：[WS（Vi）] 表示第[Vi]個關(guān)鍵詞的TextRank值，該公式表示TextRank中單詞[Vi]的權(quán)重值由[Vi] 之前的各個關(guān)鍵詞[Vj]組成;[d]表示阻尼系數(shù)，一般設(shè)置為0.85;[ωji]和[ωjk]表示兩個關(guān)鍵詞節(jié)點之間的邊的權(quán)重;[In（Vi）]表示指向關(guān)鍵詞[Vi]的關(guān)鍵詞的集合;[Out（Vj）]表示關(guān)鍵詞[Vj]指向其他關(guān)鍵詞的集合。

1.2? 倒排索引算法

搜索引擎是根據(jù)用戶輸入的關(guān)鍵詞信息，從文檔集合中找出包含這些關(guān)鍵詞的文檔。如何快速準確地找出文檔呢？一般選擇采用單詞文檔矩陣結(jié)構(gòu)表示這些文檔。在搜索引擎中，每個文檔都有其對應(yīng)的文檔ID，可以把文檔看作是一些關(guān)鍵詞組成的集合，根據(jù)單詞文檔模型，可以知道哪些關(guān)鍵詞在哪些文檔中，哪些文檔包含了哪些關(guān)鍵詞。索引結(jié)構(gòu)作為單詞文檔矩陣結(jié)構(gòu)的一種，在用來表示單詞與文檔之間的對應(yīng)關(guān)系時，把文檔ID與該文檔提取出的關(guān)鍵詞相對應(yīng)的結(jié)構(gòu)稱為正向索引結(jié)構(gòu)，如表1所示。

在使用正向索引結(jié)構(gòu)進行知識檢索時，只能從頭逐一查詢，文檔數(shù)量較多時，會導(dǎo)致資源開銷大、查詢效率低等問題。為了能快速根據(jù)關(guān)鍵詞查詢出對應(yīng)的文本，可將正向索引結(jié)構(gòu)重新構(gòu)建成每個關(guān)鍵詞對應(yīng)包含該關(guān)鍵詞文檔ID集合的結(jié)構(gòu)。這種結(jié)構(gòu)就是倒排索引[8]結(jié)構(gòu)，如表2所示。

在進行文本注冊時，本文使用倒排索引結(jié)構(gòu)把通過TextRank算法提取出的關(guān)鍵詞特征與包含該關(guān)鍵詞的文檔進行關(guān)聯(lián)，構(gòu)建索引表并存入到MySQL數(shù)據(jù)庫中。在進行文本檢索時，通過關(guān)鍵詞信息檢索出包含這些關(guān)鍵詞的文本，快速過濾掉不相關(guān)文本，提高檢索效率。在進行文本注銷時，不僅刪除掉數(shù)據(jù)庫中的不相關(guān)文本，還根據(jù)注銷文本的關(guān)鍵詞重新修正了數(shù)據(jù)庫中存儲的倒排索引表，保證了檢索結(jié)果的實時性、準確性。

1.3? 杰卡德相似系數(shù)

Jaccard相似度通常用來計算兩個集合之間的相似程度[9]。Jaccard相似度計算公式為：[J（A，B）=A?BA?B? ? ? ? ? ? ? ?=A?BA+B-A?B] （2）

式中：[A] 和[B] 表示兩個集合;集合[A] 和集合[B] 的交集與并集的比值表示Jaccard相似度，比值越大表示兩個集合越相似。在漢英文本信息檢索系統(tǒng)中，本文用Jaccard相似度計算檢索出的文本與查找文本的相似度。通過對相似度進行排序，返回相似度從高到低的前n個結(jié)果。

1.4? MD5消息摘要算法

MD5[10]（Message?Digest Algorithm 5）消息摘要算法屬于Hash算法的一種，它的作用是無論輸入多長的字符串，都會通過其特定的字符串變換算法將輸入的字符串轉(zhuǎn)換為特定長度的大整數(shù)，形成唯一的MD5消息摘要，當輸入的內(nèi)容發(fā)生任何形式的變化時都會改變這一消息摘要。MD5算法廣泛用于各種加密、解密技術(shù)。本文將爬取的網(wǎng)頁url地址和關(guān)鍵詞轉(zhuǎn)換為32位的MD5編碼，減少了存儲空間，加快了檢索速度。

2? 漢英雙語文本信息檢索系統(tǒng)的設(shè)計與實現(xiàn)

2.1? 系統(tǒng)功能結(jié)構(gòu)圖

文本信息檢索系統(tǒng)由文本注冊、文本檢索、文本注銷三個模塊構(gòu)成。文本注冊模塊包含關(guān)鍵詞提取模塊，正向索引和倒排索引的構(gòu)建模塊，根據(jù)關(guān)鍵詞與文檔之間的關(guān)系，構(gòu)建正向索引和倒排索引結(jié)構(gòu)，并將構(gòu)建好的索引結(jié)構(gòu)存入到數(shù)據(jù)庫的索引表中，實現(xiàn)索引庫的構(gòu)建。文本檢索模塊包括關(guān)鍵詞提取模塊、檢索模塊和相似度計算模塊，通過關(guān)鍵詞信息從索引庫中找出包含這些關(guān)鍵詞的文本，并計算檢索到的文本與查找到的相關(guān)文本之間的相似程度，排序輸出最終結(jié)果。文本注銷模塊功能與文本注冊模塊相反，該模塊包括關(guān)鍵詞提取模塊和索引重建模塊，根據(jù)文本的ID找到需要注銷的文本，刪除正向索引表中的信息，根據(jù)提取出的文本的關(guān)鍵詞，找到并修改索引庫中對應(yīng)的倒排索引表。文本信息檢索系統(tǒng)的功能結(jié)構(gòu)圖如圖1所示。

2.1.1? 文本注冊模塊

本文首先對爬取到的特定Web網(wǎng)頁，通過正則匹配法，提取出網(wǎng)頁內(nèi)的文本信息，之后進行語種判別，根據(jù)判別結(jié)果分別將請求提交到對應(yīng)的漢語注冊接口和英文注冊接口。Web網(wǎng)頁的url作為對應(yīng)文檔的rowkey，并使用MD5編碼得到rowkey對應(yīng)的rowkeyCode，將網(wǎng)頁內(nèi)抽取的文本信息作為context存入數(shù)據(jù)庫中。在文本注冊模塊將與Web網(wǎng)頁的url網(wǎng)址對應(yīng)的rowkeycode存入數(shù)據(jù)庫中，保證數(shù)據(jù)庫中文檔的唯一性，避免存入重復(fù)文檔。為了提高檢索的速度，壓縮存儲空間，本文采用TextRank算法對context中的內(nèi)容進行關(guān)鍵詞提取。根據(jù)文檔和關(guān)鍵詞之間的關(guān)聯(lián)建立正向索引表和倒排索引表，存入到索引庫中，成功注冊后返回消息。文本檢索模塊流程圖如圖2所示。

圖2? 文本檢索模塊流程圖

Fig. 2? Flow chart of text retrieval module

2.1.2? 文本檢索模塊

文本檢索模塊在獲取到請求之后，先進行參數(shù)校驗，判斷參數(shù)是否合法，如果不合法，直接退出，并返回錯誤類型;如果合法，則對待檢索的文本進行關(guān)鍵詞提取。根據(jù)提取的關(guān)鍵詞在索引庫找出包含這些關(guān)鍵詞的文本，拿到相應(yīng)的rowkey，再把正向索引表中rowkey對應(yīng)的文本的特征、權(quán)重與待檢索文本的特征進行Jaccard加權(quán)計算，得到文本之間的相關(guān)性，并排序輸入前n個結(jié)果，作為最終結(jié)果返回。

2.1.3? 文本注銷模塊

文本注銷模塊在接收到注銷請求后，同樣先檢查參數(shù)是否合法，如不合法，結(jié)束并返回相應(yīng)的錯誤類型;如果合法，通過rowkey查找數(shù)據(jù)庫中是否包含此條記錄。如果數(shù)據(jù)庫中沒有此條記錄，結(jié)束程序返回相應(yīng)的錯誤類型;如果數(shù)據(jù)庫中存在該記錄，刪除正向索引表中的記錄，并修改倒排索引表中的關(guān)鍵詞對應(yīng)的文檔序列，刪除該條文檔的編號，完成這些操作后，返回注銷成功消息。

2.2? 數(shù)據(jù)庫系統(tǒng)設(shè)計

數(shù)據(jù)庫設(shè)計包括概念模型設(shè)計、邏輯模型設(shè)計和物理模型設(shè)計三個層次。在數(shù)據(jù)庫設(shè)計過程中，數(shù)據(jù)庫中的數(shù)據(jù)應(yīng)當減少冗余，避免一組數(shù)據(jù)在數(shù)據(jù)庫多個表中重復(fù)出現(xiàn)。但在實際情境中，為了加快索引，方便快速查詢，通常會違背這些數(shù)據(jù)庫的設(shè)計規(guī)范。通過增加冗余列，進行數(shù)據(jù)庫表的合并和拆分，減少表之間的連接，減少數(shù)據(jù)庫的計算壓力，以達到提高性能的目的。以中文為例的文本檢索信息的物理數(shù)據(jù)模型如圖3所示。

圖3所示以漢語文本信息檢索系統(tǒng)為例，該系統(tǒng)中一共設(shè)計了8張表，分別為文本注冊表、文本內(nèi)容信息存儲表、文本基本信息存儲表、索引信息存儲表、備用索引信息存儲表、文本注銷表、臨時索引信息表、臨時排序表。文本注冊表用來判斷該篇文本是否已經(jīng)注冊過，可以方便在文本注冊和文本注銷時查找待注冊文本和待注銷文本是否在數(shù)據(jù)庫中。文本基本信息存儲表用來存儲注冊文本的詳細信息，包括爬取時間、發(fā)布時間、文本來源等。索引信息存儲表，即倒排索引表，該表存儲的是關(guān)鍵詞與包含該關(guān)鍵詞的文本編號的對應(yīng)關(guān)系，當?shù)古疟碜兊煤艽髸r，會降低檢索速度，這時會對倒排索引表進行切分，存儲到備用索引信息存儲表中。文本注銷表用來存儲用戶傳入的需要注銷的文本，以便在后臺執(zhí)行文本注銷操作。臨時索引信息表存儲的根據(jù)關(guān)鍵詞信息檢索到的文章編號，同文本內(nèi)容信息存儲表中的rowkeycode相對應(yīng)。文本內(nèi)容信息存儲表，即正向索引表，用來存儲文本的編號rowkeycode以及從文本中提取的關(guān)鍵詞信息orginaltext，用來同用戶傳入的檢索文本進行相關(guān)性計算。計算完的結(jié)果存儲在臨時排序表中。

3? 系統(tǒng)測試

本文在構(gòu)建漢英文本信息檢索系統(tǒng)后，向檢索系統(tǒng)中注冊3 000萬條數(shù)據(jù)進行測試。實驗使用的系統(tǒng)硬件環(huán)境是CPU Intel[?] Xeon[?] CPU E5?2690 V4 @ 2.60 GHz*56 GB，512 GB內(nèi)存，2 TB硬盤。使用的軟件環(huán)境如下：操作系統(tǒng)為Centos 7.2，Pyhton 3.6，Django（1.11.3），uWSGI（2.0.15），Nginx（1.12.1），MySQL（8.0.12）數(shù)據(jù)庫。數(shù)據(jù)注冊的速度及索引構(gòu)建速度隨文本數(shù)量的變化關(guān)系如圖4所示，文本檢索的速度如表3所示。

從圖4可以看出，在索引庫的建立過程中，隨著索引內(nèi)容的增加呈現(xiàn)出非線性增長，本文注冊3 000萬條數(shù)據(jù)，注冊文本的平均長度為2 123個字符，共花費了41.76 h，基本可滿足快速構(gòu)建索引庫的要求。表3顯示的是向數(shù)據(jù)庫中注冊了3 142萬條數(shù)據(jù)后的檢索速度的測試結(jié)果，當數(shù)據(jù)量達到3 000萬條時，平均每秒可完成3～4條文本的檢索。

關(guān)于文本信息檢索系統(tǒng)的檢索質(zhì)量，本文是通過關(guān)鍵詞匹配在數(shù)據(jù)庫中查找相關(guān)文本，把匹配到的結(jié)果與用戶輸入的檢索文本進行相似度計算，并設(shè)定相似度閾值，對于大于相似度閾值的文本，根據(jù)相似度、發(fā)布時間、爬取時間等排序，按照用戶的需要輸出結(jié)果。因此，檢索結(jié)果與關(guān)鍵詞提取算法相關(guān)性較大。TextRank算法能較好地抽取文本中的關(guān)鍵詞，通過判定本系統(tǒng)的搜索結(jié)果可滿足檢索質(zhì)量的要求。

4? 結(jié)? 語

本文利用Django框架，基于TextRank關(guān)鍵詞提取算法、倒排索引結(jié)構(gòu)、Jaccard文本相似度計算方法及MySQL數(shù)據(jù)庫技術(shù)，構(gòu)建了信息檢索系統(tǒng)，實現(xiàn)了千萬量級下快速注冊、快速檢索的文本信息檢索，同時用戶可根據(jù)文本注冊和文本注銷模塊對該文本信息檢索系統(tǒng)進行擴展，滿足用戶不同的需求。雖然關(guān)鍵詞可以在一定程度上代表文本的語義，但并不能完全表示文本的語義信息，所以下一步將會研究實現(xiàn)基于語義的智能化的檢索。

注：本文通訊作者為艾山·吾買爾。

參考文獻

[1] 王勇.Web網(wǎng)絡(luò)環(huán)境下的語義檢索平臺設(shè)計與分析[J].現(xiàn)代電子技術(shù)，2016，39（16）：14?18.

WANG Yong. Design and analysis of semantic retrieval platform in web network environment [J]. Modern electronics technique， 2016， 39（16）： 14?18.

[2] 丁志均，楊青，張會兵，等.基于非結(jié)構(gòu)化文本檢索模型綜述[J].計算機應(yīng)用研究，2017，34（6）：1601?1608.

DING Zhijun， YANG Qing， ZHANG Huibing， et al. Review of unstructured text retrieval model [J]. Application research of computers， 2017， 34（6）： 1601?1608.

[3] SONG W， WANG B， WANG Q， et al. A privacy?preserved full?text retrieval algorithm over encrypted data for cloud storage applications [J]. Journal of parallel & distributed computing， 2017， 99： 14?27.

[4] SHI X J， WANG Z F. An optimized full?text retrieval system based on lucene in oracle database [C]// 2014 Enterprise Systems Conference. Shanghai： IEEE， 2014： 61?65.

[5] 楊凱.數(shù)字圖書館個性化搜索引擎的用戶建模[J].現(xiàn)代電子技術(shù)，2016，39（7）：97?102.

YANG Kai. User modeling of personalized search engine for digital library [J]. Modern electronics technique， 2016， 39（7）： 97?102.

[6] TIAN X. Extracting keywords with modified TextRank model [J]. Data analysis & knowledge discovery， 2017（2）： 28?34.

[7] CHEN G， FU K， LOZA A， et al. PageRank tracker： from ranking to tracking [J]. IEEE transactions on cybernetics， 2014， 44（6）： 882?893.

[8] 林俊鴻，姜琨，楊岳湘.倒排索引查詢處理技術(shù)[J].計算機工程與設(shè)計，2015（3）：572?575.

LIN Junhong， JIANG Kun， YANG Yuexiang. Query processing strategies based on inverted indexes [J]. Computer engineering and design， 2015（3）： 572?575.

[9] 俞婷婷，徐彭娜，江育娥，等.基于改進的Jaccard系數(shù)文檔相似度計算方法[J].計算機系統(tǒng)應(yīng)用，2017，26（12）：137?142.

YU Tingting， XU Pengna， JIANG Yue， et al. Text similarity method based on the improved Jaccard coefficient [J]. Computer systems & applications， 2017， 26（12）： 137?142.

[10] 李夏夢，潘廣貞.基于消息摘要算法第五版和IDEA的混合加密算法[J].科學(xué)技術(shù)與工程，2017（9）：233?238.

LI Xiameng， PAN Guangzhen. Message?digest algorithm 5?IDEA based hybrid encryption algorithm [J]. Science technology and engineering， 2017（9）： 233?238.