logo头像
Snippet 博客主题

对海量数据进行去重的方法

一、数字型数据去重:

采用Bitmap数据结构:
数据中的数字作为数组的下标,该下标对应的数组的值为0或者1,0表示该下标对应的数字不存在,1表示该下标对应的数字存在。

具体做法:

  1. 初始化bits[capacity]为0;
  2. 遍历数据,修改值:bits[num]=1;
  3. 遍历bits数组,如果bits[index]=1,转换index为数字输出。

这样得到的输出结果就是去重后的结果。
优点:占用内存少,速度快。
项目中可以采用Google的开源项目EWAHCompressedBitmap,一种对Bitmap的高效实现。

二、文本型数据去重:

分两种:
第一种:一致性去重。
第二种:相似性去重。

一致性去重:
将文本通过哈希运算(如MD5),将结果用Bloom Filter判断是否重复。

相似性去重:
采用Simhash算法,通过海明距离判断文本的相似度。在比较相识度的时,可以通过抽屉原理减少比较时间。

参考文档:
算法分析:使用布隆过滤器(Bloom Filter)进行大数据量排序
实习日记:海量中文文本数据去重 算法及实现
我的数学之美系列二 —— simhash与重复信息识别

上一篇