徐 惠，鐵治欣,2，舒 瑩

(1.浙江理工大學(xué)信息學(xué)院，浙江 杭州 310018； 2.浙江理工大學(xué)科技與藝術(shù)學(xué)院，浙江 紹興 312369)

0 引 言

隨著科技的進(jìn)步，云存儲技術(shù)的研究發(fā)展不斷完善，對各個領(lǐng)域產(chǎn)生深遠(yuǎn)的影響，云計算的高質(zhì)量、高效率服務(wù)也越來越受到人們的青睞，無論是個人用戶還是大型企業(yè)均選擇將龐大而復(fù)雜的數(shù)據(jù)存儲到云端，以便獲得極大的便利和經(jīng)濟節(jié)約[1-2]。這種云存儲技術(shù)不但能減輕本地存貯空間的壓力，還能降低用戶或者企業(yè)數(shù)據(jù)管理成本。

云存儲為用戶提供了一種存貯解決方案，實現(xiàn)了數(shù)據(jù)信息共享甚至提供一些高質(zhì)量的服務(wù)，但是，它并不能保證數(shù)據(jù)安全，直接將數(shù)據(jù)存儲到云端可能會造成隱私泄露。因此，數(shù)據(jù)上傳云端之前需要對其進(jìn)行加密，那以前用于明文的搜索技術(shù)將不能適用于這種新的存貯方式，可搜索加密技術(shù)應(yīng)運而生，不少學(xué)者在此方面做出了很多有益的工作。現(xiàn)有大部分密文排序檢索方法[3-8]是采用KNN(K-Nearest Neighbor)技術(shù)創(chuàng)建支持密文檢索的索引并通過匹配查詢請求和文檔索引返回搜索結(jié)果來實現(xiàn)的。其中加密方案時間復(fù)雜度大、存儲空間大，這與加密的密鑰、文檔索引和查詢請求的維度有著密切的關(guān)系。降低高維度的數(shù)據(jù)加密[4]是提高搜索效率的一種解決方法。還有一些學(xué)者嘗試如何提高檢索的靈活性[9-12]。因此面對不同的用戶需求，尋找一種不僅能保護用戶隱私，還能提高檢索效率，保證查詢精確度的方案是目前主要研究方向。

1 相關(guān)工作

云環(huán)境下采用可搜索加密技術(shù)可以很好地實現(xiàn)用戶數(shù)據(jù)的隱私保護，提高數(shù)據(jù)的利用效率。目前基于可搜索加密技術(shù)的研究主要分為數(shù)據(jù)加密索引的設(shè)計[2,7]、動態(tài)增刪云服務(wù)器數(shù)據(jù)以及索引[13-14]、搜索結(jié)果的完整性驗證[15-18]等。生成數(shù)據(jù)索引的過程中，索引的形式有通過關(guān)鍵詞映射生成的布隆過濾器[19-20]、計算關(guān)鍵詞權(quán)重的線性索引[2,4]和由關(guān)鍵詞組成的平衡二叉樹或B樹的樹形索引[3]。并且在整個可搜索加密技術(shù)的研究歷程中，相關(guān)研究工作也存在由單關(guān)鍵字搜索、布隆過濾器搜索到多關(guān)鍵詞搜索的升級。

