数学之美：布隆过滤器 && BitMap

我会带着你远行 2021-06-11 15:12 499阅读 0赞

[漫画：什么是Bitmap算法？][Bitmap]

在判断垃圾邮件时，我们需要判断当前邮件是否在垃圾邮件集合中。而判断一个元素是否存在集合中，最好还是使用哈希表。但如果这个集合非常庞大，如需要存储一亿个邮件地址。使用哈希表将每个邮件地址哈希成8个字节，加上哈希表的存储效率只有50%，那么总共就需要1\*8\*2=16亿字节，也就是1.6GB的内存。如果是几十亿，那么需要上百GB内存，一般计算机是无法满足的。

而布隆过滤器可以实现仅用1/8-1/4的大小就能解决该问题。原理如下：

![70][]

布隆过滤器不会漏掉黑名单中任何一个地址，但是可能会出现某些不在黑名单中的邮件地址也被认为在黑名单内。因为某个邮件地址对应的8个地址可能恰好在被设置成了1。因此有一定的误识别率，常见解决办法是添加一个白名单。

布隆过滤器背后的数学原理在于两个完全随机的数字冲突的概率很小，因此可以在很小的误识别概率下用较少的存储空间存储大量信息，由于只涉及到算术运算，因此速度快，使用方便。

![70 1][]

![70 2][]

![70 3][]

**BitMap：**

[来源][Link 1]

MapReduce是一种编程模型，用于大规模数据集（大于1TB）的并行运算。概念"Map（映射）"和"Reduce（归约）"

Bit-map空间压缩和快速排序去重

**1. Bit-map的基本思想**  
　　32位机器上，对于一个整型数，比如int a=1 在内存中占32bit位，这是为了方便计算机的运算。但是对于某些应用场景而言，这属于一种巨大的浪费，因为我们可以用对应的32bit位对应存储十进制的0-31个数，而这就是Bit-map的基本思想。Bit-map算法利用这种思想处理大量数据的排序、查询以及去重。  
　　Bitmap在用户群做交集和并集运算的时候也有极大的便利。

**2. Bit-map应用之快速排序**  
　　假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）,我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes），首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0，  
![bitmap1][]  
　　对应位设置为1:  
![bitmap2][]  
　　遍历一遍Bit区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序的目的，时间复杂度O(n)。  
　　优点：  
　　　　运算效率高，不需要进行比较和移位；  
　　　　占用内存少，比如N=10000000；只需占用内存为N/8=1250000Byte=1.25M。   
　　缺点：  
　　　　所有的数据不能重复。即不可对重复的数据进行排序和查找。

**3. Bit-map应用之快速去重**  
　　2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。   
　　首先，根据“内存空间不足以容纳这2.5亿个整数”我们可以快速的联想到Bit-map。下边关键的问题就是怎么设计我们的Bit-map来表示这2.5亿个数字的状态了。其实这个问题很简单，一个数字的状态只有三种，分别为不存在，只有一个，有重复。因此，我们只需要2bits就可以对一个数字的状态进行存储了，假设我们设定一个数字不存在为00，存在一次01，存在两次及其以上为11。那我们大概需要存储空间几十兆左右。  
　　接下来的任务就是遍历一次这2.5亿个数字，如果对应的状态位为00，则将其变为01；如果对应的状态位为01，则将其变为11；如果为11，,对应的转态位保持不变。  
　　最后，我们将状态位为01的进行统计，就得到了不重复的数字个数，时间复杂度为O(n)。

**4. Bit-map应用之快速查询**  
　　同样，我们利用Bit-map也可以进行快速查询，这种情况下对于一个数字只需要一个bit位就可以了，0表示不存在，1表示存在。假设上述的题目改为，如何快速判断一个数字是够存在于上述的2.5亿个数字集合中。  
　　同之前一样，首先我们先对所有的数字进行一次遍历，然后将相应的转态位改为1。遍历完以后就是查询，由于我们的Bit-map采取的是连续存储（整型数组形式，一个数组元素对应32bits），我们实际上是采用了一种分桶的思想。一个数组元素可以存储32个状态位，那将待查询的数字除以32，定位到对应的数组元素（桶），然后再求余（%32），就可以定位到相应的状态位。如果为1，则代表改数字存在；否则，该数字不存在。

**5. Bit-map扩展——Bloom Filter(布隆过滤器)**  
　　当一个元素被加入集合中时,通过k各散列函数将这个元素映射成一个位数组中的k个点,并将这k个点全部置为1.  
　　有一定的误判率--在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误判为属于这个集合.因此,它不适合那些"零误判"的应用场合.在能容忍低误判的应用场景下,布隆过滤器通过极少的误判换区了存储空间的极大节省.  
![14973179752164.jpg][]  
　　Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到\{1,…,m\}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注：如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。  
![Bloom Filte][]  
在判断y是否属于这个集合时，对y应用k次哈希函数，若所有hi(y)的位置都是1（1≤i≤k），就认为y是集合中的元素，否则就认为y不是集合中的元素。  
![14973179645247.jpg][]

**6. 总结**  
　　使用Bit-map的思想，我们可以将存储空间进行压缩，而且可以对数字进行快速排序、去重和查询的操作。Bloom Fliter是Bit-map思想的一种扩展，它可以在允许低错误率的场景下，大大地进行空间压缩，是一种拿错误率换取空间的数据结构。

**7. 应用**  
　　适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下  
　　基本原理及要点：使用bit数组来表示某些元素是否存在，比如8位电话号码  
　　扩展：bloom filter可以看做是对bit-map的扩展

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

> 8位最多99 999 999，大概需要99m个bit，大概10几M字节的内存即可。

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

> 方案1：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存232\*2bit=1GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。

[Bitmap]: https://zhuanlan.zhihu.com/p/54783053
[70]: /images/20210520/854cc8eff1a94426ad2538de1a73b27a.png
[70 1]: /images/20210520/981716923db84b8f9b41c5770a4d09e4.png
[70 2]: /images/20210520/484d7565fb234d1e98740a343146b574.png
[70 3]: /images/20210520/b7133da138bc48c1be2aaef8607c1aa3.png
[Link 1]: https://www.cnblogs.com/yangjiannr/p/da-shu-ju-chu-libitmap.html
[bitmap1]: http://oc3uwt4a5.bkt.clouddn.com/bitmap1.jpeg
[bitmap2]: http://oc3uwt4a5.bkt.clouddn.com/bitmap2.jpeg
[14973179752164.jpg]: http://oc3uwt4a5.bkt.clouddn.com/14973179752164.jpg
[Bloom Filte]: http://oc3uwt4a5.bkt.clouddn.com/Bloom%20Filter.jpeg
[14973179645247.jpg]: http://oc3uwt4a5.bkt.clouddn.com/14973179645247.jpg