———————————————收稿日期：年-月-日*投稿时不填写此项*；最终修改稿收到日期：年-月-日 *投稿时不填写此项*. 基金项目：中国农业大学研究生科研创新专项基金（2013YJ008）基于数据位图的滑动分块算法邓雪峰,孙瑞志,张永瀚,聂娟(中国农业大学农业部农业信息获取技术重点实验室 北京100083) (北京农学院计算机与信息工程学院 北京 100083) (dxf75@)Sliding blocking algorithm based on data bitmapDeng Xuefeng, Sun Ruizhi, Zhang Yonghan, Nie Juan(Key laboratory of Agricultural information acquisition technology （Beijing ）,Ministry of Agriculture P.R.China, China Agricultural University, Beijing, 100083)(College of Computer and Information Engineering in Beijing University of Agriculture, Beijing, 102206 China)Abstract During similar data synchronization and storage, data blocking is an important step to detect duplication of data. Only after effective data blocking can you find difference between data accurately. This paper first summarizes and analyzes the methods of data blocking, then re-organize data files in the form similar to bitmap based on the sliding blocking algorithm. After that we read data bitmap by column to form a new data chunk and compute fingerprint information of the column. To improve its ability to locate difference in data, fingerprint of column serve as supplement for sliding bolcking algorithm to acquire more accurate information of data difference. Experimental results show that this method is better than sliding blocking algorithm in data duplication detection under the same conditions.Key words Sliding blocking algorithm; Duplicate data detection; data bitmap; data difference; datasynchronization摘 要 网络中相似的数据文件进行同步与存储的过程中，对数据进行分块，是检测数据重复的重要步骤之一，在有效的对数据分块的基础上才能更准确的定位数据间的差异部分。
本文就数据分块方法予以分析总结，在滑动分块算法的基础上，重新将数据文件组织成类似位图的排列形式，对数据位图以列向读取数据信息，形成新的数据分块，并计算列向读取数据的分块指纹信息，以列向数据指纹为补充校正滑动分块算法定位差异数据的能力的不足之处，从而获得更精确的数据差异信息。
经实验证明，本方法在同源文件的数据重复检测中效果好于相同条件下的滑动分块方法。
关键词 滑动分块算法；重复数据检测；数据位图；数据差异；数据同步 中图法分类号 TP31；TP39 随着大数据时代的到来，大量的数据将通过网络进行更新与存储。
在这些数据文件中存在着大量的同源或类似文件。
对同源的数据文件进行同步更新的过程中如何降低网络的占用；对内容大部分相同的文件如何利用更少的存储空间进行存储一直是计算机领域研究的热点问题之一。
同源或内容相近的数据文件进行网络同步过程中，经常采用基于差异的数据传输方法。
这种方法是低带宽网络中文件同步的高效方案之一，利用这个技术可以减少网络流量的开销，同时也能提升数据同步更新的速度。
利用这种技术为核心定制了相当多的应用系统[1]。
该技术在文件的传输过程中，非常重要的一个处理过程就是将数据分块，数据分块的方法是提升查找差异数据精确度的重要手段。
同源或内容相近的文件存储采用的去重技术，也是一个重要的研究方向。
存储类似数据文件的方案中，对相同内容的数据去重处理时最重要的步骤也是将数据进行分块，这种数据分块方法不同于基于差异传输数据时的数据分块方案，一般是采用基于内容的数据分块技术。
但基于差异的数据传输中用到的核心分块方案，固定数据块大小的滑动分块技术同样也可以应用于该领域。
因此，数据分块技术是对同源或内容相近的数据文件进行同步更新与去重存储的必要技术。
本文在分析了各种数据分块技术的基础上，以基于差异的数据传输模型为应用场景，提出了一种基于数据位图的分块方案，这个方案提升了查询内容相近数据文件中相同数据内容的能力，应用于差异数据传输方案中将在不提升数据指纹交换次数的情况下直接达到多轮交换数据指纹的效果，且此方案也可以用于数据存储领域中，用于更精确的检测文件重复信息。
1相关研究数据分块技术把数据文件划分为较小的数据块，通过计算这些小数据块的哈希值，将其作为数据指纹，对比不同的内容相似的数据文件中小数据块的指纹信息，从而确定不同的内容相近的数据文件中的重复数据块。
利用检测出的结果可以对数据进行基于差异的传输与去重存储等操作，这样可以只传输或存储数据文件中差异部分的数据，减少网络带宽与存储空间的占用。
对数据文件进行分块的方法主要有固定分块技术(Fixed-Sized Partition, FSP)，可变分块技术(Variable-Sized Partition, VSP)和滑动块技术(Sliding Block)[2][3]。
固定分块技术（FSP）是把数据流按固定长度的字节数进行切割，然后对固定长度的数据分块计算其数据指纹的方法。
可变分块技术（VSP）主要代表是基于内容可变长度分块(Content-Defined Chunking, CDC)算法。
CDC算法[4]利用一个固定的滑动窗口为边界切分数据文件的数据，形成可变长的数据分块，滑动窗口顺序的从数据文件的起始位置部向后逐一字节滑动，当滑动窗口的hash值（CDC算法中采用的是Rabin[5]指纹）与预设的值匹配时，就产生一个分块。
这个数据块的长度被指定在一个区间范围内获取。
滑动块技术(Sliding Block,SB)是在文献[6]中被提出的，在文中提出了一种用于同步远程内容相近的数据文件的同步算法，即Rsync算法，在Rsync算法中提出了一种对划分的数据块进行滑动分块的数据分块技术。
这种数据分块方法以固定数据分块技术为基础，利用滑动块技术更准确的获得较小的数据分块的位置信息，从而在一定程度上规避了在内容相似文件中对插入、删除等操作对固定分块技术查找重复数据影响较大的问题。
在数据分块的分析中，利用数据分块技术更精确的获取差异数据信息是一个研究的重点内容。
在数据文件同步方面对数据分块技术的改进主要集中于多轮(多次交换指纹信息)同步算法[7]~[10]，算法对数据分块采用逐渐减小数据块的粒度的方法，更精确的获取差异数据的在数据文件中的位置，减少传输差异数据的带宽占用。
其中固定分块技术与基于内容的可变长分块技术都被利用到其中，用于缩小数据分块粒度，例如文献[7]中将基于内容的分块方法与滑动分块技术结合，形成两轮数据指纹交换，从而确定同源文件的差异信息。
文献[11]中对于文件信息交换的次数有一个界定，这个结论说明不可以无限次的交换文件的指纹信息，一般来说多轮同步算法在实际应用中由于信息的交换在网络上进行，出于对系统稳定性的考虑以及具体的节省带宽的效果两方面原因，在实际中应用还比较少。
2数据分块技术分析本节对FSP、VSP及以Rsync算法为原型的SB等几种对数据进行分块的方法进行分析，总结利用各种数据分块技术对数据文件分割产生的问题。
FSP分块方法中新文件示意图如图1所示的排列形式，假设新文件为一个顺序排列的字符组成，按数据流顺序排列成图中所示的字符串，固定分块技术将文件按固定的分块方式拆分成数据块，而旧文件以同样的长度拆分数据，图1中，假设在数据中，分块长度为图中示意的间隔长度，新文件分块为ABCD 、EFGH 、IJKL ……，不妨设待更新的旧文件与新文件有如下差异，在第二块数据由EF 与GH 间插入新的数据23、在第四块在第9块7890中删除0。
利用FSP 分块的方法，在图1中所示的情况下，第二块数据由于插入引起数据的改动直接影响到其后的分块，待更新的旧文件中只有第1块数据块可以在新文件中找到对应的相同数据分块，新文件中第2块数据块其后的数据块均无法在图1 FSP 数据分块方法示意图固定分块的方法对于文件的更新，尤其是插入或删除操作是非常敏感的，在数据文件某个位置发生改变后，其后的所有的分块内容都将受到影响，从而使相似文件的匹配度降低。
因此在实际应用中利用这种技术实现的系统不常见。
变方式同前文中FSP 数据分块方案中的数据变动情况，假设在示意图中（E ，F ）、（K ，L ）、（P ，Q ）、（U ，V ）、（Z ，1）、（6，7）、（6，5）、（1，Z ）、（U ，T ）、（Q ，P ）、（L ，K ）等处获得的数据内容指纹相同。
分块形式如图2所示。
图2 VSP 数据分块方法示意图在VSP 分块方法分割数据时，可以以内容区别分块的边界，这种方案可以把仅被改动过的分块区分出来，并且如果不是修改了边界的内容，可以达到仅识别修改后的区块的目的，检测精确度较固定分块技术有极大的提升，也一定程度上消除了插入及删除的影响。
进行数据分块对比结果的示意图如图3所示，由于采用了滑动分块的方法查找待更新的旧文件中的区块，可以将固定数据分块的缺点得以消除，在对插入与删除的情况中，利用区块窗口滑动的方法可以消除修改部分对后续分块分割的影响，提升了固定分块技术的现实可用性。