基于字节指纹极值特征的数据分块算法  

Data Chunking Algorithm Based on Byte-fingerprint Extremum Characteristics

作　　者：孙继忠[1] 马永强[1] 李玉华[1] 

机构地区：[1]西南交通大学信息科学与技术学院,成都610031

出　　处：《计算机工程》2010年第8期69-70,73,共3页Computer Engineering

摘　　要：针对基于内容的数据分块算法中基本滑动窗口算法不能确定最大数据块的问题,提出一种基于字节指纹极值特征的数据分块算法。算法以上一个块边界点为起点构建最大块长区间,通过定义字节指纹极值域半径函数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）.

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

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]