[發明專利]為基于散列的消重進行子塊分割的方法和系統

有效

• 申請號: 201310275022.4
• 申請日: 2013-07-03
• 公開（公告）號: CN103530310A
• 公開（公告）日: 2014-01-22
• 發明（設計）人: L·阿羅諾維奇;M·海爾什
• 申請（專利權）人: 國際商業機器公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 中國國際貿易促進委員會專利商標事務所 11038
• 代理人: 高青

1.一種用于在計算環境中由處理器設備對基于散列的消重進行子塊分割的方法，該方法包括：

定義子塊的最小尺寸和最大尺寸；

對于子塊的每個邊界開始位置，通過使用多個搜索標準來測試在搜索期間生成的多個散列值，在子塊的最小尺寸之后開始對于子塊的邊界位置的搜索，其中，所述多個散列值至少包括各個散列值和從基礎散列值的集合中導出的導出散列值；

如果所述多個散列值中的一個滿足所述多個搜索標準中的一個，則把所述多個散列值中的所述一個的位置聲明為所述子塊的邊界位置；以及

如果在滿足多個搜索標準中的一個之前到達子塊的最大尺寸，則把基于所述多個搜索標準中的另外一個搜索標準選擇的所述多個散列值中的另外一個散列值的位置聲明為所述子塊的邊界位置。

2.如權利要求1所述的方法，進一步在所述多個散列值中包括最小散列值、最大散列值、最后計算的一個散列值和最后計算的k個散列值。

3.如權利要求1所述的方法，進一步包括：把邊界開始位置識別為下列之一：塊的開始、最后選擇的邊界位置、以及跟在最后識別的邊界結束位置之后的一個或多個字節。

4.如權利要求1所述的方法，其中，所述多個搜索標準中的一個包括第一種類型搜索標準和第二種類型搜索標準中的一個，以及所述多個搜索標準中的另外一個搜索標準是第三種類型搜索標準。

5.如權利要求4所述的方法，進一步包括：如果最后計算的一個散列值的預定義位置的n位等于第m個預定義的不同位模式中的一個，則滿足第一種類型搜索標準。

6.如權利要求4所述的方法，進一步包括通過下列至少之一滿足第二種類型搜索標準：

如果通過對最后計算的k個散列值應用XOR操作而計算的值的預定位置的n位等于第m個預定義的不同位模式中的一個，以及

應用組合最后計算的k個散列值的值并且產生其統計分布與被組合的多個散列值的統計分布相似的備選值的多個操作中的一個。

7.如權利要求4所述的方法，進一步包括通過選擇子塊的邊界位置來滿足第三種類型搜索標準，其中選擇子塊的邊界位置是通過選擇通過以下至少一個在搜索期間計算的多個散列值中的一個：

選擇最大散列值，

選擇最小散列值，以及

選擇第n大或小散列值。

8.如權利要求7所述的方法，進一步包括提供被考慮為選擇方法的輸入的多個散列值的預定義位置的范圍，其中，所述預定義位置的范圍是用于預定義位置的整個可用范圍的子集。

9.如權利要求4所述的方法，進一步包括：如果所述多個搜索標準中的一個未被所述多個散列值中的一個滿足，則執行以下至少一個：

把所述多個散列值中的一個的當前位置遞增至少一個字節，以及

如果在滿足所述多個搜索標準中的一個之前沒有到達子塊的最大尺寸，則計算所述多個散列值中的下一個，以利用所述多個搜索標準中的所述一個進行測試。

10.如權利要求1所述的方法，進一步包括使用滾動散列函數來計算在每個字節位置的各個散列值。

11.一種用于在計算環境中為基于散列的消重進行子塊分割的系統，包括：

處理器設備，可在所述計算環境中操作，其中所述至少一個處理器設備適于：

定義子塊的最小尺寸和最大尺寸；

對于子塊的每個邊界開始位置，通過使用多個搜索標準來測試在搜索期間生成的多個散列值，在所述子塊的最小尺寸之后開始對所述子塊的邊界位置的搜索，其中，所述多個散列值至少包括各個散列值和從基礎散列值的集合中導出的導出散列值；

如果所述多個散列值中的一個滿足所述多個搜索標準中的一個，則把所述多個散列值中的所述一個的位置聲明為所述子塊的邊界位置；以及

如果在滿足多個搜索標準中的一個之前到達所述子塊的最大尺寸，則把基于所述多個搜索標準中的另外一個搜索標準選擇的所述多個散列值中的另外一個散列值的位置聲明為所述子塊的邊界位置。

12.如權利要求11所述的系統，其中，所述處理器設備進一步適于在所述多個散列值中包括最小散列值、最大散列值、最后計算的一個散列值和最后計算的k個散列值。