目录
0. 问题
假设有两个集合(A)和(B)，它们均含有不同数量的字符串，如何统计(A)中的哪些元素在(B)中也存在？
对于这个问题，最直观的想法就是，对(A)中的每个元素都遍历一遍集合(B)，这样就可以得到想要的结果。方法是没有问题，但是非常的麻烦，而且当数据量非常大的时候，能不能把两个集合都放到内存中都是一个未知数。
笔者认为，无论采取什么样的方式，只要是操作的对象是集合的元素本身，那么效率不会有太多提高，而且内存问题始终是一个桎梏。既然不能对元素本身进行操作，那么就需要找到一种映射，使得我们可以根据映射后的“元素”来进行判断。我们知道，散列表（Hash Table）中最重要的部分——哈希函数其实就提供了类似的映射方式，而布隆过滤器（Bloom Filter）就是利用多个哈希函数来将原始集合进行“缩小”以达到满足内存的要求。
1. 建立一个布隆过滤器
如何建立一个布隆过滤器呢？首先，假设集合(B)中有(n)个元素，我们定义一个长度为(m)的向量，并将其初始化为0。对于某些自定义的哈希函数(f_1,f_2,f_3,...,f_k)，它们可以将集合(B)中任一个元素(b_1)映射成(k)个([1,m])中的正整数，每个正整数均代表的是向量中的某个位置，然后将该位置处的值设置为1。将(B)中的每个元素经过这些函数的运算处理之后所得到的向量就称之为集合(B)的布隆过滤器。我们知道，在计算机中每个bite所可能的取值为0或者1，那么上述向量就可以用内存中的二进制向量来表示，即可以建立一个(m)bite的二进制向量来作为集合的处理后的过滤器。
需要注意的是，这里的“过滤器”指的既是处理过程（(k)个哈希函数的设置），又是处理的结果（处理后的向量），这与我们日常理解的实物过滤器不同（比如空气过滤器，指的是一种可以净化空气的装置，但并不会强调净化后的空气的作用）。
2. 它是如何工作的
将此图与上面的介绍相对应，元素个数(n=3)，哈希函数一共有(k=3)个，向量长度(m=18)，待检验的元素为(w)。不难理解，三个元素(x,y,z)经过哈希函数映射之后的值（假设）分别是(x:[2,6,14];y:[5,12,17];z:[4,6,12])。于是将这些位置上的值设置为1。对于新的元素(w)，经过上述相同的哈希函数映射后的值分别是：5，14，16。尽管5和14的位置上均为1，但是16的位置上为0，这就说明(w)一定不在集合里面。
通过这个简单的例子，相信大家一定能理解，判断一个元素不在原始集合里的证据是充分的，因为相同的元素经过相同的哈希函数映射后一定得到的是相同的值。但是，即使某个元素经过函数映射后得到的位置上的值均为1，也不能说明该元素一定在集合中，因为哈希函数的随机性使得不同的元素也可能映射到同一个位置（如上图所示）。所以，布隆过滤器有存在“假正率”（False Positive），而不会有“假负率”（False Negative）。
3. 优缺点分析
优点1. 节约存储空间
正如上面说到的，布隆过滤器不存储数据本身，而是把数据映射为内存中的一个位，这样就大大减少了内存占用。读者一定会觉得，集合数量(n)如果和二进制向量的长度(m)之间一定满足某些条件吧，或者直观来看，(m)一定要比(n)大很多才行吧，不然假正率就太高了。的确，为了保证FP在一定的水平之下，二进制向量长度要比集合元素数要长，我将在下面附上具体的说明。尽管如此，对于较大的数据量而言，采用这种数据结构仍然比存储元素本身更节省空间。
优点2. 查询效率高
对于一个已经建好的布隆过滤器（确定的(k)个哈希函数以及处理后的二进制向量），我们要判断一个新的元素是否在该集合中，只需要进行(k)次哈希映射计算，然后看对应的位置上是0还是1即可，与集合中元素的个数没有关系，这一点其他很多的数据结构都无法做到。另外，由于(k)个哈希函数之间是相互独立的，因此可以采取并行运算的方式，进一步加快速度。
缺点1. FP无法消除
我们可以尽可能的降低FP的值，但却永远无法消除它，这是这种数据结构本身的特点所决定的。因为我们无法找到一个完美的映射方式，来将所有可能的元素映射为不同的值。
缺点2. 删除困难
如果要想往过滤器中添加元素是非常简单的，只需要做几次映射运算即可。但是如果要删除集合中的某个元素，却几乎是不可能的。要删除一个元素，首先就要判断这个元素一定在集合中才会删除，但是这一点这个过滤器就无法做到。另外，假设我们确定一个元素一定在集合中，然后通过映射找到了二进制向量中对应的位置，但是我们又不确定这些位置是不是也是其他某些元素映射后的位置，盲目重置为0的话很可能会多删。正如图中第6个位置，(x)和(z)均映射到了该位置，重置为0则会影响两个元素。
4. 假正率推导及最优选择
并非严谨的数学推导，但不影响读者理解。
4.1 假正率推导
再重申以下字母的含义：
- (m)：二进制向量的长度
- (n)：集合中的元素个数
- (k)：哈希函数的个数
- (p)：某元素不在集合中却误判的概率，即假正率
前提假设是选择的哈希函数足够好，即它们对任一元素均等概率映射到([1,m])中的某个值。
于是，对于初始化后的二进制向量，在对插入的元素进行计算时，一个哈希函数将某个位置设置为1的概率是(frac{1}{m})，所以该位置为0的概率是(1-frac{1}{m})。那么，经过(k)个哈希函数，某个位置仍然为0的概率显然是((1-frac{1}{m})^k)。又因为一共有(n)个元素需要进行插入操作，所以，将所有的元素进行运算之后，某个位置为0的概率是((1-frac{1}{m})^{nk})，显然，为1的概率就是(1-(1-frac{1}{m})^{nk})。
对于一个不在集合中的元素，得到“该元素在集合中”的错误结论的依据是该元素经过(k)个哈希函数的映射后所有位置上的值均为1，即：[p=(1-(1-frac{1}{m})^{nk})^k]
根据极限公式：(lim_{x to infty} left ( 1+frac{1}{x} right )^{x}=e)，当(mtoinfty)时，[p=(1-e^{-nk/m})^k]
4.2 最优选择
经过4.1的计算，可以看出(p)和(m,n,k)都有关系，于是，先假定(n/m)为定值时，求如何取(k)使(p)最小。
首先，(p)可以看做是(k)的函数，并假设(e^{-n/m}=b)对两边同时取对数可得：
[lnp(k)=k·ln(1-b^{k})]
所以，只需要求使(lnp(k))最小的(k)值即可。
两边对(k)求导数：
[frac{1}{p(k)}·{p}'(k)=ln(1-b^{k})+k·frac{1}{1-b^{k}}·(-1)·b^{k}ln(b)]
要取得最值，那么另导数为0可得：
[b^{k}ln(b^k)=(1-b^{k})·ln(1-b^{k})]
显然，(b^{k}=1/2)是它的解，因此满足条件的(k=log{_{b}}^{1/2})，化简后可得：[k=frac{m}{n}·ln2]
即，当集合元素个数与二进制向量长度的比值确定时，使假正率最小的哈希函数个数应满足上述要求。
进一步，若元素个数(n)已知（这通常是容易得到的），人为设置的假正率为(p)，那么根据上一步的结论，可以计算出至少需要多少长度的二进制向量才能达到我们的要求。将(k=frac{m}{n}·ln2)代入(p=(1-e^{-nk/m})^k)并化简，可得：
[lnp=-frac{m}{n}(ln2)^2]
即
[m=-frac{n·ln(p)}{(ln2)^2}]
所以，要想使建立的过滤器盛下(n)个元素，且假正率不超过(p)，那么二进制向量的长度最小需满足上述要求。基于这一点，就可以知道需要的存储空间有多大（8bit=1Byte，1024Byte=1KB）。
5. 两个实现此功能的Python包
最后，推荐两个实现布隆过滤器的Python包，一个是pybloom，另一个是pybloomfiltermmap，后者要比前者的速度更快，详细情况可以去看它们的主页说明。另外一点，原作者使用的Python均为2.x，不过有人在此基础性进行改写发布以适用Python3.x，包的名字分别是pybloom-mirror和pybloomfiltermmap3，直接去Pypi上搜索安装即可。
最后的最后，尽管pybloomfiltermmap3很快，但是编译的时候需要许多环境支持，至少我装起来非常麻烦，因此上传一个.whl文件，为64位Liunx下Python3.7版本的，如有需要，下面百度云链接自行下载。
链接：https://pan.baidu.com/s/1lXXIY_8XnU37uYEWGvEObQ
提取码：nz47
6. 参考内容
https://en.wikipedia.org/wiki/Bloom_filter
https://blog.csdn.net/houzuoxin/article/details/20907911
- 还没有人评论，欢迎说说您的想法！
客服
