摘要
针对基于内容的数据分块算法中基本滑动窗口算法不能确定最大数据块的问题,提出一种基于字节指纹极值特征的数据分块算法。算法以上一个块边界点为起点构建最大块长区间,通过定义字节指纹极值域半径函数F并利用函数F值的分布特性,以概率1在允许的最大块长的区间内确定下一个块边界点。该算法克服了基本滑动窗口等分块算法不能确定最大分块长度的不足,其时间复杂度为O(n)。
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).
出处
《计算机工程》
CAS
CSCD
北大核心
2010年第8期69-70,73,共3页
Computer Engineering
关键词
数据分块算法
哈希指纹
存储算法
data chunking algorithm
Hash fingerprint
storage algorithm