可搜索加密技術(shù)最早在2000年由Song等[9]提出，將每一篇文檔看成等長的關(guān)鍵詞組成，分別對文檔和關(guān)鍵詞加密，然后加密后的文檔全文搜索后與加密關(guān)鍵詞比對，但是這種全文掃描的方式搜索效率低下。2003年，Goh等[19]第一次提出了利用布隆過濾器構(gòu)造文檔索引的對稱可搜索加密方案，然后將安全加密索引和加密文檔上傳到云端，搜索時，判斷索引的哈希值是否與查詢相同，并返回搜索結(jié)果。2005年，Chang和Mitzenmacher[21]第一次提出了在可搜索加密問題上真實的應(yīng)用場景，例如用戶先將文件信息在本地電腦上加密后上傳并存于云服務(wù)器上，然后在任何移動設(shè)備上提交關(guān)鍵詞檢索相關(guān)文件，并且使用了偽隨機函數(shù)來屏蔽關(guān)鍵詞索引，提高了文件更新的安全性。2011年，Curtmola等[22]提出了一種基于倒排索引的加密索引方案，構(gòu)建了高效且可證明安全的自適應(yīng)SSE方案，并且考慮了多用戶設(shè)置，所有者可以通過授予和撤銷其他用戶的搜索權(quán)限來控制搜索訪問。2012年，Wang等[12]第一次提出了一種同時支持多關(guān)鍵字查詢和模糊搜索的隱私保護方案，該方案使用基于通配符的模糊關(guān)鍵詞字集和布隆過濾器，在加密的文檔數(shù)據(jù)上完成關(guān)鍵字的模糊搜索，而且服務(wù)器使用了偽隨機函數(shù)返回搜索結(jié)果。2020年，Guan等[23]提出了一種跨語言的多關(guān)鍵詞排名語義搜索的方案，通過構(gòu)建一個跨語言的目標(biāo)查詢系統(tǒng)對查詢請求進(jìn)行語義轉(zhuǎn)換和擴展，同時利用堆二叉樹結(jié)構(gòu)實現(xiàn)高效隱私保護的Top-k檢索。

雖然上面的方案對于可搜索加密技術(shù)在不同方向上作了不同程度的改善。但是在多關(guān)鍵詞的密文排序搜索技術(shù)在數(shù)據(jù)隱私保護、檢索效率以及結(jié)果的完整性等方面還有待進(jìn)一步研究。

2 問題描述

2.1 系統(tǒng)模型

可搜索加密過程的系統(tǒng)模型架構(gòu)如圖1所示。

圖1 可搜索加密系統(tǒng)模型架構(gòu)

可搜索加密模型包含3個不同的實體：云服務(wù)器、數(shù)據(jù)擁有者、數(shù)據(jù)使用者。數(shù)據(jù)擁有者首先把數(shù)據(jù)當(dāng)作文檔提取其關(guān)鍵詞，構(gòu)成關(guān)鍵詞詞典，根據(jù)該詞典創(chuàng)建每篇文檔的索引，然后將文檔和索引加密后上傳到云服務(wù)器上儲存。當(dāng)授權(quán)的數(shù)據(jù)使用者通過輸入多個關(guān)鍵詞查詢文檔時，利用搜索控制機構(gòu)根據(jù)查詢關(guān)鍵詞生成相應(yīng)的關(guān)鍵字陷門，將陷門和返回的文檔數(shù)目參數(shù)k作為搜索請求一起上傳給云服務(wù)器。服務(wù)器收到搜索請求后，首先計算關(guān)鍵詞陷門和每篇文檔索引的安全內(nèi)積，然后將內(nèi)積值降序排序，最后返回前k個加密文檔給數(shù)據(jù)使用者。數(shù)據(jù)使用者收到返回的結(jié)果后對加密文檔進(jìn)行解密，獲取所需數(shù)據(jù)信息。

2.2 攻擊模型

在密文搜索的過程中由于云服務(wù)器具有“誠實但又好奇”的特性[2]，它會根據(jù)文檔索引和搜索請求相關(guān)信息推斷所要搜索的文檔的大致內(nèi)容，這可能會造成對用戶隱私信息的泄漏[7]。所以在整個密文搜索過程中會考慮2種不同攻擊能力的威脅模型：

級別1：云服務(wù)器知道加密的數(shù)據(jù)集、搜索請求。

級別2：云服務(wù)器不但知道加密數(shù)據(jù)集和搜索請求，還知道一些背景信息，包括陷門之間的相關(guān)性，以及一些數(shù)據(jù)的統(tǒng)計信息。

2.3 設(shè)計目標(biāo)

本文在MRSE方案[7]的基礎(chǔ)上提出了基于特征匹配的快速降維排序搜索方法，其主要工作如下：

