摘要：海量数据上的处理常用数据结构的使用场合以及简单原理介绍，包括Bloom filter/Hash表/bitmap/堆/倒排索引/trie字典树等。
关键字：大数据处理 海量数据处理
Bloom filter/Hash表/bitmap/堆/倒排索引/trie字典树
海量数据/大数据处理，无非就是基于海量数据上的存储、处理、挖掘等操作。数据量的增大造成许多问题，数据量大导致存储、读取时间上会增加，操作起来占用时间会更多，需要内存也会更大。
针对上述问题，采取不同的解决方案。针对时间，我们可以采用巧妙的算法搭配合适的数据结构，如Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie树；针对空间，无非就一个办法：分而治之/hash映射从而大而化小，把规模大化为规模小的，各个击破问题也就迎刃而解。
以下内容基本来自blog：
http://zhlj11.iteye.com/blog/1709468
（1）分而治之/hash映射 + hash统计 + 堆/快速/归并排序：
分而治之/hash映射：针对数据太大，内存受限，只能是：把大文件化成(取模映射)小文件，即16字方针：大而化小，各个击破，缩小规模，逐个解决
hash统计：当大文件转化了小文件，那么我们便可以采用常规的hash_map(ip，value)来进行频率统计。
堆/快速排序：统计完了之后，便进行排序(可采取堆排序)，得到次数最多的IP。
（2）双层桶划分：
双层桶划分----其实本质上还是分而治之的思想，重在“分”的技巧上！
适用范围：第k大，中位数，不重复或重复的数字
基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子。
（3）Bloom filter/Bitmap：
http://www.cnblogs.com/qianye/archive/2013/05/02/3055625.html http://blog.csdn.net/dazhong159/article/details/7907207（
Bloom filter详解）
使用范围：实现数据字典，进行数据的判重，集合求交集
基本原理：基于bitmap，bitmap中用一个bit位来表示一个数字，而Bloom filter是用多个bit位是否同时存在来判定元素是否存在。它的实现用到了位数组和k个hash函数，存入一个元素时，用k个hash函数分别求值，并将相应的bit位置1，当查找的时候，根据k个hash值，到k个位置查找，如果k个位置都存在，表明该元素存在，如果有一个bit位不存在表明元素不存在。很明显这个过程并不保证查找结果是百分百正确。同时它也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动其它的关键字，一个简单的改进是使用counting bloom filter,用一个counter数组来替换位数组，就可以支持删除了。还有一个比较重要的问题，如何根据输入元素个数n，确定位数组m的大小以及 hash函数个数k. 当hash函数个数k=(ln2)*(m/n)时错误率最小，在错误率不大于E的情况下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合，因为要保证bit数组里至少一半为0，则应该满足m>=n*lg(1/E) * lge,大概就是n*lg(1/E)的1.44倍(lg表示以2为底的对数)
举个例子，我们假设错误率为0.01，则此时m应该大概是n的13倍，k大概是8个
注意m是以bit为单位，而n则是以元素个数为单位，通常单个元素的长度都是有很多bit的，所以使用Bloom filter通常很节省内存
（4）Trie树/数据库/倒排索引：
Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
它有3个基本性质： 根节点不包含字符，除根节点外每一个节点都只包含一个字符；从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；每个节点的所有子节点包含的字符都不相同。
适用范围：数据量大，重复多，但是数据种类小可以放入内存
基本原理及要点：实现方式，节点孩子的表示方式
扩展：压缩实现。
（5）外排序：
（6）分布式处理之Hadoop/Mapreduce：
MapReduce是一种计算模型，简单的说就是将大批量的工作（数据）分解（MAP）执行，然后再将结果合并成最终结果（REDUCE）。这样做的好处是可以在任务被分解后，可以通过大量机器进行并行计算，减少整个操作的时间。但如果你要我再通俗点介绍，那么，说白了，Mapreduce的原理就是一个归并排序。
适用范围：数据量大，但是数据种类小可以放入内存
基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。
阅读(1261) | 评论(0) | 转发(0) |
