基於MRDI的關鍵詞語義擴展密文檢索技術研究

摘要：面向雲環境中精確密文檢索需求，設計了一種多屬性、雙索引（Multi-Rationality for Dual-Indexing，MRDI）檢索方案。檢索時對查詢關鍵詞進行語義擴展，並利用語義相似度過濾擴展結果來獲得擴展查詢集，以便更好地理解用戶查詢意圖。從建索和檢索兩方面改進傳統密文檢索方案，高效檢索出包含對應關鍵詞的文件目錄信息，同時提高了查准率。實驗結果表明，該方案具有高效性和可行性。

正文內容：

0　引　言

在蓬勃發展的信息檢索領域，數據量日益增大，信息安全問題凸顯，如何對密文信息進行高效檢索是急需解決的問題。密文全文檢索，即快速而準確地從密文信息中檢索出用戶想要的信息，宗旨是「安全+高效」，涉及的主要技術有密文線性檢索、索引的維護管理、文檔和索引的安全性（加密）、密鑰管理等。密文全文檢索的高效與安全之間存在矛盾，一旦將安全機制引入，為提升檢索效率而設計的全文索引結構將大受影響，安全和性能之間的平衡成為目前的研究重點。

密文全文檢索的基本思路是：先對文本分析建立索引，通過索引對密文文本進行快速檢索。Song等人提出了一種線性檢索（Linear Scan）方案[1]，Eu-jin等人提出了基於布隆過濾器（Bloom Filter）的方法[2]。這兩種方案檢索時都需要遍歷整個索引，所需開銷將隨索引數量的增加而快速增長。Mehmet等人提出了讓用戶自己選取關鍵詞建立索引的方案[3]，能減少檢索時間開銷，但主觀性強、增加用戶負擔，在雲環境中面向雲用戶時擴展性不佳。Wang等人引入TF-IDF值到排序搜索演算法[4]，對文檔相關度進行排序，計算量小、檢索快，但它採用單關鍵詞匹配技術，只有當用戶提供的查詢詞與文檔關鍵詞完全匹配時才能檢索出文檔，使得一些包含相關語義的有效文檔被忽略，查准率不高。

本文結合矩陣索引和線性索引引入文檔屬性值，建立了一種多屬性雙索引結構。檢索時，通過本體技術擴展關鍵詞，充分挖掘用戶查詢意圖，對檢索結果進行相關度排序，返回用戶最關心（排序靠前）的文檔，使系統更加友好。

1　方案整體工作流程

本文的密文檢索結構如圖1所示。

數據持有者首先對上傳文檔進行預處理，提取並加密關鍵詞後對密文建立索引。本文索引由線性、矩陣、多屬性三種索引技術耦合後建立形成。隨後把加密文檔上傳至雲端資料庫，索引和雲端資料庫建立對應關聯信息，該信息需要實時維護和更新。檢索時，客戶端接收用戶輸入的關鍵詞，經語義擴展後得到關鍵詞擴展語義集密文，然後以密文集作為關鍵詞在已經建好的多屬性雙索引中檢索，檢索結果返回給雲伺服器。伺服器根據檢索結果從雲端資料庫中取出相應文檔，以供用戶下載。

2　多屬性雙索引建索方案

2.1　分詞技術

數據上傳者首先根據文檔生成文檔元數據，包括關鍵詞及其詞頻信息，通過分詞技術將關鍵詞從文檔中提取出來。常見的分詞種類有基於字典的、基於統計的、基於規則的分詞，演算法則分為正向最大匹配、逆向最大匹配兩大類。分詞過程包括詞語提取、停用詞（如標點和常見助詞等）和低頻詞過濾以及詞頻統計，最後得到關鍵詞集合K=(K1,K2,…,Kn) 及其詞頻信息作為文檔元數據。

2.2　權重計算

關鍵詞的重要程度通過權值來衡量。設用戶上傳文檔集總數為M ，可以通過關鍵詞Ki(i=1,2,…,n) 在文檔中出現的次數和含有關鍵詞Ki 的文檔佔總文檔的比例來計算權重，計算如式（1）所示：