1)提出特征得分算法。在創(chuàng)建文檔索引時，利用文檔特征關(guān)鍵詞與特征詞典中的每一個特征通過特征得分算法計算相關(guān)性得分，創(chuàng)建文檔的索引特征向量。

2)提出匹配得分算法。在用戶輸入關(guān)鍵詞查詢時，利用查詢關(guān)鍵詞與特征詞典中每一個特征計算得分，創(chuàng)建查詢匹配向量。

3)通過K-L變換算法[24]對所有文檔的索引特征向量矩陣和查詢匹配向量進(jìn)行降維，使得主要信息集中在較少的維度上，從而降低密鑰的維度，簡化了加密運算，提高了檢索的效率。

2.4 符號說明

本文使用的符號說明如下：

F：明文的文檔集，表示為F={F1,F2,…,Fm}。

G：包含文檔集中每一篇文檔的特征關(guān)鍵詞的特征集，表示為G={g1,g2,…,gm}。

gi：第i篇文檔的特征關(guān)鍵詞。

W：由G中的特征關(guān)鍵詞匯總?cè)ブ靥幚砗蠼M成的特征詞典，表示為W={w1,w2,…,wn}。

wj：特征詞典中的第j個特征關(guān)鍵詞。

n：特征詞典中所有特征關(guān)鍵詞的總數(shù)。

Pi：第i篇文檔的索引特征向量，表示為Pi=(pi1,pi2,…,pin)。

I：加密后的文檔索引集，表示為I={I1,I2,…,Im}。

q：查詢的關(guān)鍵詞詞集，表示為q={q1,q2,…,qz}。

Q：查詢關(guān)鍵詞的查詢向量，表示為Q=(Q1,Q2,…,Qn)。

T：查詢陷門。

3 算法解釋

3.1 BM25算法

BM25算法模型[25]是一種評價查詢關(guān)鍵詞和文檔之間相關(guān)性的算法。由詞在文檔中的相關(guān)度、詞在查詢關(guān)鍵字中的相關(guān)度以及詞的權(quán)值這3個部分組成。假設(shè)有一組查詢關(guān)鍵詞s，首先進(jìn)行語素分析得到單個關(guān)鍵詞詞集{s1,s2,…，sn}，再計算每個關(guān)鍵詞與某篇文檔的相關(guān)性得分，最后將每個關(guān)鍵詞對于該文檔的相關(guān)性得分做一個加權(quán)求和便得到最終得分。其中關(guān)鍵詞的權(quán)值，就是一個詞與一個文檔的相關(guān)性的權(quán)重，因此可以用公式(1)計算IDF(si)：

(1)

公式(1)中的N表示總的文檔數(shù)，n(si)表示含有關(guān)鍵詞si的文檔數(shù)。

關(guān)鍵詞和文檔的相關(guān)度，與TF-IDF模型中用關(guān)鍵詞的詞頻來表示不同，這里用公式(2)計算：

(2)

其中，tfsi表示關(guān)鍵詞si在文檔Fi中出現(xiàn)的頻率，Ld表示文檔Fi的長度，Lave表示整個文檔集中文檔的平均長度，k1、b都是調(diào)節(jié)參數(shù)，k1用來控制關(guān)鍵詞在文檔中出現(xiàn)頻率的縮放程度，b用來控制文檔長度的縮放程度，通常k1取值1.2，b取值0.75。

3.2 特征得分算法

