基于双布鲁姆过滤器的数据排重技术

席晔文，杨金民

湖南大学 信息科学与工程学院，长沙 410082

基于双布鲁姆过滤器的数据排重技术

席晔文，杨金民

湖南大学 信息科学与工程学院，长沙 410082

1 引言

随着计算机技术的飞速发展，数字信息量呈爆炸式的增长，占用的储存空间越来越多。有研究指出，一般系统中数据有60%是冗余的，这个数据还会随着系统运行时间的推移而继续增长。由此，重复数据删除技术[1]得到了大量的关注：它使系统数据的存储空间暴增问题得以缓解，对系统中已存在的资源进行最大化利用；在网络数据传输前将重复数据查找出来，减少对网络带宽的占用。

如何简洁地表示海量的数据信息，如何快速地在海量数据中快速查找重复数据，是排重技术应用于大规模数据管理的关键。

现在流行的排重技术有Message Digest Algorithm MD5（MD5码）[2]排重法，MD5码是对任意长度的明文输入，通过函数计算，得出的只属于该输入的独一无二的指纹值，所以可以通过比对MD5码来验证2个文件是否相同。它的具体算法流程如下：将系统中所有文件计算MD5码存储到集合中并建立索引，称为集合S。当更新文件时，计算传入文件MD5码并在集合S中查找，若发现集合中存在相同的MD5码，说明该传入文件是重复文件，删除该文件，就达到了数据排重的目的。在效率方面，其查找过程就是将传入文件MD5码与全集S的MD5码元素按集合索引一条条比对，时间复杂度为O(n)，若传入文件全为新文件，则每次查找都要将集合从头查到尾，所以该算法的查找时间并不尽人意，没有对MD5码进行任何处理直接进行查找，对其利用率还处于原始阶段。……