式中TFi 為關鍵詞Ki 在文檔中出現的次數，M 為文檔總數，Fi 為含有關鍵詞 Ki文檔數。權重Wi 越大，表明關鍵詞Ki 在該文檔中越重要。

2.3　文檔屬性信息收集

用戶上傳文檔到雲資料庫時，伺服器需要記錄該文檔的相關信息，如文件大小、上傳時間。這樣用戶在查詢時可以對文件進行詳盡描述，從而更方便快捷地找到所需文件，提高檢索效率。同時，統計文檔被下載次數、被引次數、最近訪問時間等有效屬性，分別賦予各屬性相應的權值比重，使之和為1。該權重數據可在建立多屬性索引時使用，防止檢索結果對關鍵詞過分依賴。

2.4　建立索引

本文採用矩陣和線性多屬性耦合建立密文雙索引結構。

2.4.1　矩陣索引

以密文形式的關鍵詞Ki(i=1,2,…,n) 為橫坐標，密文形式的文檔Dj(j=1,2,…,t) 為縱坐標，設關鍵字Ki 相對文檔Dj 的詞頻權值為dij ，創建如式（2）的矩陣向量：

若關鍵字Ki 與文檔Dj 無關聯，則記元素dij=0 。通過和值統計函數將每個關鍵詞和文檔名對應的詞頻權值相加，即將矩陣的第i 行元素和第 j列元素的和值分別進行統計記為Ni 和Sj ，有：

Ni 值越大，其對應的文檔Di 被檢索的可能性越大；Sj 值越大，其對應的關鍵詞Kj 對檢索貢獻度越大。為了提高檢索效率，根據Ni 值的大小將矩陣索引進行行變換，使得Ni 值大的文檔名靠近矩陣上側。根據Sj 值的大小將矩陣索引進行列變換，使得Sj 值大的關鍵詞靠近矩陣左側。經過以上矩陣變換後形成了元素盡量分布在左上側的類稀疏矩陣，將被檢索期望值高的關鍵詞和文檔名集中在索引矩陣的左上角，然後檢索的遍歷從左上角開始，大大提升了檢索效率。由於是簡單的二維矩陣變換，所以建索時的計算開銷、索引更新的時間開銷均在可接受範圍。

2.4.2　線性多屬性索引

為減少檢索結果對關鍵詞的依賴，充分考慮用戶檢索行為和提高伺服器檢索效率，引入多屬性索引。本文通過改進傳統倒排索引結構，每一個關鍵詞的索引指向域包括除密文文件名之外的文件大小、上傳時間、被下載次數和最近下載時間共4個屬性。多屬性指針域的索引結構如圖2所示。

文檔的屬性可以反映它某方面的特徵，如下載次數多反映文檔的實用性廣，最近下載時間近反映近期雲用戶對該文檔的關注度高。可以根據實際檢索需求在索引中為文檔的多屬性設置不同權值組合。例如，在初始模式下各屬性權重一樣，均為0.25；常態模式下關鍵詞對應文件的文件大小、上傳時間、下載次數、最近下載時間屬性比重分別為0.2、0.2、0.3、0.3；在被下載次數優先模式下對應比重調整為0.1、0.1、0.7、0.1，以此突出下載次數在檢索時的重要性。設計者可以根據實際需求為文檔設置多條屬性值和比重不一但合理的權重值。

建立和更新多屬性線性索引以矩陣索引為依據，根據矩陣索引的橫標關鍵詞排序將線性索引中的關鍵詞進行同樣排序，使線性索引在檢索時也具備與矩陣索引排序一致的遍歷順序，增加檢索高效性。

2.4.3　雙索引多屬性耦合

