大数据去重算法
2019-08-09 14:25:25 0 举报AI智能生成
大数据去重算法整理
作者其他创作
大纲/内容
Hash 分割
思路：将大数据集进行分割，然后去重最后合并
方法：选择 hash 函数， 用 md5 作为转码规则几乎不会碰撞，
进行分割时候对 个数取模
进行分割时候对 个数取模
MapReduce，Hadoop
完事后进行 取低位 Hash 对比
Trie 树实现
Redis 分布式 搞定 HashTable
dump load性能问题
dump load性能问题
shingling NLP去重
Bloom Filter
简介：多哈希函数映射的快速查找算法
用途：通常用于在一些需要快速判断某个元素属于集合
，但不严格要求 100% 正确的场景
，但不严格要求 100% 正确的场景
评估点：错误率，哈希函数个数，Bloom 位数大小
改进：引入几个独立的 hash 函数 减少碰撞概率
当集合中的元素过多时候 n/m 过大时候 组建新的 Filter 来减小误判
当集合中的元素过多时候 n/m 过大时候 组建新的 Filter 来减小误判
SimHash
简介：Google 指纹生成算法，降维操作
相似度判断 海明距离
相似度判断 海明距离
应用：降维搜索比较，提高搜索速度
双层桶划分
划分数据然后将数据分离到不同区域
在不同区域中利用 bit map解决
BerkeleyDB
磁盘判重方案提供了相应的方法去判重
方法：将 url 作为 key 值为固定值做判重
MD5+ 去重树
0 条评论
下一页
