首页 / 大数据 / 大数据处理方法bloom filter
大数据处理方法bloom filter
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了大数据处理方法bloom filter,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1023字,纯文字阅读大概需要2分钟。
内容图文
![大数据处理方法bloom filter](/upload/InfoBanner/zyjiaocheng/1132/2d14aa68b2c143b881cab416da96833e.jpg)
布嵘过滤器为一种空间效率很高的随机数据结构, 它的实现方法主要包括一个位数组, 可用c++中的bitset来实现和k个哈希函数. 算法原理为: 当向某一个集合中添加一个元素的时候, 该元素会分别作为K个哈希函数的输入, 将该元素映射到位数组的k个点, 将这些点置为1. 当要查找某个元素是否在该集合中时, 只要将该元素作为k个哈希函数的输入, 然后看映射到的k个点是否为1, 如果全为1, 则该元素(可能)在该集合中, 如果出现了一个为0, 则说明该元素不在该集合中. 这就是该算法的基本思想.
集合s = {x1, x2, x3,...xn}在添加元素时, 设置位数组的过程:
说全为1, 该元素可能存在是因为该算法是存在一个错误率的, 即可能将一个不存在的元素判断为存在这个集合中.为了使错误率最低, 需要知道如何根据输入元素个数n,确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下,m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。
即: 位数组大小 m >= nlg(1/E)*lge (E为错误率) = nlg(1/E)1.44倍(lg表示以2为底的对数)
哈希函数的个数 k = (ln2)*(m/n)
所以bloom filter比较适合可以容忍错误的应用.它通过低的错误率来节省大量的存储空间.
使用范围: 拼音错误检测和数据库系统; 可以用来实现数据字典, 数据判重或者求集合的交集.
Bloom filter将集合中的元素映射到位数组当中, 用k(k为哈希函数的个数)个映射位是否全1表示元素是否在这个集合中. 它的缺点是, 一个元素添加到集合中之后, 就不能删除了, 否则该元素对应的位会影响其他元素. CBF是一种改进, 它将每个bit改为了一个计数器, 从支持删除操作,即每删除一个关键字, 将对应k个位(计数器)减一. SBF 将计数器与元素出现次数相关联, 将计数器中最小的作为该元素出现的频率.
原文:http://www.cnblogs.com/xieyizun-sysu-programmer/p/bigdata.html
内容总结
以上是互联网集市为您收集整理的大数据处理方法bloom filter全部内容,希望文章能够帮你解决大数据处理方法bloom filter所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。