实习日记:海量中文文本数据去重 算法及实现

在某视频公司实习的时候遇到一个问题，也不算海量吧，200万左右的短中文文本数据去重，然后在Elasticsearch中重建索引。

感谢参考链接中提到还有很多没有提到的博客文章的技术分享，小白小生还是学到了不少东西，在这里做一下记录。

文本去重有两策略，其一是通过 MD5 等给文本生成数字证书，这样做 叫 “一致性” check。其二是 计算文本间的相似度，这种做法 是 “相似性” check

显然 “一致性” check 并不能很好的满足 文本查重去重，而对于 “相似性” check,有很多经典的算法

段子评论去重

去重本应该根据相似度去重的，根据的算法原理为 simhash 和抽屉原理，simhash 加海明距离 确定是否相似，一般认为海明距离在4以内（小于等于3）为相似，我们的数据大概在 200万条，如果一一比较海明，时间复杂度是挺大的，在 （1+n）n/2 O(n^2),利用抽屉原理，<K,V>数据库存四份，每份K 为 16 bit 的hash 码值，一共 2^16个K值，V为对应 K的剩下三个 16bit 的list 链，这时如果来了一个新的 64 bit 的simhash码，分成四份，遍历四份<K,V> 数据库，如果都没找到相同的K，则可以认为改文本在库中没有相似文本，然后将其put 进四份<K,V>数据库中，若找到相同的K，则遍历比较V上的list 的海明距离，若海明距离在4以内则丢弃。采用这种做法时间 需要利用额外的空间，这个空间只利用内存来做在 10G左右，所以需要额外的数据库辅助，好处是降低了时间成本。

海明距离
两个码字的对应比特取值不同的比特数称为这两个码字的海明距离。在一个有效编码集中,任意两个码字的海明距离的最小值称为该编码集的海明距离。举例如下：10101和00110从第一位开始依次有第一位、第四、第五位不同，则海明距离为3。

参考链接:

经典算法1---相似度--模糊查询，查抄袭，语言识别
短文本合并重复（去重）的简单有效做法
海量数据相似度计算之simhash短文本查找
我的数学之美系列二 —— simhash与重复信息识别
海量数据相似度计算之simhash和海明距离
LSH 位置敏感哈希算法
http://blog.csdn.net/al_xin/article/details/38919361
https://zhuanlan.zhihu.com/p/22936654
http://blog.csdn.net/heiyeshuwu/article/details/69706414