基于Simhash改进的文本去重算法

张亚男，陈卫卫，付印金，徐 堃

(陆军工程大学 指挥控制工程学院，江苏 南京 210007)

0 引 言

进入大数据时代，数字化信息呈现爆炸式增长。伴随着云计算、大数据、物联网等信息技术的快速发展，数据量呈几何级增长，据IDC最新发布的报告预测，全球数据总量将从2016年的16.1 ZB增长到2025年的175 ZB[1]。随着全球生成和存储的数据越来越多，对存储容量的需求将继续以稳定的速度增长。但是无论是云存储系统，还是传统的数据存储系统，都存在大量的冗余数据，有的系统中数据重复率高达70%～90%[2]。越来越多的研究者开始关注解决数据冗余问题以缩减存储空间，重复数据删除技术应运而生。重复数据删除技术的核心思想是，只存储唯一的数据对象，对于其他重复数据则通过存储指针代替，指针指向该唯一数据对象。

当前流行的相似文本检测和去重算法主要有k-shingle[3]、Minhash[4]和Simhash[5]算法。Simhash是Google工程师Charikar等人提出的一种局部敏感哈希算法，用来解决亿万级别网页去重问题。Simhash算法较其他算法的优势是处理速度快，结果准确度高，被广泛应用于相似文本检测、冗余数据去重和数据异常检测等领域[6]。该文主要对Simhash算法在文本去重上的应用进行研究和改进，以进一步提高其检测重复文本的精确率。

1 相关研究

1.1 Simhash算法

传统的哈希算法能够对任意长度的输入数据进行计算，输出固定长度的哈希值。SHA-1、MD5等传统哈希算法，对输入数据非常敏感，只要有1 bit的差距都几乎不可能产生相同的哈希值，因此无法衡量文本的相似度。……