[發明專利]基于局部敏感哈希的中文多關鍵詞模糊排序密文搜索方法

有效

• 申請號: 201710387493.2
• 申請日: 2017-05-26
• 公開（公告）號: CN107220343B
• 公開（公告）日: 2020-09-01
• 發明（設計）人: 楊旸;劉佳;郭文忠;葉少珍;董晨
• 申請（專利權）人: 福州大學
• 主分類號: G06F16/31
• 分類號: G06F16/31;G06F16/33;G06F21/62
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 蔡學俊

本發明涉及一種基于局部敏感哈希的中文多關鍵詞模糊排序密文搜索方法，將中文關鍵詞轉換成對應的拼音串后，基于聲韻母和音調、unigram對拼音串分割；設計了三種中文關鍵詞向量生成算法，將拼音串映射成關鍵詞向量。并且，利用局部敏感哈希的特性和布隆過濾器來實現關鍵詞的模糊匹配。本發明采用一篇文檔對應一個布隆過濾器作為文檔的加密索引，當加入新文檔（或刪除舊文檔）時，無需更改原數據集的加密索引，只需構建新文檔的加密索引（或刪除舊文檔的加密索引），就可實現文檔的動態更新。為了提高排序結果的精確性，本發明引入了域加權評分，將關鍵詞向量間的歐氏距離、詞頻權重和域加權評分結合，實現更為精確的三因子排序，返回更加滿足用戶需求的文檔。

技術領域

本發明涉及一種基于局部敏感哈希的中文多關鍵詞模糊排序密文搜索方法

背景技術

隨著云計算技術的飛速發展，敏感數據越來越多的存儲到云中，如電子郵件、個人健康記錄、私人視頻和照片、公司財務數據和政府文件等。云服務器提供了高質量的數據存儲服務，將數據存儲到云中，可以減少用戶的數據存儲和維護開銷。但是數據擁有者和云服務器不在同一個信任域中會使外包數據處于危險之中，為了保護用戶的隱私安全，將數據加密后再存儲到云服務器是一種常見的解決方法。然而數據經過加密后不再具有原有的特性，當用戶需要某些數據時，無法直接在密文中分辨出所需要的數據，在數據量很小的情況下，可以將所有的密文數據下載至本地，解密后在明文中搜索自己想要的數據。然而隨著云端數據規模的急劇增長，這種浪費了大量時間開銷與帶寬功耗的做法顯然已經不能滿足用戶的實際需求，因此，如何在大量密文中搜索到需要的文檔成為了一個難題。

Song等率先開始進行可搜索加密技術的研究，為解決密文檢索的問題提供了思路。Chang等為每篇文檔創建索引，搜索時只需對加密的文檔索引進行搜索，提高了搜索效率。Wang等提出了單關鍵詞排序的搜索方案，主要通過計算文檔的tf-idf(詞頻-逆文檔頻率)值并經過保序加密后，對保序加密后的相關度分數進行排序，返回top-k篇文檔給用戶。Cao等提出了多關鍵詞排序可搜索加密方案，引入了向量空間模型和安全KNN(secure k-nearest neighbor)方法，通過矩陣對索引向量進行加密，計算索引向量和搜索向量的內積相似度來實現多關鍵詞的排序搜索。但是這些方案只支持精確關鍵詞搜索，用戶輸入的關鍵詞必須與預定義的關鍵詞完全匹配，才能返回搜索結果，這使得搜索方案具有較大局限性。因此，Li等提出模糊關鍵詞可搜索加密方案，用通配符的方法構造關鍵詞模糊集合，用戶在輸入的搜索關鍵詞出現拼寫錯誤或格式不匹配的情況時，也能以較大的概率找到相關文檔，極大改善了用戶的搜索體驗。Li等提出了節省存儲空間的模糊搜索方案，通過克(gram)來構造模糊集。Wang等利用通配符和索引樹，實現了高效的模糊搜索方案。Chuah等為了提高搜索效率，實現了基于BedTree的多關鍵詞模糊搜索方案。

但是以上的方案都是針對英文關鍵詞實現模糊搜索，由于漢字是典型的非字母語言，詞語的搭配靈活多樣，因此以上的方案并不適用于中文關鍵詞的模糊搜索。Cao等提出了一種基于漢語拼音的明文模糊搜索方案，但是并不能實現密文上的搜索。Chen等使用基于拼音的漢字串相似度衡量方案，實現了中文關鍵詞的密文模糊搜索方案。

然而以上的模糊搜索方案都要預先構建模糊集，這些模糊集合將占用云服務器大量的存儲空間。例如，在基于通配符的模糊集構造方法中，隨著編輯距離的增加，模糊集合的大小會呈指數增長，因此構造模糊集合會耗費大量的計算和存儲開銷。Yang等基于simhash的降維思想，將關鍵詞做n-gram處理得到simhash指紋來實現模糊搜索。Wang等和Fu等將局部敏感哈希(Locality-sensitive hashing，LSH)和安全KNN方法(secure k-nearest neighbor)結合，實現了一種新的多關鍵詞模糊搜索方案。以上方案雖然無需構建關鍵詞模糊集合，但是同樣是針對英文的模糊搜索，并不能實現中文模糊搜索。