[發明專利]一種基于統一采樣的快速相似數據檢測方法

有效

• 申請號: 201910243356.0
• 申請日: 2019-03-28
• 公開（公告）號: CN110083743B
• 公開（公告）日: 2021-11-16
• 發明（設計）人: 夏文;王軒
• 申請（專利權）人: 哈爾濱工業大學（深圳）
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 王學強

1.一種基于統一采樣的快速相似數據檢測方法，其特征在于，包括以下步驟：

A、基于滑動窗口算法快速計算哈希集合；在步驟A中，基于快速滑動哈希算法，計算出得滑動指紋集{F₁,F₂,……,F_N}；

B、對計算得出的哈希集合進行快速統一采樣；步驟B中的快速統一采樣為：統一判斷步驟A計算出來的當前滑動窗口的指紋值fp_i的前X1個比特位或者是后X1個比特位或者是中間X1個比特位是否為X2，如果為X2，則進入采樣集合，X1、X2均為設定值；采樣得出新的哈希集合{Z₁,Z₂,……,Z_X}，該集合的成員數遠遠小于原始滑動指紋集大小N；

其中，

在步驟B后，進行以下過程：基于采樣后的哈希集合，再提取特征值和超級特征值用于相似性匹配查找；

還包括以下步驟：

C、對采樣后的哈希集合，進行M次線性變換，獲得M個新的集合，并基于計算最大值原則，每個集合提取出一個特征值；

D、對特征值進行超級特征值打包，并向已經存在的超級特征值索引庫里面進行查找匹配；

E、如果有一個超級特征值匹配，則認為數據塊相似，進一步差量壓縮編碼處理以及存儲；對于未匹配的數據塊，則將相應的數據塊存入存儲系統，同時將對應的超級特征值寫入超級特征值索引庫。

2.根據權利要求1所述的基于統一采樣的快速相似數據檢測方法，其特征在于：在步驟A中，快速滑動哈希算法為：通過一個32/64位的整形數數組放大數據字節內容，實現哈希散列的效果，同時滿足滑動哈希算法要求，即當前窗口的哈希值可以基于上個窗口哈希值快速算出。

3.根據權利要求2所述的基于統一采樣的快速相似數據檢測方法，其特征在于：快速滑動哈希算法的核心計算策略如下：fp_i＝(fp_i-1＜＜1)^G[b]，其中，G指一個預先算好的固定隨機數組，可以對每個字節映射到一個很大隨機數；fp_i-1就是當前滑動窗口的上一個窗口的指紋值；b就是當前滑動窗口的最后一個字節的內容。

4.根據權利要求1所述的基于統一采樣的快速相似數據檢測方法，其特征在于：X1設定為1或者2或者3或者4。

5.根據權利要求1所述的基于統一采樣的快速相似數據檢測方法，其特征在于：在步驟C中，每個集合提取出一個特征值，即最大值或者最小值，特征值的計算公式如下，

其中，特征值又稱相似性特征值，Feature_i指的就是相似性特征值，FastHash(W_j)表示滑動窗口W_j的FastHash指紋，m_i和a_i表示預定的隨機數；在這里數據塊的長度為N，所以該數據塊有N個滑動窗口，相似性特征值Feature_i就是在這N個滑動窗口的FastHash指紋中取哈希最大值，不同預定值m_i和a_i會產生不同相似性特征值；

在步驟D中，超級特征值的計算公式如下，

SuperFearture_k＝Hash(Feature₁,Feature₂,...)，

其中，SuperFeature_k指的是超級特征值。