[發明專利]一種索引建立方法及裝置

有效

• 申請號: 201711069369.8
• 申請日: 2017-11-03
• 公開（公告）號: CN107784110B
• 公開（公告）日: 2020-07-03
• 發明（設計）人: 謝永恒;張俠;火一莽;萬月亮
• 申請（專利權）人: 北京銳安科技有限公司
• 主分類號: G06F16/31
• 分類號: G06F16/31
• 代理公司: 北京品源專利代理有限公司 11332
• 代理人: 孟金喆

本發明實施例公開了一種索引建立方法及裝置，所述方法包括：提取目標文本的特征詞；對所述特征詞進行排序得到特征字符串；對所述特征字符串應用MinHash算法，得到所述目標文本對應的哈希值；查找映射緩存池中是否存在與所述哈希值匹配的索引映射桶，若存在，則在所述索引映射桶中建立所述哈希值與所述目標文本之間的索引；若所述映射緩存池中不存在與所述哈希值匹配的索引映射桶，建立與所述哈希值匹配的索引映射桶，并建立所述哈希值與所述目標文本之間的索引。本發明實施例提供的索引建立方法減少了索引存儲量，通過將相似文本的索引建立在同一個索引映射桶中，實現了相似文本的分類，提高了相似文本的檢索速度。

技術領域

本發明實施例涉及信息索引以及查詢領域，尤其涉及一種索引建立方法及裝置。

背景技術

近年來，隨著互聯網技術的迅速發展和普及，很多情況下我需要從海量數據中快速而準確地找到我們想要的數據，這一過程稱為相似性搜索。

隨著網絡數據的急劇增加，搜索速度已經成為相似性搜索的一大瓶頸，因此，如何設計一個快速有效的索引結構，成為了大數據時代下相似性搜索的迫切需求。目前常用的索引技術一種為基于樹形結構的索引，典型的有KD樹。樹形結構的索引采用了子空間劃分的結構設計，通過將對象數據劃分到若干個子空間中，每個子空間中包含相似的數據，在進行搜索時，只在某個子空間范圍內進行搜索即可，在低維特征空間中有效提高了檢索速度。但是當搜索對象的特征維數增大時，樹形結構索引的效率大大降低，其效率與線性查找的時間復雜度相比幾乎沒有提高。另一種索引技術為基于傳統的hash函數索引，例如md5，其原理為將原始內容盡量均勻地隨機映射為一個簽名，因此，即使原始內容只相差一個字節，則所產生的簽名也很可能差別極大。若兩個簽名相等，則說明原始內容在一定概率下是相等的，如果不相等，除了說明原始內容不相等外，不再提供任何信息。因此基于傳統的hash函數的索引技術不能通過比較簽名的相似度來確定原始內容之間的相似度，具備一定的局限性。

發明內容

本發明實施例提供了一種索引建立方法及裝置，有效降低了索引數據的存儲量，進而提高了檢索速度。

第一方面，本發明實施例提供了一種索引建立方法，該方法包括：

提取目標文本的特征詞；

對所述特征詞進行排序得到特征字符串；

對所述特征字符串應用MinHash算法，得到所述目標文本對應的哈希值；

查找映射緩存池中是否存在與所述哈希值匹配的索引映射桶，若存在，則在所述索引映射桶中建立所述哈希值與所述目標文本之間的索引；

若所述映射緩存池中不存在與所述哈希值匹配的索引映射桶，建立與所述哈希值匹配的索引映射桶，并建立所述哈希值與所述目標文本之間的索引。

進一步地，在所述索引映射桶中建立所述哈希值與所述目標文本之間的索引，包括：

若所述索引映射桶中不存在與所述哈希值相同的索引哈希值，則將所述哈希值存入所述索引映射桶中，并建立所述哈希值與所述目標文本之間的索引；

若所述索引映射桶中已經存在與所述哈希值相同的索引哈希值，則不對所述哈希值進行再次保存，直接建立所述索引哈希值與所述目標文本之間的索引。

進一步地，所述方法還包括：

若所述映射緩存池中存在與所述哈希值匹配的索引映射桶，則將與所述哈希值對應的文本數據作為與所述目標文本相似的文本數據進行推薦。

進一步地，所述方法還包括：

隨機確定N個哈希函數；

基于所述N個哈希函數對目標文本的特征字符串分別進行哈希運算，得到N個哈希值；