由BM25算法模型可知，這種計算多個關(guān)鍵詞對于某篇文檔的權(quán)重之和得分，或許會出現(xiàn)一些錯誤得分情況，影響其在文檔中的重要程度。例如Fi中的特征關(guān)鍵詞與詞典匹配，得hx,b={“joint keywords”, “concurrent programming”}，F(xiàn)j中的特征關(guān)鍵詞與詞典中特征關(guān)鍵詞匹配，得hx,k={“joint keywords”}，由于“joint keywords”在文檔Fj中出現(xiàn)的頻率高，而“joint keywords”,“concurrent programming”在文檔Fi中出現(xiàn)的頻率較低，這會導(dǎo)致hx,b的“joint keywords”、“concurrent programming”兩者的權(quán)重得分之和小于hx,k中“joint keywords”的一個詞的權(quán)重得分。但檢索時根據(jù)得分高低會先返回文檔Fj，這就出現(xiàn)了查詢結(jié)果誤差了。因此，本文提出了特征得分算法和匹配得分算法，綜合考慮特征關(guān)鍵詞和查詢關(guān)鍵詞在詞典中的匹配情況，分配不同的得分，避免出現(xiàn)這種誤差。

特征得分算法在創(chuàng)建文檔索引特征向量Pi時，每個維度上的值根據(jù)文檔特征關(guān)鍵詞與詞典特征相匹配的關(guān)鍵詞的數(shù)量分配不同的得分：

1)當(dāng)文檔Fi中的特征關(guān)鍵詞gh與詞典中的特征wj完全相同時，說明該特征能充分反映該文檔的主要內(nèi)容，該維度應(yīng)該設(shè)置為最高的特征得分Imax，高于其他任何的匹配情況。

2)當(dāng)gh和wj不完全相同，沒有一個關(guān)鍵詞相同時，該維度特征得分為0。

3)當(dāng)有部分匹配時，該維度特征得分為匹配的多個關(guān)鍵詞的權(quán)重得分之和，用BM25算法模型中公式(2)的R(si,d)分?jǐn)?shù)之和來表示。但是這種計算得分的算法會有出現(xiàn)上述誤差的情況，因此在這里引入一個調(diào)節(jié)參數(shù)αb，參與每一個匹配關(guān)鍵詞在文檔中得分的計算，即gh和wj中匹配成功的第b個關(guān)鍵詞si,b在文檔Fi中的得分用公式(3)表示：

FS′=R(si,b,Fi)+αb

(3)

其中，α1=α,αb=αb-1qα，α為等比數(shù)列αb的首項，qα為等比數(shù)列αb公比。

因此，當(dāng)文檔Fi中特征關(guān)鍵詞與詞典特征匹配后，文檔Fi的索引特征向量Pi的第j維特征得分用公式(4)所示：

(4)

3.3 匹配得分算法

匹配得分算法在用戶進(jìn)行檢索前，輸入查詢關(guān)鍵詞詞集q生成查詢匹配向量Q，根據(jù)q與詞典中每一個特征wj的不同匹配情況去分配得分：

1)當(dāng)查詢關(guān)鍵詞詞集q與詞典中某個特征wj完全相同時，那么將查詢匹配向量中的第j維的匹配得分QS設(shè)置為最高的匹配得分Qmax。

2)當(dāng)q和wj中沒有一個匹配的關(guān)鍵詞時，QS=0。

3)當(dāng)q和wj中的關(guān)鍵詞有部分匹配成功時，該維度匹配得分為匹配的多個關(guān)鍵詞的權(quán)重得分之和，用BM25算法模型中公式(1)的IDF(si)分?jǐn)?shù)之和來表示，并且引入調(diào)節(jié)參數(shù)βb來調(diào)節(jié)多個關(guān)鍵詞匹配成功后計算的匹配得分，q與wj中匹配成功的第b個關(guān)鍵詞在文檔中的得分由公式(5)表示：

QS′=IDF(sj,b)+βb

(5)

其中，β1=β,βb=βb-1qβ，β為等比數(shù)列βb的首項，qβ為等比數(shù)列βb公比。

因此，查詢關(guān)鍵詞與詞典特征匹配后，查詢匹配向量Q中的第j維的匹配得分由公式(6)表示：

(6)

4 基于文檔特征匹配的快速降維排序搜索方案

本章從6個部分詳細(xì)介紹本文提出的基于文檔特征匹配的快速降維排序搜索方案(DRFM)。

4.1 文檔處理

