大数据去重算法

大数据去重算法

Hash 分割

思路：将大数据集进行分割，然后去重最后合并

方法：选择 hash 函数， 用 md5 作为转码规则几乎不会碰撞，进行分割时候对 个数取模

MapReduce，Hadoop

完事后进行 取低位 Hash 对比

Trie 树实现

Redis 分布式 搞定 HashTable dump load性能问题

shingling NLP去重

Bloom Filter

简介：多哈希函数映射的快速查找算法

用途：通常用于在一些需要快速判断某个元素属于集合，但不严格要求 100% 正确的场景

评估点：错误率，哈希函数个数，Bloom 位数大小

改进：引入几个独立的 hash 函数 减少碰撞概率当集合中的元素过多时候 n/m 过大时候 组建新的 Filter 来减小误判

SimHash

简介：Google 指纹生成算法，降维操作相似度判断 海明距离

应用：降维搜索比较，提高搜索速度

双层桶划分

划分数据然后将数据分离到不同区域

在不同区域中利用 bit map解决

BerkeleyDB

磁盘判重方案提供了相应的方法去判重

方法：将 url 作为 key 值为固定值做判重

MD5+ 去重树