1.2.2 可变大小数据块(基于文件内容的查找)

可变大小数据块的检测是基于文件内容的将文件分成大小不等的数据块，通常是利用Rabin指纹的方法计算出数据内容的指纹值。Rabin指纹是一种高效的指纹计算函数，利用hash函数的随机性，它对任意数据的计算结果表现出均匀分布。基于内容的数据块划分方法如下：

预先设定一对整数D，r(D>r)和一个滑动窗口的固定宽度l(实际中常用r=D-1)。对于一个序列S=S1,S2,……,Sn，当且仅当 窗口的边缘停在某一个k位置，也就是子序列W=S(k-l+1),S(k-l+2),……,Sk的指纹函数计算结果为h(W) mod D = r，则k位置有一个D-match。k位置也就是某个数据块的边界位置。

实际操作时，从文件头部开始，将固定大小(相互重叠)的滑动窗口中的数据作为Rabin 指纹的子序列，计算每个窗口位置的指纹。当满足指纹条件时，就将此时窗口所在位置的边界作为块的边界。重复这样一个过程，直到整个文件数据都被划分成数据块。接下来再用hash 函数(MD5 或者SHA) 计算出每个划分的数据块hash 值，并将它们管理起来存放在hash 函数值库中。有新来的文件时，首先按照上述方法划分成数据块，再将每个数据块的hash 值与已存储的数据块hash 值进行对比，如果检测到相同的hash 值，则不存储其代表的数据块，否则存储这个新数据块并更新hash 值库信息。如图所示：

利用基于文件内容的划分方法，无论是插入还是删除一小部分字节，都只会影响到一到两个块，其余的块保持不变，所以对于只相差几个字节的数据块可以检测出更多的冗余。

经典文献

u A Framework for Analyzing and Improving Content-Based Chunking Algorithms

K.Eshghi and H. K. Tang. Technical Report HPL-2005-30(R.l), Hewlett Packard Laboraties, Palo Alto, 2005.

上面描述的数据块划分方法容易产生一些问题。由于hash函数的随机性，极端情况就是某文件始终找不到D-match，造成数据块过大(可能是一个 文件只有一个数据块);另一个极端情况就是每个字节都是D-match，这样数据块过小(只有1字节的长度)。针对这些可能出现的问题，本文提出了一些改 进算法，并且给出了如何评估这些算法好坏的数学公式。主要的改进算法如下：