首页 > 代码库 > 海量数据处理方法

海量数据处理方法

1.hashing

  适用范围:快速查找,删除的基本数据结构,通常需要总数据量可以放入内存。
 这里的hashing和 hashmap是不一样的概念,这里的hash指的是hashtable可以看例子:(比较两个字符串的包含问题)
 
 
  问题实例:

  1).海量日志数据,提取出某日访问百度次数最多的那个IP。
   IP的数目还是有限的,最多2^32个,所以可以考虑使用hash将ip直接存入内存,然后进行统计。

2.bitmap
  适用范围:可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下。
   疑惑:bitmap处理的数据范围最大为多少?
   
   将bit-map扩展一下,用2bit表示一个数即可,0表示未出现,1表示出现一次,2表示出现2次及以上。或者我们不用2bit来进行表示,我们用两个bit-map即可模拟实现这个2bit-map。
   问题实例:

  1)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。
  8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。
  2)2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。

 
3.
    适用范围:海量数据前n大,并且n比较小,堆可以放入内存。
    问题实例:
  1)100w个数中找最大的前100个数。
  用一个100个元素大小的最小堆即可。
 
4.双层桶划分----其实本质上就是【分而治之】的思想,重在“分”的技巧上
  适用范围:第k大,中位数,不重复或重复的数字

 基本原理及要点:因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最后在一个可以接受的范围内进行。可以通过多次缩小,双层只是一个例子。

  扩展:
  问题实例:
  1).2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。
  有点像鸽巢原理,整数个数为2^32,也就是,我们可以将这2^32个数,划分为2^8个区域(比如用单个文件代表一个区域),然后将数据分离到不同的区域,然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间,就可以很方便的解决。

  2).5亿个int找它们的中位数。
  这个例子比上面那个更明显。首先我们将int划分为2^16个区域,然后读取数据统计落到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。

这个看的不是很明白。

  
5.倒排索引
  适用范围:搜索引擎,关键字查询

  基本原理及要点:为何叫倒排索引?一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。

 以英文为例,下面是要被索引的文本:
    T0 = "it is what it is"
    T1 = "what is it"
    T2 = "it is a banana"

我们就能得到下面的反向文件索引:

    "a":      {2}
    "banana": {2}
    "is":     {0, 1, 2}
    "it":     {0, 1, 2}
    "what":   {0, 1}

 检索的条件"what","is"和"it"将对应集合的交集。

扩展:
  问题实例:文档检索系统,查询那些文件包含了某单词,比如常见的学术论文的关键字搜索。
 

6.外排序 --归并排序
   适用范围:大数据的排序,去重
   一般处理海量数据的时候,首先用hashmap分到较小的文件中,或者是mapreduce分配到多个计算机中,然后再通过归约来进行统计。
   问题实例:

  1).有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16个字节,内存限制大小是1M。返回频数最高的100个词。

  这个数据具有很明显的特点,词的大小为16个字节,但是内存只有1m做hash有些不够,所以可以用外排序。内存可以当输入缓冲区使用。首先就是hashmap到不同文件中。

 7.mapreduce
   
 
8.trie树,还需要总结
  
有个实例的解法很好,这里贴上去

 
本文只是相当于笔记,便于日后复习。内容全部来自 http://blog.csdn.net/v_JULY_v/article/details/6279498 
  
 
 
 



来自为知笔记(Wiz)