對于每一篇文檔Fi(i=1,2,…,m)，數(shù)據(jù)擁有者提取具有主題意義的多個關(guān)鍵詞作為其特征關(guān)鍵詞gi，m篇文檔的特征關(guān)鍵詞就組成了一個特征集G。將特征集中的所有特征關(guān)鍵詞進(jìn)行匯總?cè)ブ靥幚?，生成了特征關(guān)鍵詞詞典W,其中特征關(guān)鍵詞的個數(shù)為n。

4.2 初始索引特征向量降維

1)為每一篇文檔Fi(i=1,2,…,m)創(chuàng)建一個n維的原始索引Pi=(pi1,pi2,…,pin)。其中索引的每一維pij(j=1,2,…,n)的值由公式(4)計算。

2)將m篇文檔的初始索引特征向量Pi=(pi1,pi2,…,pin)組成了一個m×n維的索引特征向量矩陣P=(P1,P2,…，Pm)T。

3)設(shè)置相應(yīng)的閾值，根據(jù)K-L變換算法得到一個新的n×t維的特征變換矩陣R，然后對原始矩陣P進(jìn)行K-L變換降維，使P′=PR，變換后的矩陣P′=(P′1,P′2,…，P′m)T，將有用的信息集中在其中的t維上，閾值的選擇使得誤差最小，信息最大程度集中在較少的維數(shù)上，其中P′i是t維的該文檔Fi(i=1,2,…,m)的降維后的索引特征向量。

4.3 生成密鑰

在這個部分，數(shù)據(jù)擁有者執(zhí)行密鑰生成算法生成2個可逆的隨機矩陣M1、M2和一個分割指示器S，此處M1、M2均為(t+u+1)×(t+u+1)的可逆矩陣，S[i]∈{0,1}t+u+1，其中,t是降維后的索引特征向量的維數(shù)，(u+1)是擴展的維度。生成的密鑰可以表示為K={S,M1,M2}。

4.4 加密初始索引

(7)

第三步：分別加密分割后的索引I′i和I″i。通過對稱密鑰M1、M2對索引I′i和I″i進(jìn)行加密，生成每一篇文檔的加密索引Ii={I′iTM1,I″iTM2}。

4.5 創(chuàng)建陷門

(8)

式中r、e為隨機數(shù)。

第三步：隨機分割擴展的查詢匹配向量。根據(jù)分割指示器S的值將擴展的查詢請求隨機分割成2個查詢向量Q′和Q″，它們的第j(j=1,2,…,t+u+1)維的值按公式(9)進(jìn)行賦值:

(9)

4.6 查詢

當(dāng)云服務(wù)器接收到授權(quán)用戶的搜索請求(包括陷門和返回的文檔數(shù)目參數(shù)k)后執(zhí)行公式(10)得到每一篇文檔的得分，并且返回得分高的前k個加密文檔。用戶解密這些加密的文檔后得到相關(guān)信息。

(10)

5 性能分析

5.1 精確度

在DRFM方案中，利用特征得分算法創(chuàng)建索引特征向量，利用匹配得分算法創(chuàng)建查詢匹配向量。在這2個算法中的最高得分Imax和Qmax應(yīng)該設(shè)置大于任何情況下的得分，并且2個調(diào)節(jié)參數(shù)αb和βb分別是首項為α、β，公比是qα、qβ的等比數(shù)列，才能保證匹配關(guān)鍵詞越多，得分越高。因此一般情況下，Imax、Qmax、qα、qβ的數(shù)值越大，文檔的查詢區(qū)別就越明顯。因為在風(fēng)險等級為2的情況下，云服務(wù)器知道背景信息和關(guān)鍵詞的統(tǒng)計信息，如果分?jǐn)?shù)設(shè)置過大，即明確告訴服務(wù)器該關(guān)鍵詞能表達(dá)該文檔的主要信息，那么可能造成文檔內(nèi)容的泄漏。于是為了精確度并且防止隱私泄漏，一般情況下，公比可以設(shè)置為qα、qβ∈(2,2.5)。初始的調(diào)節(jié)參數(shù)可以設(shè)置為α比IF高，β比QF高，IF是文檔特征中g(shù)i(i=1,2,…,m)中的關(guān)鍵詞在文檔中的最高得分，QF是詞典特征wj(j=1,2,…,n)中關(guān)鍵詞在文檔中的最高得分。

