海量数据处理资料分享

在面试中可能会遇到“假如给你十几个亿的数据,如何利用有限的内存和时间进行排序,查找和统计一些统计指标等等”,在附件中的资料中,给出了十个方法,并结合了具体的例子进行解释,个人感觉还是挺好的一份资料,虽然细节不是很详细,但是可以作为一个系统地了解过程吧,感兴趣的同学可以查阅更详细的资料。
本文只是资料分享,下面的总结不是原创,方法和例子都来源于附件中文章。
文章中给出了十个海量数据处理的方法,分别是:
1、哈希分治
2、SimHash算法
3、外排序
4、MapReduce
5、多层划分
6、位图
7、布隆过滤器
8、Trie树
9、数据库
10、倒排索引
下面列举几个文章中提到的几个代表性面试问题:
Problem 1:
    有一个1G大小的文件,每一行是一个词,现在统计出现频次Top100的所有词,每个词不超过16字节,内存大小限制为1M。
Answer:
    采用Hash分治的思想。
    1)顺序读取文件每一行,按照Hash(word) % 5000计算,将每个词归为5000个小文件中的每一个,这样每个文件平均大小200K(如果有某个文件大于1M,可以对之进行二次Hash划分)。
    2)对每个小文件,利用Trie树或HashTable统计词和词频,利用堆排序返回前100个最高频词。
    3)合并,5000 * 100个词和词频,Trie树或HashTable进行合并,然后堆排序返回前100最高频词。
 
 
Problem2:
    给定a,b两个文件,每个文件有50亿个URL,每个URL占64字节,如何利用4G内存的计算机求出两个文件中相同的URL。
Answer:
   采用Hash分治。
   1)对a文件中每个URL,计算Hash(URL)00,变为1000个小文件;同样地,对于b文件也划分为1000个小文件。
   2)对ai和bi文件进行查找相同URL,1<=i<=1000。这一步可以利用先将ai里面的所有URL加入HashSet,然后对于bi中的每一个URL进行查找即可。
   3)合并1000个小结果,得到最终结果。
 
 
Problem3:
    搜索引擎中的网络爬虫会爬取大量网页,但是有许多网页是转载或抄袭的,因此高度相似,如何将这些近似重复的网页筛选出来呢?网页数量是上亿级别的。
Analysis:
    如果利用向量空间模型+文本相似度计算,那么时间复杂度是平方级别,并且计算余弦相似度特别耗费时间。
    如果利用Hash值,那么这只能挑选出那些完全一样的网页,而不能得到近似重复的网页集合。
    所以思想应该放在:容错性的Hash上,即SimHash算法。
    SimHash包括分词、Hash、加权、合并、降维操作。
Answer:
   文本相似度计算 + SimHash算法。
   1)对每个网页利用SimHash得到文档的Hash值,即01字符串。
   2)计算网页之间的Hamming距离,这里设置阈值,小于某个阈值即判别为重复。
   3)第2步还是需要计算凉凉网页间的Hamming距离,时间复杂度也比较大,文章给出了一种利用鸽巢原理和倒排索引的方法降低时间复杂度。
 
 
Problem4:
    文件中有上亿个电话号码,每个号码8位数字,如何快速找到不重复的所有电话号码。
Analysis:
    两两比较肯定是下下策略。
    利用HashSet思想可以通过。
    如果能利用位图BitMap的思想就更好了,内存空间更省。
Answer:
    1) 8位数字最大的是99 999 999,就开辟一个长度为100 000 000的字符串,作为01位图,空间大小为100 000 000/8 Bytes,即12.5M。
    2)对每个号码,假如是82 876 123,就将字符串第82 876 123处置为1;
    3)将最后字符串里面所有1对应的index输出即可。
More:
    如果电话号码为11位呢,那么需要的内存空间就是12.5G,此时可以利用电话号码的一些特性,比如第一位为1等等特性缩小为1.25G空间,但是还是很大。
    所以位图不是任何情况下都适用的,当数据集中数据量很大,且每个数据本身很小的时候,利用位图比较优。
    其实位图可以理解为计数排序的思想,这里提一下Hash分治的思想和基数排序、桶排序的思想比较相似。
 
 
Problem5:
    邮件供应商要解决的问题之一就是过滤垃圾邮件,那么每天可能需要处理上亿封邮件,如何快速高效地进行判别垃圾邮件呢?
Analysis:
    提到垃圾邮件,可能会想到机器学习里面的朴素贝叶斯。
    利用已有垃圾邮件,通过SimHash可以实现相似邮件查找,从而判断是否是垃圾邮件。
    这里利用布隆过滤器来实现,其主要思想也是利用了Hash思想,是对位图的扩展。
Answer:
    布隆过滤器,可以允许一定错误率(即错误分类),但是效率高且时间复杂度比较低。
 
 
上面就是我选取的5个比较有代表性的问题,涉及到了很多新知识,比如SimHash、布隆过滤器、位图、Trie树等等,除此之外还有外排序、MapReduce等没有列举。个人感觉,花费一上午时间阅读这篇文章并写一个小的博客来总结,获益匪浅。这里分享给大家,希望大家能学习到一些知识!

0 个评论

要回复文章请先登录注册