Abstract: Aiming at the problem that the Basic Sliding Window(BSW) algorithm can not determine the maximal block length in the field of data storage, a kind of data chunking algorithm based on the extremum characteristic of byte-fingerprints is presented. It constructs the interval within allowed maximal chunk length next to the previous chunk, and defines the function F for the field radius of byte-fingerprint’s extremum. By using the characteristics of the function F, it can determine the next block boundary in the maximum interval with the probability of 1. Experimental results prove that the algorithm can overcome the shortage that BSW window algorithm and some other block-based algorithm can not determine the length of the largest block. The complexity of the algorithm is O(n).

Key words: data chunking algorithm, Hash fingerprint, storage algorithm

摘要： 针对基于内容的数据分块算法中基本滑动窗口算法不能确定最大数据块的问题，提出一种基于字节指纹极值特征的数据分块算法。算法以上一个块边界点为起点构建最大块长区间，通过定义字节指纹极值域半径函数F并利用函数F值的分布特性，以概率1在允许的最大块长的区间内确定下一个块边界点。该算法克服了基本滑动窗口等分块算法不能确定最大分块长度的不足，其时间复杂度为O(n)。

关键词: 数据分块算法, 哈希指纹, 存储算法

CLC Number: 

• TP312