海量数据处理 算法总结（一）

问题导读
1、什么是堆，有哪八大排序算法？
2、什么是Bloom Filter？
3、什么是Bit-map？






1. Bloom Filter
Bloom Filter（BF）是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。它是一个判断元素是否存在集合的快速的概率算法。Bloom Filter有可能会出现错误判断，但不会漏掉判断。也就是Bloom Filter判断元素不再集合，那肯定不在。如果判断元素存在集合中，有一定的概率判断错误。因此，Bloom Filter不适合那些“零错误”的应用场合。
而在能容忍低错误率的应用场合下，Bloom Filter比其他常见的算法（如hash，折半查找）极大节省了空间。
Bloom Filter的详细介绍：海量数据处理之Bloom Filter详解
【适用范围】
可以用来实现数据字典，进行数据的判重，或者集合求交集

【基本原理及要点】
原理要点：一是位数组， 而是k个独立hash函数。
1）位数组：
       假设Bloom Filter使用一个m比特的数组来保存信息，初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0，即BF整个数组的元素都设置为0。



2）k个独立hash函数

      为了表达S={x1, x2,…,xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。

          当我们往Bloom Filter中增加任意一个元素x时候，我们使用k个哈希函数得到k个哈希值，然后将数组中对应的比特位设置为1。即第i个哈希函数映射的位置hashi(x)就会被置为1（1≤i≤k）。 注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位，即第二个“1“处）。   



3）判断元素是否存在集合

    在判断y是否属于这个集合时，我们只需要对y使用k个哈希函数得到k个哈希值，如果所有hashi(y)的位置都是1（1≤i≤k），即k个位置都被设置为1了，那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素（因为y1有一处指向了“0”位）。y2或者属于这个集合，或者刚好是一个false positive。



      显然这 个判断并不保证查找的结果是100%正确的。

Bloom Filter的缺点：
       1）Bloom Filter无法从Bloom Filter集合中删除一个元素。因为该元素对应的位会牵动到其他的元素。所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。 此外，Bloom Filter的hash函数选择会影响算法的效果。
       2）还有一个比较重要的问题，如何根据输入元素个数n，确定位数组m的大小及hash函数个数，即hash函数选择会影响算法的效果。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况 下，m至少要等于n*lg(1/E) 才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应 该>=nlg(1/E)*lge ，大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。
举个例子我们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。
注意：
         这里m与n的单位不同，m是bit为单位，而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。
       一般BF可以与一些key-value的数据库一起使用，来加快查询。由于BF所用的空间非常小，所有BF可以常驻内存。这样子的话，对于大部分不存在 的元素，我们只需要访问内存中的BF就可以判断出来了，只有一小部分，我们需要访问在硬盘上的key-value数据库。从而大大地提高了效率。

【扩展】  
Bloom filter将集合中的元素映射到位数组中，用k（k为哈希函数个数）个映射位是否全1表示元素在不在这个集合中。Counting bloom filter（CBF）将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。Spectral Bloom Filter（SBF）将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。

【问题实例】
给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？
根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿 bit，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。 现在可用的是340亿，相差并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换成ip，则大大简单了。


2. Hash
【什么是Hash】
       Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不 同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
       HASH主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系。
      数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易 的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，（也是树的一种存储结构，称为二叉链表）我们可以理解为“链表的数组”，如图：

                                                
     左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。
元素特征转变为数组下标的方法就是散列法。
散列法当然不止一种，下面列出三种比较常用的：
1，除法散列法 （求模数）
最直观的一种，上图使用的就是这种散列法，公式：
index = value % 16
学过汇编的都知道，求模数其实是通过一个除法运算得到的，所以叫“除法散列法”。
2，平方散列法
求index是非常频繁的操作，而乘法的运算要比除法来得省时（对现在的CPU来说，估计我们感觉不出来），所以我们考虑把除法换成乘法和一个位移操作。公式：
index = (value * value) >> 28
如果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问 题，value如果很大，value * value不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index。
3，斐波那契（Fibonacci）散列法
平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿value本身当作乘数呢？答案是肯定的。
1，对于16位整数而言，这个乘数是40503
2，对于32位整数而言，这个乘数是2654435769
3，对于64位整数而言，这个乘数是11400714819323198485
这几个“理想乘数”是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列，如果你还有兴 趣，就到网上查找一下“斐波那契数列”等关键字，我数学水平有限，不知道怎么描述清楚为什么，另外斐波那契数列的值居然和太阳系八大行星的轨道半径的比例 出奇吻合，很神奇，对么？
对我们常见的32位整数而言，公式：
i ndex = (value * 2654435769) >> 28
如果用这种斐波那契散列法的话，那我上面的图就变成这样了：
                                             
很明显，用斐波那契散列法调整之后要比原来的取摸散列法好很多。
【适用范围】
快速查找，删除的基本数据结构，通常需要总数据量可以放入内存。
【基本原理及要点】
hash函数选择，针对字符串，整数，排列，具体相应的hash方法。
碰撞处理：
一种是open hashing，也称为拉链法；
另一种就是closed hashing，也称开地址法，opened addressing。
【扩展】
d-left hashing中的d是多个的意思，我们先简化这个问题，看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备一个哈希函数，h1和h2。在存储一个新的key时，同 时用两个哈希函数进行计算，得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置，哪一个 位置已经存储的（有碰撞的）key比较多，然后将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，就把新key 存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。
【问题实例】
1).海量日志数据，提取出某日访问百度次数最多的那个IP。
IP的数目还是有限的，最多2^32个，所以可以考虑使用hash将ip直接存入内存，然后进行统计。