當(dāng)在文檔Fi中有(p+1)個關(guān)鍵詞匹配成功，文檔Fj中有p個關(guān)鍵詞匹配成功時，由公式(3)可知，每一個匹配成功的關(guān)鍵詞的得分由2個部分組成，如第b個關(guān)鍵詞si,b的得分由其在文檔中的得分R(si,b,Fi)和αb組成，那么(p+1)個關(guān)鍵詞在文檔Fi中的得分與p個關(guān)鍵詞在文檔Fj中的得分之差如公式(11)所示：

(11)

其中，ab表示文檔Fi匹配成功的(p+1)個關(guān)鍵詞中第b個關(guān)鍵詞在文檔中的得分R(si,b,Fi)，bd表示文檔Fj匹配成功的p個關(guān)鍵詞中第d個關(guān)鍵詞在文檔中的得分R(sj,d,Fj)。

由公式(11)最后結(jié)果可知，α大于b1到bp中的任意值，q>2，考慮最極端的一種情況，假設(shè)b1是最大值，(b1+b2+…+bp)的值最大時為(p·b1)，那么α·qp永遠(yuǎn)大于(p·b1)，公式(11)的結(jié)果也就永遠(yuǎn)大于0成立。因此，當(dāng)創(chuàng)建文檔索引特征向量和查詢匹配向量時，保證了當(dāng)匹配成功的關(guān)鍵詞越多，這一維的得分也就越高。

5.2 效率分析

在創(chuàng)建索引特征向量后，將索引進(jìn)行擴維加密的過程中，在m篇文檔初始索引特征向量創(chuàng)建后，引入了K-L變換算法。雖然求K-L變換矩陣需要比較多的時間，但這只是一次工作，即只需要在加密文檔索引前求一次就可。變換后的索引特征向量由原來的n維變成t維，將高維的特征向量最大程度地集中在較少數(shù)的維數(shù)上，從而降低了運算的維度，提高了效率。

5.3 隱私分析

1)密鑰的安全性。在2.2節(jié)中級別2的攻擊模型下，云服務(wù)器知道一些數(shù)據(jù)集、陷門的統(tǒng)計信息，但是它無法得知具體的擴維、加密的過程。以m篇文檔降維后的索引特征向量加密過程為例，該過程可以建立方程式(12)：

(12)

其中，M1、M2是2個隨機生成的(t+u+1)×(t+u+1)維的矩陣，那么m篇文檔會產(chǎn)生2m(t+u+1)個方程式，但是I′i、I″i中有2m(t+u+1)個未知數(shù)，M1、M2中有2(t+u+1)2個未知數(shù)，這個方程式不足以解出這些未知數(shù)，也就無法反推出密鑰的信息。

2)關(guān)鍵詞和索引特征向量信息的安全性。云服務(wù)器是無法得知詞典中特征關(guān)鍵詞的個數(shù)以及組成情況的，也就無法推出關(guān)鍵詞信息。在進(jìn)行K-L變換降維時，由于閾值的選擇隨機性，降維后的矩陣也不確定，這也大大提高了關(guān)鍵詞的安全性。在索引擴維部分又引入了一組隨機的不相等的數(shù)ε1,ε2,…,εu，且εi∈N(μ,c2)(i=1,2,…,u)，受標(biāo)準(zhǔn)差c的控制來調(diào)節(jié)其的大小，云服務(wù)器就更難分析出索引的信息。

