存档

文章标签 ‘海量数据处理’

布隆过滤器(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函数,就不讨论了,哈哈

阅读全文...