雲環境中，在密文檢索時採用多線程並行計算對矩陣索引、線性多屬性索引同時進行檢索，其返回值都是關鍵詞對應的兩個文檔名稱集合，且每個文檔名都對應有一個權值，二者權值和也為1。一個關鍵詞對應的多個文檔進行排序，依據除了常用的根據綜合相關score大小進行排序[5]外，還需要結合該文檔各個屬性的屬性值與權值比重乘積之和排序。基於以上兩種機制綜合排序，返回用戶最關心的排名前 篇文檔。

3　密文關鍵詞查詢擴展方案

3.1　查詢擴展技術

查詢擴展是解決信息過載、不匹配等問題的重要技術。傳統的關鍵詞匹配技術重點關注查全率，而未考慮與關鍵詞語義相關的詞語，導致一些語義相關的文檔被忽略，查准率得不到保證。用戶只好儘可能多、儘可能准地輸入關鍵詞，使系統容易遭受字典攻擊，也降低了用戶使用體驗。通過構建本體[6]知識庫，對用戶輸入的關鍵詞進行推理擴展得到關鍵詞集合。若擴展的關鍵詞集過大，會對原始查詢產生雜訊影響，增加系統負荷。因此，利用語義相似度檢查設定相似度閾值，只選大於相似度閾值的詞語加入擴展關鍵詞集合，從而在保證一定查全率的情況下提高查准率。

3.2　查詢關鍵詞擴展演算法

本文藉助通用本體WordNet知識庫。該庫中詞間關係主要有同義詞、上下位、整體與部分等關係。利用以上關係構建以原始查詢關鍵詞為根節點的語義樹。當用戶輸入查詢關鍵詞a時，利用WordNet的層次結構知識庫構建以a為根節點語義樹，得到與a語義相關的詞作為樹的下一級子節點。依此繼續擴展，同時依次計算根節點與各節點的語義相似度，將相似度大於設定閾值的詞加入擴展集合，與a一起作為新的密文查詢關鍵詞集合。

一般用語義相似度描述詞語的相似程度，計算公式如下：

式中Ni 和Nj 分別表示概念詞Vi 、Vj 與最近公共父節點概念詞V 間的最短路徑，H 表示從V 到根節點的最短路徑。兩個詞的語義越接近，語義相似度越大。設語義相似度閾值為t ，以關鍵詞K0 為根節點構建擴展語義樹的流程如圖3所示。

首先查詢WordNet知識庫，若以關鍵詞K 為根節點的擴展樹尚未建立，則以K0 為根節點構建擴展樹，接著查詢該節點是否有同義詞節點。若無流程，直接結束；若有，則計算該擴展辭彙Ki 與K0 的語義相似度是否大於閾值t 。大於，則將Ki 辭彙加入擴展關鍵詞集，直到語義相似度小於閾值為止。該流程圖以同義詞關係擴展為例，也可以選擇上下位關係、整體與部分的關係進行本體語義擴展[7]。

利用此演算法給出一個以「protocol」為關鍵詞的擴展樹示意圖如圖4所示。可以看到，通過語義擴展，得到「protocol」的同義詞「communications protocol」，上位詞「rule」「prescript」，下位詞「file_transfer_protocol」「TCP」等擴展辭彙，為關鍵詞查詢提供了更多語義信息，能夠更好地領會用戶的查詢意圖。

4　實驗測試與分析

4.1　語義擴展方案測試分析

實驗硬體平台為Intel core_i5_750M CPU、64位系統、4G內存，採用檢索引擎工具包Lucene2.4.3、WordNet2.1搭建實驗環境，測試文檔集為RFC標準文檔集，文件格式為.txt，選其中500篇文檔作為測試集。

用「information」作關鍵詞進行檢索，設置語義相似度閾值為0.5，按照WordNet知識庫的語義樹期望，「information」的同義詞有「message」「info」「news」等。運行語義擴展搜索後會發現，包含「message」「information」「info」的數據都被檢索到了，說明關鍵詞語義得到了擴展。下面給出以「information」「design」為關鍵詞進行擴展語義的檢索統計信息，並用統計分析的方法判斷程序的結果覆蓋率，結果如表1所示。