3)查詢信息和陷門的安全性。在生成查詢匹配向量的過程中，通過詞典特征與查詢關(guān)鍵詞的不同匹配情況設(shè)置得分，這樣為查詢信息的隱私保護增加了一道屏障。并且在生成陷門的擴展維度以及隨機分割的過程中又引入了隨機數(shù)r、e，就算輸入相同的查詢關(guān)鍵詞也會生成不同的陷門，從而防止了云服務(wù)器對用戶信息的泄漏。

5.4 實驗分析

為驗證本文所提方法的有效性，采用RFC(Request For Comments)文檔[7]作為實驗的測試數(shù)據(jù)集，服務(wù)器操作系統(tǒng)為Windows10，CPU為Intel 4核3540(2.66 GHz)處理器。

第一個實驗是關(guān)于閾值的選擇對于查詢時間以及返回文檔的精確度的影響。圖2為當(dāng)K-L變換閾值分別為0.8、0.85、0.9、0.95時，文檔數(shù)從1000增加到6000，要求返回30篇文檔，在相同的查詢關(guān)鍵詞情況下，查詢時間的變化情況。圖3是在文檔數(shù)6000篇時，要求查詢返回30篇文檔，查詢精度隨K-L變換閾值的變化而變化的情況，這里查詢精度A用公式(13)來計算：

圖2 在不同的閾值下，查詢時間隨著文檔數(shù)的增加的變化趨勢

圖3 在6000篇文檔的試驗下，不同的閾值對精確度的影響

A=Lm/Ln

(13)

其中，Ln表示查詢文檔返回的總數(shù)，Lm表示這些文檔中含有查詢關(guān)鍵詞的文檔數(shù)。

從圖2可以看出，不管閾值選擇為多少，實驗結(jié)果都隨著文檔數(shù)的增加，查詢時間不斷增加，從時間復(fù)雜度的角度分析，加密過程中密鑰的維度為t，是特征關(guān)鍵詞詞典中關(guān)鍵詞的總數(shù)。由于需要擴展該維度以確保數(shù)據(jù)安全，(u+1)就是擴展的維度。檢索算法采用了向量安全內(nèi)積和的方法，查詢時間依賴于文檔的數(shù)目和關(guān)鍵詞詞典的大小，所以m篇文檔的查詢時間復(fù)雜度近似于O(m(t+u))?？梢钥闯鲭S著文檔數(shù)不斷增加，查詢時間也相應(yīng)地增加。但是當(dāng)閾值越小時，選擇的新特征維數(shù)也就越小，那么降維的幅度就越大，這樣就降低了查詢時間，然而降維的幅度越大，特征損失越多，又影響查詢結(jié)果的準(zhǔn)確度。圖3的實驗是為了選擇合適的閾值進(jìn)行K-L變換降維，于是比較了相同條件下，不同的閾值對查詢結(jié)果精確度的影響。從圖3可以看出，閾值越大，精確度才更高，因此結(jié)合圖2和圖3，綜合考慮一般的查詢精度要求，下面的實驗選擇閾值為0.95。

第二個實驗測試了閾值在0.95時，DRFM方案在不同文檔數(shù)，如1000、2000、…、6000時，與MRSE方案[7]、CRQM方案[4]查詢的時間比較，此時CRQM方案中降維的閾值也取值0.95，實驗結(jié)果如圖4所示。在這個實驗測試中，為了結(jié)果的公平性和準(zhǔn)確性，每次在文檔不同時提取的關(guān)鍵詞個數(shù)，即詞典的維度是相等的，并且擴展維度u都是100。

圖4 檢索關(guān)鍵詞為10個，文檔數(shù)不同時，3種方案查詢時間的比較

從圖4可以看出，查詢的時間上3種方案也是隨著文檔數(shù)的增加，時間不斷增長，并且MRSE方案要比CRQM、DRFM方案多了將近50%的時間。這是因為文檔數(shù)越大，檢索的范圍也就越大，消耗的時間就增多了，但是CRQM和DRFM方案都在不同程度上進(jìn)行了降維，因此最后的查詢時間相差不多。但在相同條件下，DRFM比CRQM快一些，如在文檔數(shù)為1000時，DRFM比CRQM快近似7%。

