[發明專利]一種面向可變長數據塊的快速檢索方法

有效

• 申請號: 202110424974.2
• 申請日: 2021-04-20
• 公開（公告）號: CN113495901B
• 公開（公告）日: 2023-10-13
• 發明（設計）人: 徐振楠;呂鑫;吳濤;高晟凱
• 申請（專利權）人: 河海大學;華能瀾滄江水電股份有限公司;網聯清算有限公司
• 主分類號: G06F16/2453
• 分類號: G06F16/2453;G06F16/22;G06F3/06
• 代理公司: 南京縱橫知識產權代理有限公司 32224
• 代理人: 凌雋宇

1.一種面向可變長數據塊的快速檢索方法，其特征在于，包括以下步驟：

步驟S1、讀取一個待檢索的可變長數據塊組；

步驟S2、提取數據塊組中的數據塊的長度及部分位置字節值；

步驟S3、將當前數據塊長度映射到[0,255]區間上，并以映射后的值作為索引樹的第一個子節點，構建索引樹；

步驟S4、計算數據塊指紋，再比對指紋，將數據塊信息添加為當前節點的子節點，返回步驟S1。

2.根據權利要求1所述的一種面向可變長數據塊的快速檢索方法，其特征在于，

所述步驟S2，具體為：

步驟S2.1、輸入一個所述可變長數據塊組的數據塊；

步驟S2.2、若當前輸入為空，則輸出判斷結果并終止檢索，否則提取當前數據塊的長度L以及部分位置的字節值A0、A1、A2、…。

3.根據權利要求1所述的一種面向可變長數據塊的快速檢索方法，其特征在于，所述步驟S3，具體為：

步驟S3.1、計算K＝min(L,65536)mod 256，其中，K表示將當前數據塊長度映射到[0,255]區間上的值，L表示數據塊長度，min(L,65536)表示取L與65536中較小值，用于將長度超過64KB的數據塊劃分為同一子節點，mod表示取模運算；

步驟S3.2、依次以K，A0，A1，A2，…為鍵，構建索引樹S-K-A0-A1-A2-…，其中，S表示索引樹的根節點。

4.根據權利要求1所述的一種面向可變長數據塊的快速檢索方法，其特征在于，所述步驟S4，具體為：

步驟S4.1、若當前索引下無其他數據塊，則當前檢測的數據塊為唯一塊，返回步驟S2；否則，進入步驟S4.2；

步驟S4.2、分別計算當前索引下未計算指紋的數據塊的指紋和當前檢測的數據塊的指紋；

步驟S4.3、將當前檢測的數據塊指紋與索引下其他數據塊指紋比對，若存在，則當前檢測的數據塊為重復塊，否則為非重復塊；

步驟S4.4、將數據塊信息添加為當前節點的子節點，返回步驟S2。

5.根據權利要求1所述的一種面向可變長數據塊的快速檢索方法，其特征在于，所述數據塊指紋為數據塊的安全哈希函數值。

6.根據權利要求1所述的一種面向可變長數據塊的快速檢索方法，其特征在于，所述提取的部分位置字節值定義為第1個字節值、最后1個字節值、第[L/2]個字節值、第2ⁿ個字節值，其中，L表示數據塊長度，n為自然數且2ⁿ≤L。