基于改进CDC的实验原始记录匹配算法

针对当前实验室检测报告的生成过程存在时间长和易出现偶然性差错等问题,提出基于栅栏因子的通用实验原始记录文件自动抓取技术.先通过计算文件整体hash值准确过滤当日已读取文件,再使用改进的内容可变长度分块(content-defined chunking,CDC)算法进行文本分块.该CDC算法改进之处主要体现在:设定滑动窗口下一单位为行与行间距之和的高度以及滑动窗口内字节大小的范围.待文本分块结束后,使用基于数据块索引的字符串匹配算法完成匹配.该字符串匹配算法结合数据块索引表构建模式串与数据块的映射关系,之后由模式串Pn通过数据块索引表快速匹配到相应数据块.使用海关实验室的实验原始记录文件进行测试,实验证明,该算法的内存占用量少且分块吞吐量更大.

基于对象的OpenXML复合文件去重方法研究

现有的重复数据删除技术大部分是基于变长分块(content defined chunking,CDC)算法的,不考虑不同文件类型的内容特征.这种方法以一种随机的方式确定分块边界并应用于所有文件类型,已经证明其非常适合于文本和简单内容,而不适合非结构化数据构成的复合文件.分析了OpenXML标准的复合文件属性,给出了对象提取的基本方法,并提出基于对象分布和对象结构的去重粒度确定算法.目的是对于非结构化数据构成的复合文件,有效地检测不同文件中和同一文件不同位置的相同对象,在文件物理布局改变时也能够有效去重.通过对典型的非结构化数据集合的模拟实验表明,在综合情况下,对象重复数据删除比CDC方法提高了10%左右的非结构化数据的去重率.

内容分块算法中预期分块长度对重复数据删除率的影响

针对基于内容分块重复数据删除方法缺少能够定量分析预期分块长度与重复数据删除率之间关系的数学模型,导致难以通过调整预期分块长度优化重复数据删除率的问题,提出了一种基于Logistic函数的数学模型。在大量真实数据测观察基础上,提出了通过Logistic函数描述非重复数据的"S"形变化趋势,解决了该数据难以从理论上推导、建模的问题,证明了基于内容分块过程服从二项分布,并从理论上推导出了元数据大小模型。基于上述两种数据模型,通过数学运算最终推导得到重复数据删除率模型,并利用收集到的3组真实数据集对模型进行了实验验证。实验结果表明:反映数学模型拟合优度的R2值在0.9以上,说明该模型能够准确地反映出预期分块长度与重复数据删除率之间的数学关系。该模型为进一步研究如何通过调整预期分块长度使重复数据删除率最优化提供了理论基础。

基于极值点分块的重复数据检测算法

重复数据检测技术能够大幅降低数据中心的存储量,节省网络带宽,减少建设和运维成本。为了克服基于内容分块(CDC)方法容易出现超长块的缺点,文章提出了基于极值点分块(EDC)的重复数据检测算法。EDC算法先计算出所有右边界在数据块上下限范围内的滑动窗口中数据的指纹,找出最后一个指纹极值,所对应的滑动窗口结束位置作为数据块的分界点,再计算该数据块的哈希值并判断是否重复块。实验结果表明,EDC算法的重复数据检测率、磁盘利用率分别是CDC算法的1.48倍和1.12倍,改进效果显著。

Rabin指纹算法在重复数据检测中的应用研究

Rabin指纹算法计算效率高、随机性好,可将数据更改对连续指纹序列的影响限制在局部范围内,广泛应用于重复数据检测领域。分析了Rabin指纹在有限域GF(2n)上的运算原理,得出滑动窗口移动时定长字符序列的数字指纹快速计算公式。用伪代码描述了Rabin指纹算法在重复数据检测中的应用,并用VC++语言进行了算法实现,在普通计算机上提取Word文档、程序源代码和BMP图像等三类文件作为测试数据集,测试结果表明算法是有效的。

一种用于重复数据删除的非对称最大值分块算法研究

分块是一种将文件划分成更小文件的过程,该方法被广泛应用在重复数据删除系统中。针对传统的基于内容分块(CDC)中面临的高额计算开销问题,提出了一种称为非对称最大值的分块算法(CAAM)。采用字节值代替哈希值来声明切点,利用固定大小窗口和可变大小窗口来查找作为切点的最大值,并且允许在保留内容定义分块(CDC)属性的同时进行较少的计算开销。最后将CAAM与现有的基于散列和无哈希的分块算法进行了比较,实验结果表明,CAAM算法比其他算法具有更低的计算开销和更高的分块吞吐量。

基于极值点自适应的快速文件同步方法

Rsync差异同步方法是一种高效的文件同步方法,但是在差异数据分布离散和同步网络速度较快等情况下,可能会出现其同步效率低于完全同步的问题。为了避免这种问题,提出了一种基于极值点分块自适应的快速文件同步方法。该方法利用数据极值点进行基于内容的可变长分块,快速估算同步源端和同步目的端在差异数据分布不同时的动态数据差异度,根据计算出的差异度和当前同步网络速度的定量值,自适应地选择采用更优的同步方法。实验结果表明,在差异数据分布不同和网络同步速率不同的情况下,本文的方法能有效地选择更优的同步方法,达到减少同步时间,提高同步效率的目的。

一种基于预分块和滑动窗口的重复数据消除方法

针对现有重复数据消除方法中提高压缩比和降低元数据开销之间的矛盾,提出了一种基于预分块和滑动窗口的重复数据消除方法并建立了性能分析通用模型.该方法首先对数据对象进行基于内容的预分块,再对数据变动区域和非变动区域采用不同的分块策略,从而在分块大小预期值较大时,仍能获得较高的压缩比并降低了元数据开销.真实数据集上的实验结果表明,该方法的平均压缩比高于现有最优值,而平均时间开销显著降低.