第三個實驗測試了閾值在0.95時，在文檔數(shù)相同而關(guān)鍵詞個數(shù)不同時，這3種方案創(chuàng)建陷門和查詢時間的比較。由上可知，檢索的效率和詞典維度息息相關(guān)，那么在文檔數(shù)相同的情況下，關(guān)鍵詞的個數(shù)不同也會影響這些算法過程的效率。該實驗選擇文檔數(shù)為6000時，擴展維度都為100，關(guān)鍵詞的個數(shù)分別為1000、2000、…、5000，實驗結(jié)果如圖5、圖6所示。

圖5 文檔數(shù)為6000時，詞典中關(guān)鍵詞個數(shù)不同時，3種方案創(chuàng)建陷門的時間比較

圖6 文檔數(shù)為6000時，詞典中關(guān)鍵詞個數(shù)不同時，3種方案查詢時間的比較

從圖5可以看出，3種方案創(chuàng)建陷門的時間也是隨著關(guān)鍵詞個數(shù)的增加不斷增長，并且3種方案的時間相差不大。這是因為關(guān)鍵詞的個數(shù)即是詞典的維度，也就是密鑰索引和陷門的維度，這個數(shù)完全決定了創(chuàng)建陷門的時間效率，但是又因為陷門表示為一個1×n維的向量矩陣，要比索引的m×n維向量矩陣小許多，所以創(chuàng)建的過程時間差也就不大。

從圖6可以看出，3種方案查詢的時間同樣隨著關(guān)鍵詞的個數(shù)增加而不斷增長，但是CRQM和DRFM要比MRSE方案快許多，DRFM方案最快。這是因為DRFM方案在創(chuàng)建索引和陷門的過程中都進(jìn)行了降維的算法操作，導(dǎo)致最后查詢的矩陣運算計算量減少，提高了查詢速度。然而CRQM方案中加入了單位矩陣，無疑又增加了一些計算量，所以查詢速度要比DRFM方案慢一些，如在關(guān)鍵詞詞典中關(guān)鍵詞個數(shù)為5000時，DRFM比CRQM快近似30%。

第四個實驗測試了3種方案在文檔數(shù)為5000時，返回不同的文檔數(shù)時準(zhǔn)確度的比較，此時擴展維度u等于100。

從圖7可以看出，DRFM方案和CRQM方案精確度差不多，因為它們降維過程中的閾值都取0.95，CRQM方案通過創(chuàng)建索引時添加了一個單位矩陣保證了精確度，而DRFM方案在創(chuàng)建索引和陷門的過程中，提出特征得分算法和匹配得分算法進(jìn)行關(guān)鍵詞的匹配計算不同的得分作為各組向量的一維數(shù)值，最后查詢時計算內(nèi)積值，進(jìn)行內(nèi)積值降序排序返回結(jié)果的。總體而言，MRSE方案的精確度最低。

圖7 當(dāng)文檔數(shù)為5000時，在查詢返回不同數(shù)量的文檔時，3種方案在查詢準(zhǔn)確度上的比較

6 結(jié)束語

本文提出了一種基于文檔特征匹配的快速降維排序搜索方案。通過提出的特征得分算法來創(chuàng)建每一篇文檔的索引特征向量，其每一維數(shù)值對應(yīng)著該篇文檔的特征關(guān)鍵詞與詞典中每一個特征關(guān)鍵詞通過特征得分算法計算的得分；通過提出的匹配得分算法來創(chuàng)建查詢關(guān)鍵詞的查詢匹配向量，其每一維數(shù)值對應(yīng)著查詢關(guān)鍵詞與詞典中每一個特征關(guān)鍵詞通過匹配得分算法計算的得分。最后通過K-L變換算法提取新特征，最大程度保留原來的信息，將索引特征向量和查詢匹配向量都進(jìn)行了降維，減少了加密和查詢過程的內(nèi)積運算，提高了查詢速度。實驗表明，該算法是有效的。