布隆过滤器【1】

布隆过滤器

 

     最近一直在看美剧《犯罪心理》，剧中的BAU小组每次都要从茫茫人海中找到真正的凶手，这跟我们要在庞大的数据库中找到一个数据的感觉很相似。

     就拿最简单的来说，全世界70多亿人口，每个人的指纹都是独一无二的，当把每个人的指纹信息整合起来，必定是一个庞大的数据库。假设现在从现场采集到一枚指纹，我们可以用电脑通过对这枚指纹的几个“特征点”进行扫描，然后用“特征点”的信息来筛选数据库中的指纹信息，可以这样减轻繁琐的对比工作，随着特征点数量的增加，其检索的正确率也会大大提高。这样的检索方式不仅可以减少信息的存储空间，也提高了信息检索的速度。布隆过滤器也和这样的过程极为相似。

     布隆过滤器，简单来说，就是位数组+K个哈希函数，那么它就同时继承了位图和哈希表两者的优点，不仅节省空间，而且查找快速，缺点就是，存在一定的误判率。

     继续用指纹识别这个例子来说明布隆过滤器的原理。假设，我们存储了全国大学生的指纹信息，那么首先，我们需要建立一个很长的二进制向量，即一个位数组，把所有的位都设为0。然后使用K个哈希函数对指纹信息进行计算存储，得到特征点S1,S2,S3,...Sk，再把这些特征点映射到位数组中的K个位置，把这些位置上的0置为1，当我们把所有人的指纹信息都通过这样的方式处理过之后，一个针对指纹信息的布隆过滤器就做好了。接下来，让我们看看这个布隆过滤器是如何检测一个未知指纹X是否在数据库中的吧！首先，用相同的K个哈希函数指纹X进行计算，同样得到K个特征点分别为X1,X2,...Xk，再将这K个数映射到布隆过滤器中的K个位置，如果指纹X在数据库中，那么其映射的K个位置上的位一定是1。那么任何存在于这个指纹库中的指纹都能被检查出来。

 

     这样的例子还是不够具体，那么就举一个简单的实例，比如说有集合M=｛2，4，5，6，3，2，7｝，现在我们要用布隆过滤器来判断这个集合中是否存在重复的数字，首先，我们建立一个位数组BitSet[]，根据集合元素的数值，位数组设为8位，并使其各位都为0，如下图所示：

 

BitSet[0]	BitSet[1]	BitSet[2]	BitSet[3]	BitSet[4]	BitSet[5]	BitSet[6]	BitSet[7]
0	0	0	0	0	0	0	0

 

接下来使用一个哈希函数来对集合M进行存储，H(k)=k，即，2对应位数组第2位BitSet[1]，4对应第四位BitSet[3]……在对应位上置1，其余位上的仍为0，

如下图所示：

 

位数组	0	1	1	1	1	1	1	0
M		2	3	4	5	6	7

 

通过计算发现，当集合M中的第6个元素“2”出现时，其对应的位数组上的BitSet[1]=1，由此可以判断，元素“2”重复。

由这个简单的例子应该可以大概了解布隆过滤器的基本原理。

    【不知道我自己的理解对不对啊，请多多指教啦！】

     明天写一个揪出垃圾邮件的简单布隆过滤器，到时候再把代码PO上来和小伙伴们交流吧~

<!--EndFragment-->

评论

2 楼 javafound 2014-05-06  

期待！

1 楼 qindongliang1922 2014-05-06  

good !