3. Bit-map
【什么是Bit-map】
        所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。
        如果说了这么多还没明白什么是Bit-map，那么我们来看一个具体的例子，假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元 素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes），首先我们开辟 1Byte的空间，将这些空间的所有Bit位都置为0(如下图：)
                                                      

然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置为1（可以这样操作 p+(i/8)|(0x01<<(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况，这里默认为Big-ending）,因为是从零开始的，所以要把第五位 置为一（如下图）：

                                       

然后再处理第二个元素7，将第八位置为1,，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1，这时候的内存的Bit位的状态如下：

                                                   

然后我们现在遍历一遍Bit区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序的目的。下面的代码给出了一个BitMap的用法：排序。
C代码  

//定义每个Byte中有8个Bit位    
     #include ＜memory.h＞    
     #define BYTESIZE 8    
     void SetBit(char *p, int posi)    
     {    
         for(int i=0; i ＜ (posi/BYTESIZE); i++)    
         {    
             p++;    
         }    
          
         *p = *p|(0x01＜＜(posi%BYTESIZE));//将该Bit位赋值1    
         return;    
    }    
         
    void BitMapSortDemo()    
     {    
         //为了简单起见，我们不考虑负数    
        int num[] = {3,5,2,10,6,12,8,14,9};    
          
        //BufferLen这个值是根据待排序的数据中最大值确定的    
        //待排序中的最大值是14，因此只需要2个Bytes(16个Bit)    
        //就可以了。    
        const int BufferLen = 2;    
        char *pBuffer = new char[BufferLen];    
          
        //要将所有的Bit位置为0，否则结果不可预知。    
        memset(pBuffer,0,BufferLen);    
        for(int i=0;i＜9;i++)    
        {    
            //首先将相应Bit位上置为1    
            SetBit(pBuffer,num[i]);    
        }    
          
        //输出排序结果    
         for(int i=0;i＜BufferLen;i++)//每次处理一个字节(Byte)    
        {    
            for(int j=0;j＜BYTESIZE;j++)//处理该字节中的每个Bit位    
            {    
                //判断该位上是否是1，进行输出，这里的判断比较笨。    
                //首先得到该第j位的掩码（0x01＜＜j），将内存区中的    
                //位和此掩码作与操作。最后判断掩码是否和处理后的    
               //结果相同    
               if((*pBuffer&(0x01＜＜j)) == (0x01＜＜j))    
               {    
                    printf("%d ",i*BYTESIZE + j);    
                }    
            }    
            pBuffer++;    
            }    
    }    
         
    int _tmain(int argc, _TCHAR* argv[])    
     {    
         BitMapSortDemo();    
         return 0;    
     }    
复制代码

【适用范围】

可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下
【基本原理及要点】
使用bit数组来表示某些元素是否存在，比如8位电话号码

【扩展】

Bloom filter可以看做是对bit-map的扩展

【问题实例】

1)已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。

8位最多99 999 999，大概需要99m个bit（1024*1024 *99个bit ），大概10几m字节的内存即可。
申请内存空间的大小为:int a[1 + N/32] =（(99 999 999/32 +1)*4 个字节/1024/1024 = 1.2M
（可以理解为从0-99 999 999的数字，每个数字对应一个Bit位，所以只需要99M个Bit==1.2MBytes，这样，就用了小小的1.2M左右的内存表示了所有的8位数的电话）

2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上，在遍历这些数的时候，如果对应位置的值是 0，则将其置为1；如果是1，将其置为2；如果是2，则保持不变。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit- map，都是一样的道理。

4. 堆
【什么是堆】
在八大排序里面有堆 的详细介绍：八大排序算法
概念：堆是一种特殊的二叉树，具备以下两种性质
1）每个节点的值都大于（或者都小于，称为最小堆）其子节点的值
2）树是完全平衡的，并且最后一层的树叶都在最左边
这样就定义了一个最大堆。如下图用一个数组来表示堆：
                           
那么下面介绍二叉堆：二叉堆是一种完全二叉树，其任意子树的左右节点（如果有的话）的键值一定比根节点大，上图其实就是一个二叉堆。
你一定发觉了，最小的一个元素就是数组第一个元素，那么二叉堆这种有序队列如何入队呢？看图：

                                                   
假设要在这个二叉堆里入队一个单元，键值为2，那只需在数组末尾加入这个元素，然后尽可能把这个元素往上挪，直到挪不动，经过了这种复杂度为Ο(logn)的操作，二叉堆还是二叉堆。
那如何出队呢？也不难，看图                           
                                      

出队一定是出数组的第一个元素，这么来第一个元素以前的位置就成了空位，我们需要把这个空位挪至叶子节点，然后把数组最后一个元素插入这个空位，把这个“空位”尽量往上挪。这种操作的复杂度也是Ο(logn)。
【适用范围】
海量数据前n大，并且n比较小，堆可以放入内存
【基本原理及要点】
最大堆求前n小，最小堆求前n大。方法，比如求前n小，我们比较当前元素与最大堆里的最大元素，如果它小于最大元素，则应该替换那个最大元 素。这样最后得到的n个元素就是最小的n个。适合大数据量，求前n小，n的大小比较小的情况，这样可以扫描一遍即可得到所有的前n元素，效率很高。
【扩展】
双堆，一个最大堆与一个最小堆结合，可以用来维护中位数。
【问题实例】
1)100w个数中找最大的前100个数。
用一个100个元素大小的最小堆即可。


下一篇：海量数据处理 算法总结（二）

威武，学习了，算法，慢慢品

好东西，学习了！

好东西，学习了！

好东西，学习了！

好东西，收下了。。。

学习了，算法

收藏了，以后再看

算法是最烧脑的东西 有是有灵光一现 有时候绞尽脑汁！