存档

‘海量数据处理’ 分类的存档

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的基础上能分析解决实际问题,并实现其代码加深理解,拟包含以下几方面:

欢迎关注并讨论。

阅读全文...

海量数据处理之归并、堆排、前K方法的应用:一道面试题

2011年9月8日 6 条评论

 

最初关注海量处理方面是因为好久以前在西安交大BBS算法版上看到一个牛人总结的帖子,收集了起来,后来发现网上铺天盖地地转载过,那个帖子提供了一些解决问题很好的思路,所以就零碎地整理过海量数据处理方面的一些方法,但终归没有深入并做一个稍微细致的思考,从这篇博文开始,希望能坚持整理出来。

下面一道面试题是以前大雄考过我的,据说是那时一些公司常问的类型题目,这里回顾并总结一下,欢迎大家讨论并提出问题。

题目:一个10G的关键词的log,找出词频最高的前K个词,设可用内存为2G左右

分析:

本题的难点主要有两处,一是如何在有限内存下对大文件进行词频统计;二是如何在有限内存的下找出词频的前K大个词

  1. 词频统计

词频统计,我们很自然的会想到使用hash。但是直接hash内存是放不下的啊…怎么办?其实对于有限内存下的大文件处理,都可总结为归并的思想,不过要注意归并时的分段亦是有学问的。请比较归并a与归并b方法

  • 归并a:将数据分为5段,分别对每段在内存中hash统计并将统计结果写入文件,然后合并分段的hash。

问题:表面看来不错的主意,实则有很大问题,稍微想一下,a方法存在一个主要的困难就是,hash合并的时候相当于同时在5个文件中判断是否有相同的词,要这样做会非常繁琐。

怎么解决呢?我当时是受编程珠玑中第一题(排序一千万个32位整数)启发的,它在归并分段的时候,不是直接的简单分段,而是每段取一个范围比如第一段取0~249000之间的数,这样有什么好处?将来的各段数彼此间是没有交集(重复)的。所以我们的思想就是要让这10G的关键词分段后各小段没有交集,这样hash合并就没有问题了。请看归并b

  • 归并b:将数据分为5段,分段时对每个词hashhash值在一个范围中的词语分到一个段中,然后对于每个分段统计的hash结果直接都写入一个文件即可。

分析:使用hash分段,保证各小段没有重复的词。我当时想的方法是将词语的首字拼音打头一样的分在一段中,例如“五谷丰登”、“万箭齐发”分到一起,都是w打头的拼音,其实这仅仅只是hash的一种,至于具体的hash函数,就不讨论了,哈哈

阅读全文...