【支持通配符的常用技術(shù)分析4300字】_第1頁
【支持通配符的常用技術(shù)分析4300字】_第2頁
【支持通配符的常用技術(shù)分析4300字】_第3頁
【支持通配符的常用技術(shù)分析4300字】_第4頁
【支持通配符的常用技術(shù)分析4300字】_第5頁
已閱讀5頁,還剩5頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

支持通配符的常用技術(shù)分析綜述目錄TOC\o"1-3"\h\u20921支持通配符的常用技術(shù)分析綜述 1104811.1布隆過濾器 1147061.1.1布隆過濾器的構(gòu)造 1126421.1.2支持單個(gè)通配符查詢的可搜索加密 2187961.1.3支持多個(gè)通配符查詢的可搜索加密 3197541.2關(guān)鍵詞索引樹 4153741.2.1基本介紹 4102341.2.2關(guān)鍵詞索引樹的構(gòu)建 514351.2.3關(guān)鍵詞索引樹的搜索過程 8263621.3安全KNN方案 91.1布隆過濾器1.1.1布隆過濾器的構(gòu)造1970年,布隆過濾器被首次提出來,該技術(shù)可以用來判斷一個(gè)集合中是否擁有某個(gè)元素[26],其主要思想是:將該元素輸入至若干個(gè)哈希函數(shù)中,經(jīng)過哈希運(yùn)算后,會(huì)分別輸出若干個(gè)值,將布隆過濾器上這幾個(gè)值對(duì)應(yīng)的位置設(shè)為“1”。當(dāng)需要判斷該元素是否在集合中時(shí),只要判斷這幾個(gè)位置上的值是不是為“1”即可。因此布隆過濾器的詳細(xì)構(gòu)造流程可描述為以下幾個(gè)步驟:首先先定義一些符號(hào),符號(hào)及相對(duì)應(yīng)的說明如表1.1所示表1.1布隆過濾器相關(guān)符號(hào)及說明符號(hào)說明含有n個(gè)元素的集合m布隆過濾器的長(zhǎng)度k哈希函數(shù)的個(gè)數(shù),每個(gè)哈希函數(shù)均不同第i個(gè)哈希函數(shù),其中首先將布隆過濾器上m比特的值初始化為0,然后將集合中的某個(gè)元素,分別輸入至k個(gè)哈希函數(shù)中,輸出k個(gè)哈希值,同時(shí)把布隆過濾器中對(duì)應(yīng)位置設(shè)為1。如此往復(fù)n次,將n個(gè)元素依次插入到布隆過濾器中。最后,當(dāng)要查詢集合S中是否擁有元素q時(shí),則將q分別輸入至k個(gè)哈希函數(shù)中,輸出k個(gè)哈希值,觀察布隆過濾器上這k個(gè)哈希值對(duì)應(yīng)位置的值是否全為1,若是,則q存在集合S中,反之則反。下面給出一個(gè)生成布隆過濾器的例子。假設(shè),布隆過濾器長(zhǎng)度為10,獨(dú)立選擇三個(gè)不同的哈希函數(shù)。示例如圖1.1所示圖1.1布隆過濾器構(gòu)造示例1.1.2支持單個(gè)通配符查詢的可搜索加密本節(jié)將介紹支持單個(gè)通配符查詢的可搜索加密,先考慮關(guān)鍵詞中只含一個(gè)通配符的情況。其搜索的基本思想是首先為所有關(guān)鍵詞分別生成一個(gè)布隆過濾器,并將其存儲(chǔ)至數(shù)據(jù)庫中作為索引。當(dāng)需要搜索關(guān)鍵詞時(shí),用戶再為待搜索的關(guān)鍵詞構(gòu)建一個(gè)布隆過濾器,然后將此布隆過濾器與數(shù)據(jù)庫中的索引逐一進(jìn)行比較得到符合要求的結(jié)果。在建立索引的過程中,假設(shè)某個(gè)長(zhǎng)度為l個(gè)字符的關(guān)鍵詞w,該關(guān)鍵詞中每個(gè)字符可以記為,然后將得到一個(gè)索引集合其中表示字符在關(guān)鍵詞中的正序位置,表示字符在關(guān)鍵詞中的逆序位置。比如關(guān)鍵詞為“drag”,那么它的索引集合為。在生成陷門的過程中,假設(shè)某個(gè)含有一個(gè)通配符且長(zhǎng)度為l的搜索關(guān)鍵詞w,其中每個(gè)字符分別記為,其中*表示通配符,且通配符在關(guān)鍵詞中所處位置為i。對(duì)于通配符之前的字符,記錄其正向順序,即。對(duì)于通配符之后的字符,記錄其逆向順序,因此將得到一個(gè)陷門集合 比如含有一個(gè)通配符的搜索關(guān)鍵詞為“d*g”,那么它的陷門集合為。由此容易觀察到,如果含有通配符的搜索關(guān)鍵詞與索引中的關(guān)鍵詞相匹配的話,則陷門集合應(yīng)該是索引集合的子集。容易觀察到,該通配符能夠表示若干個(gè)字符。最后再分別對(duì)陷門集合和索引集合生成兩個(gè)布隆過濾器,并且比較兩個(gè)布隆過濾器相應(yīng)位置的值,判斷兩者是否匹配。圖1.2給出了匹配過程的一個(gè)示例。圖1.2單個(gè)通配符查詢過程示例1.1.3支持多個(gè)通配符查詢的可搜索加密一般來說,一個(gè)關(guān)鍵詞中可能存在多個(gè)通配符,下面考慮含有若干通配符的情形,將對(duì)擁有兩個(gè)通配符的搜索關(guān)鍵詞“c*o*d”作為樣例來進(jìn)行闡釋。此時(shí),如果仍然使用上文提到的方法,則不能準(zhǔn)確地描述字符“o”的位置,因此在生成陷門的時(shí)候需要考慮每個(gè)字符的存在性,所以可以在陷門布隆過濾器中添加字符“c、o、d”的存在性,約定用比特“0”表示該字符的存在性,將添加到陷門集合中。另外,陷門集合還需要記錄第一個(gè)通配符之前所有字符的正向順序和最后一個(gè)通配符后所有字符的逆向順序。比如,含有兩個(gè)通配符的搜索關(guān)鍵詞“c*o*d”,其陷門集合為。與此同時(shí),在建立索引的過程中,也要將關(guān)鍵詞中每一個(gè)字符的存在性添加到索引布隆過濾器中。比如關(guān)鍵詞“cloud”,它的索引集合為:圖1.3給出了匹配過程的樣例。圖1.3多個(gè)通配符查詢過程示例1.2關(guān)鍵詞索引樹1.2.1基本介紹通常來說,數(shù)據(jù)使用者希望能從云服務(wù)器中快速找到自己需要的文件,因此遍歷文件集合中所有文件的方法一般是不可取的,所以需要考慮文件和查詢關(guān)鍵詞間的相關(guān)系數(shù),從而對(duì)搜索結(jié)果進(jìn)行排序,并將最滿足搜索條件的前k個(gè)文件傳輸給用戶??梢岳肨F-IDF值來判斷密文文件與搜索關(guān)鍵詞之間的相關(guān)程度。下面將詳細(xì)地介紹一種計(jì)算TF-IDF值來建立關(guān)鍵詞向量的方案。首先需要從文件集合中提取m個(gè)關(guān)鍵詞,并且為每一個(gè)文件構(gòu)建一個(gè)m維的關(guān)鍵詞向量,將其每一維都用一個(gè)確定的關(guān)鍵詞來表示,并且將每一個(gè)元素的值都設(shè)置成對(duì)應(yīng)關(guān)鍵詞在文件中的TF-IDF值。TF值可由以下公式求得:(1.1)其中,是歸一化因子,是關(guān)鍵詞在文件中出現(xiàn)的頻率。文件的逆文檔頻率IDF可用如下公式計(jì)算:(1.2)其中n表示文件總數(shù)目,表示包含關(guān)鍵詞的文件個(gè)數(shù),是歸一化因子。1.2.2關(guān)鍵詞索引樹的構(gòu)建文獻(xiàn)[25]提出的REMKS方案構(gòu)造了一個(gè)關(guān)鍵詞索引樹來加快搜索速度。索引樹本質(zhì)是一個(gè)平衡二叉樹,其每一個(gè)葉子節(jié)點(diǎn)均分別代表一個(gè)文件,其中存放了向量形式的關(guān)鍵詞的TF-IDF值。如圖1.4為關(guān)鍵詞索引樹結(jié)構(gòu)構(gòu)造的一個(gè)樣例,其中為文檔集合。首先REMKS方案將內(nèi)容相似的文件放在樹中相鄰的位置來節(jié)省不必要的計(jì)算開銷。即先提取每個(gè)文檔的TF-IDF值,比如的TF-IDF值為(0,0.2,0.6,0.7),的TF-IDF值為(0,0,0.5,0.6)等,并且將TF-IDF值相差最小的兩個(gè)文件放在相鄰的位置,比如的TF-IDF值與的TF-IDF值相差為(0.1,0.1,0.1,0),但與的TF-IDF值相差為(0.1,0.3,0.2,0.2),與的TF-IDF值相差為(0.2,0.3,0.2,0.1),同樣與其他文件的TF-IDF值相比,的TF-IDF值與的TF-IDF值相差最小,因此將文件和文件放在了相鄰位置,同理將和,和,和放在了相鄰位置,由此往復(fù)得到了如圖1.4的文件順序。然后每次選取兩個(gè)相關(guān)性最高的文件相應(yīng)的葉子節(jié)點(diǎn),并且構(gòu)造父節(jié)點(diǎn),父節(jié)點(diǎn)也表示為向量形式,其每一維的值等于左右子節(jié)點(diǎn)中向量相應(yīng)位置較大的值。比如父節(jié)點(diǎn)由子節(jié)點(diǎn)和子節(jié)點(diǎn)構(gòu)造的,記為節(jié)點(diǎn)(可以為葉子節(jié)點(diǎn)也可以為父節(jié)點(diǎn))TF-IDF向量第k維元素的值。分別比較和TF-IDF向量各個(gè)維度元素的大小,比如,因此;,因此;,因此;,因此。重復(fù)以上操作至構(gòu)造至根節(jié)點(diǎn)。圖1.4關(guān)鍵詞索引樹構(gòu)建數(shù)據(jù)擁有者為了把文件集合外包給云服務(wù)器,并且讓其他用戶能夠從中搜索到符合要求的文件,因此需要構(gòu)造一個(gè)索引樹結(jié)構(gòu),并且加密該索引樹結(jié)構(gòu)外包給云服務(wù)器來完成搜索操作。首先從每個(gè)文件中提取對(duì)應(yīng)的關(guān)鍵詞,并且分別計(jì)算每個(gè)關(guān)鍵詞和對(duì)應(yīng)文檔之間的相關(guān)程度,即TF-IDF,同時(shí)將每個(gè)關(guān)鍵詞TF-IDF值的向量形式作為文檔的索引。為了加快索引樹的搜索速度,REMKS方案還將相關(guān)程度最高的兩個(gè)文檔放在相鄰的位置。樹中的每個(gè)節(jié)點(diǎn)記為U,其由五個(gè)部分構(gòu)成,分別是節(jié)點(diǎn)的id值,左右子節(jié)點(diǎn),,所對(duì)應(yīng)文件的索引碼fid,以及向量,即。如果節(jié)點(diǎn)U為葉子節(jié)點(diǎn),為從所有文件中提取的各關(guān)鍵詞以及和該葉子節(jié)點(diǎn)相應(yīng)文件的TF-IDF值,fid的值為該文件的文件標(biāo)識(shí)符。否則每一維的值等于左右子節(jié)點(diǎn)每一維元素向量中中較大的值,且fid記為null。此外,還使用索引節(jié)點(diǎn)集INX(IndexNodeSet)來存儲(chǔ)葉子節(jié)點(diǎn)。索引樹可以用如下算法來構(gòu)造:算法1:關(guān)鍵詞搜索樹構(gòu)造算法輸入:文件集合,文檔的標(biāo)識(shí)符,以及關(guān)鍵詞向量。輸出:關(guān)鍵詞索引樹TStep1:將文件集合F中的每個(gè)文件都與索引樹中的葉子節(jié)點(diǎn)一一對(duì)應(yīng),其中葉子節(jié)點(diǎn)的id值可由id生成函數(shù)GenID來生成。因?yàn)樵摴?jié)點(diǎn)是葉子節(jié)點(diǎn),所以左右子節(jié)點(diǎn);存儲(chǔ)了從文件中提取的關(guān)鍵詞以及和該葉子節(jié)點(diǎn)相應(yīng)密文文件的TF-IDF值。最后將節(jié)點(diǎn)相關(guān)信息存儲(chǔ)到索引節(jié)點(diǎn)集合INX中。Step2:計(jì)算文件與文件的相關(guān)程度,當(dāng)有偶數(shù)個(gè)文件時(shí),每次從INX中取出兩個(gè)相關(guān)程度最大的文件節(jié)點(diǎn),如果以為子節(jié)點(diǎn),為它們構(gòu)造父節(jié)點(diǎn),由id生成函數(shù)GenID()生成;為這個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn),為這個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn);向量中的第i維為兩個(gè)子節(jié)點(diǎn)向量中第i維元素的較大值,即因?yàn)橹挥腥~子節(jié)點(diǎn)才能代表特定的文件,而父節(jié)點(diǎn)無法代表文件,因此fid=null。當(dāng)有奇數(shù)個(gè)文件時(shí),轉(zhuǎn)到Step3。Step3:當(dāng)有奇數(shù)個(gè)文件時(shí),即n為奇數(shù),每次從INX中選取兩個(gè)相關(guān)程度最高的文件所對(duì)應(yīng)的節(jié)點(diǎn),并為它們構(gòu)造父節(jié)點(diǎn),直到INX中只剩下最后三個(gè)節(jié)點(diǎn),之后再選取兩個(gè)相關(guān)程度最大的文件,為它們構(gòu)建父節(jié)點(diǎn),并將它們的父節(jié)點(diǎn)和INX中最后的那個(gè)節(jié)點(diǎn)構(gòu)造父節(jié)點(diǎn)。Step4:依據(jù)Step2,自下向上依次構(gòu)造父節(jié)點(diǎn)直到根節(jié)點(diǎn),并由此獲得一個(gè)關(guān)鍵詞索引樹T。1.2.3關(guān)鍵詞索引樹的搜索過程構(gòu)建關(guān)鍵詞索引樹能夠很大程度加快了查詢的速度,將查詢的時(shí)間復(fù)雜度優(yōu)化到了。我們將通過這一節(jié)詳細(xì)介紹在關(guān)鍵詞索引樹上進(jìn)行搜索的方法,并迅速找到最符合匹配條件的前k個(gè)文件。我們采用可剪枝的深度優(yōu)先搜索算法對(duì)索引樹進(jìn)行搜索,得到搜索結(jié)果,即最符合查詢條件的前k個(gè)文件,根據(jù)文件和關(guān)鍵詞相關(guān)分?jǐn)?shù)按降序排序[25]。由和fid兩部分構(gòu)成,表示文件與查詢關(guān)鍵詞之間的相關(guān)分?jǐn)?shù),其中fid表示文件的文件標(biāo)識(shí)符。算法2:關(guān)鍵詞的搜索樹搜索算法輸入:關(guān)鍵詞索引樹T,搜索令牌token輸出:前k個(gè)最相關(guān)的文檔集合RSTStep1:使用深度優(yōu)先搜索對(duì)索引樹進(jìn)行搜索。首先分別計(jì)算左右子節(jié)點(diǎn)與查詢的關(guān)鍵詞之間內(nèi)容相關(guān)分?jǐn)?shù)Score,并且記錄Score較大的節(jié)點(diǎn)的相關(guān)信息。如果該節(jié)點(diǎn)不是葉子節(jié)點(diǎn),那么遞歸向下一直搜索到葉子節(jié)點(diǎn),否則將節(jié)點(diǎn)信息存入到集合RST中。Step2:一直遞歸使用Step1的方法,直到集合RST中已經(jīng)存儲(chǔ)了k個(gè)葉子節(jié)點(diǎn)的信息為止,然后按照RST中的結(jié)果按降序進(jìn)行排序。Step3:繼續(xù)遞歸。如果RST中第k個(gè)節(jié)點(diǎn)的相關(guān)分?jǐn)?shù)大于子節(jié)點(diǎn)的相關(guān)分?jǐn)?shù),則將這個(gè)節(jié)點(diǎn)剪枝,也就是不搜索這個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的子樹,否則依次遞歸至葉子節(jié)點(diǎn),同時(shí)將集合RST中最后一個(gè)元素的節(jié)點(diǎn)信息作為新的葉子節(jié)點(diǎn)信息插入其中。Step4:此時(shí)最滿足搜索條件的k個(gè)文件與集合RST中的節(jié)點(diǎn)一一對(duì)應(yīng),同時(shí)將這些密文文件返回給數(shù)據(jù)使用者。1.3安全KNN方案安全KNN方案(Securek-NearestNeighborScheme)允許對(duì)加密數(shù)據(jù)集上k個(gè)連續(xù)的數(shù)據(jù)進(jìn)行高效計(jì)算,一般應(yīng)用于加密索引和查詢。本文在后續(xù)提到的PIPE方案則是基于安全KNN思想提出來的方案。下面定義一些參數(shù)。設(shè)表示安全參數(shù),該參數(shù)應(yīng)足夠長(zhǎng),以防止暴力攻擊(例如,128位)。給定向量v,它的第i個(gè)元素用v[i]表示。用符號(hào)“*”和“·”分別表示矩陣乘法和向量?jī)?nèi)積。用和分別表示M的逆矩陣和轉(zhuǎn)置矩陣。如下為KNN方案的構(gòu)造::將安全參數(shù)作為輸入產(chǎn)生一個(gè)私鑰,其中表示可逆矩陣,s是一個(gè)d維的二進(jìn)制向量。在向量s中,0的數(shù)量應(yīng)該和1的數(shù)量近似一樣,最大地保證隨機(jī)化:將一個(gè)索引向量分裂為兩個(gè)向量,分裂規(guī)則如下所示,對(duì)于i從1到d的范圍內(nèi)變化時(shí),如果s[i]=1,那么p[i]

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論