從表1可以看到，加入語義擴展後，檢索返回的文檔覆蓋率都在95%以上，基於同義詞集合的語義擴展查詢收到了較好效果，能更好地領會用戶意圖。耗時方面，使用語義擴展檢索雖然耗時增加18%左右，但本身檢索耗時的基數不大，為毫秒級別，且從擴展後查詢的關鍵詞數量來看，數量增加到4倍，而耗時並沒有成4倍增加。可見，該演算法下時間開銷的增加幅度是可以接受的。

4.2　雙索引多屬性的檢索測試分析

使用語義擴展技術建立不同數量的關鍵詞，從建索速度、檢索效率、查准率三項參數方面，對比傳統線性檢索和多屬性雙索引檢索，結果如表2所示。

從表2數據可見，MRDI方案的建索時間明顯要大於傳統方案，隨著關鍵字數量增加，MRDI的建索耗時時間增加幅度變小；檢索時間方面，MRDI方案耗時明顯少於傳統方案，在關鍵詞數量很多時，檢索效率明顯高於傳統方案；查准率方面，二者的查准率都能保持在98%以上，當關鍵詞較少時，傳統方案佔優，關鍵詞數量增多時，MRDI查准率高於傳統方案。整體而言，MRDI方案在建立索引時耗時較多，而一旦索引建立，檢索時的效率便大大提高，其查准率也能得到保障，且隨著關鍵詞數量的增加，MRDI方案的優勢愈加明顯。

5　結　語

本文藉助雲平台的分散式計算能力加快建索速度，將系統的開銷盡量集中在索引建立時而不是檢索時，爭取做到「一次建索，多次高效」。在檢索時擴展查詢關鍵詞，爭取做到「合理擴展，有效返回」，降低檢索中對關鍵詞的依賴，提高查准率。從實驗結果分析來看，該方案具有一定的高效性和可用性。

但是，本文方案也存在不足：（1）語義擴展僅針對單個關鍵詞，未考慮多個關鍵詞的聯合語義擴展，使得根據不同關鍵詞生成的擴展集具有重複元素，拉低了系統效率；（2）多屬性權值的分配尚沒有合理的選擇演算法，使得檢索結果未必真正符合用戶期望；（3）在單機環境下測試，利用雲平台的並行計算能力來提高建索效率的初衷尚未實現。以上問題是本文繼續研究的方向，希望能夠繼續從索引建立和關鍵詞檢索兩部分對密文檢索系統進行改進研究，以期將該技術能更好地運用於雲環境中。

參考文獻：

[1] Song D X,Wanger D,Perrig A.Practical Techniques for Searches on Encrypted Data[C].Proceedings of 2000 IEEE Symposium on Security and Privacy,2000:44-55.

[2] Eu-Jin G.IACR Cryptology ePrint Archive [EB/OL].(2003-07-10)[2017-08-06].http://eprint.org/2003/216.pdf.

[3] Mehmet U.Searching on Encrypted Data[D].MD:University of Maryland College Park,2005:1-18.

[4] Wang C,Cao N,Li J,et al.Secure Ranked Keyword Search over Encrypted Cloud Data[C].2010 IEEE 30th International Conference on Distributed Computing System,2010:253-262.

[5] Zinger S,Millet C,Mathieu B,et al.Extracting an Ontology of Portrayable Object from WordNet[J].Muscle,2005:17-23.

[6] 尚新麗.國外本體構建方法比較分析飢[J].圖書情報工作,2012,56(04):116-119.

[7] Miller G A,Fellbaum C.WordNet Then and Now[J].Language Resources & Evaluation,2007,41(02):209-214.

作者：塗俊亮，雷　波

單位：中國電子科技集團有限公司第三十研究所，四川 成都 610041

作者簡介：塗俊亮，男，碩士，助理工程師，主要研究方向為信息安全、密碼技術應用；

雷　波，男，碩士，高級工程師，主要研究方向為計算機應用、信息安全、雲計算安全。

本文刊登在《通信技術》第12期（轉載請註明出處，否則禁止轉載）

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！