Winnowing指纹串匹配的重复数据删除算法
来源：计算机应用杂志2018年第3期北京时间：
作者：王青松, 葛慧
单位：辽宁大学 信息学院, 沈阳 110036
摘要：针对可变长度分块（CDC）的重复数据删除算法的分块大小难以控制、指纹计算对比开销大、需要预先设置参数问题，提出Winnowing指纹串匹配的重复数据删除算法（DWFM）。首先，在数据分块前引入分块大小预测模型，较准确地根据应用场景计算出合适的分块大小；然后，在计算指纹时采用ASCⅡ/Unicode编码方式作为数据块指纹；最后，在确定分块边界时，提出指纹串匹配的分块算法，不需要预先设置参数，使得指纹计算和对比开销减少。在多种数据集上的实验结果表明，相比固定长度分块（FSP）和CDC算法，DWFM在数据的重删率上提升10%左右，在指纹计算和对比开销方面减少了18%左右。因此，DWFM的分块大小和边界更加符合数据特性，减少了参数设置对重复数据删除算法性能的影响，在处理不同类型的数据时，可以有效地消除更多的重复数据。
关键词：重复数据删除,数据分块,指纹串匹配,Winnowing,分块预测
基金资助：国家自然科学基金资助项目（61502215）。
