存档

文章标签 ‘Bloom Filter’

Bloom Filter(一),引子:从哈希到布隆过滤器

2011年11月13日 5 条评论

---

布隆过滤器(Bloom Filter)系列博文总览

信息指纹那篇博文我们提到,使用哈希时,利用信息指纹将字符串转为128位整数既可以降低内存需耗,又可以节省查找时间;但是如果要处理的信息量特别大时,哈希表存储效率低的问题就显现出来了,此时就需要考虑其他数据结构了:Bloom Filter。

本篇文章要解决的问题:什么是布隆过滤器?为什么要使用布隆过滤器?

我们经常会遇到要判断一个元素是否在一个集合中这样的问题,例如以下情景:

  • 字处理软件中,需要检查一个英语单词是否拼写正确(也就是要判断它是否在已知的字典中)
  • 网络爬虫里,一个网址是否被访问过等等

最直接的方法就是将集合放入内存,使用哈希的方法,好处是快速、准确;缺点是费空间。请注意,这件事情是在内存中完成的,所以空间问题必须作为考虑因素。当要哈希的集合比较小时,这个问题不显著,但是当集合巨大时,对于有限的内存来说,哈希表存储效率低的问题就显现出来了,这里借数学之美中的案例说明一下bloom Filter的思想及使用它的必要性:

Yahoo,Hotmail 和 Gmai 那样的公众电子邮件(email)提供商,总是需要过滤来自发送垃圾邮件的人(spamer)的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址,全世界少说也有几十亿个发垃圾邮件的地址。如果用哈希表,每存储一亿个 email 地址, 就需 1.6GB 的内存(十亿字节为1G。用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹,然后将这些信息指纹存入哈希表,由于哈希表的存储效率一般只有 50%,因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB, 即十六亿字节的内存)。因此存贮几十亿个邮件地址可能需要上百 GB 的内存,一般服务器是无法存储的。

一种称作布隆过滤器的数学工具,它只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。

布隆过滤器实际上是一个很长的二进制向量一系列随机映射函数

按我的理解:说白了,bloom filter就是将集合元素进行位编码存储

阅读全文...

布隆过滤器(Bloom Filter)

2011年10月23日 没有评论

---

最初知道布隆过滤器是通过数学之美了解的,后来学习算法时,09年在西交BBS算法版上偶然看到一篇帖子,讲海量数据处理的,也提到了布隆过滤器,后来的学习过程中发现网上转载的相关文章铺天盖地,参差不一,大部分是一个概述性的东西,要真正为我所用还需要一个深入的思考和细致的分析,本博力求做到这样的思考和分析,对bloom filter做一个详细的总结,所涉参考文献也将一并给出,欢迎讨论。

本帖希望在了解bloom filter的基础上能分析解决实际问题,并实现其代码加深理解,拟包含以下几方面:

欢迎关注并讨论。

阅读全文...