论文部分内容阅读
摘 要：Bloom Filter是一种空间和时间效率很高的二进制项量数据结构，它利用位数组很简单地表示一个集合，并能检索一个元素是否属于这个集合。Bloom Filter的高效检索是由有一定误报率换来的。因此，Bloom Filter只适合那些允许一定误报率的应用场合。
关键词：Bloom Filter 哈希函数 漏报 误报
中图分类号：TP311.12 文献标识码：A 文章编号：1672-3791（2013）04（a）-0011-01
1 Bloom Filter
Bloom Filter（布隆过滤器）是1970年由Howard Bloom提出的一个很长的二进制向量数据结构。布隆过滤器可以用于查询一个元素是否在某集合中。由于Bloom Filter在空间效率、查询效率以及安全性上的优势明显，因此被广泛的应用于各种需要查询的场合中，如Oracle的数据库，Google的Bit Table，web cache共享，拼写检查等都用了此技术。
2 Bloom Filter原理
假如要想判断一个元素是不是在某一个集合中，一般情况想到的是将所有元素保存起来，然后通过比较来确定。链表，树等数据结构就是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大，利用这种思路去检索查找，效率也会越来越低。
工作效率低下让人难以容忍，这时候我们可以考虑利用哈希表哈希函数这个数据结构。哈希函数在计算机领域，尤其是数据快速查找领域，加密领域用的极广。其作用是将一个大的数据集映射到一个小的数据集上面。哈希表是根据哈希值（Key value）而直接进行访问的数据结构。也就是说，它通过把哈希值映射到表中一个位置来访问记录，以加快查找的速度。或者也可以认为哈希表是通过一个Hash函数将一个元素映射到一个位阵列（Bit array）中的一个点。这样就简单了，只要看阵列中这个点是不是1就知道判断出他在不在集合中了。这实际上就是Bloom Filter的基本思路。
虽然了解了Bloom Filter的基本思路但是其中要用到哈希函数，哈希函数有个很大的问题就是冲突，那么在Bloom Filter算法是怎么解决的呢？那就是在其中用多个哈希函数来解决判断一个元素，只要有一个函数判断说该元素不在此集合中那么它肯定就不在此集合中。但也有一种可能就是其中的所有函数都说该元素在此集合中，但实际上它并不在其中，这种情况是从在的，但是概率非常低。那就是它的效率很高了。我们把这种有多个哈希函数组成的数据结构称为Bloom Filter。
下面我们举一简单的例子来看Bloom Filter是如何工作的。
Bloom Filter是一个包含n位的位数组，初始化时每一位都置为0。存在一个具有m个元素的集合W={x1，x2，…，xm}和k个最优的相互独立的哈希函数。我们利用k{h1，h2，…hk}个哈希函数把它们分别将W集合中的每个元素映射到位数组{1，…，n}的范围中。对任意一个W集合中的元素x，第i（1≤i≤k）个哈希函数映射的位置hi（x）就会被置为1。注意，如果同一个位置多次被置为1，那么只有第一次是起作用的，后面几次置位将没有任何效果。
如果n=20，k=3，W=（1，2），要判断3是否在W集合中的示意图（如图1）。
首先需要把位数组通过集合元素和哈希函数的运算来置位为1，如图1。
然后，我们开始判断3是否在w集合中。3与所有的k中的哈希函数进行运算，去看运算结果对应的位数组中的值是否为1，如果都为1则它在w中，如果有一个结果不为1，则它不在w中。图2所示是3不在集合w中，但如果碰巧3是一个误报那么就如图3所示了。
从上面的例子可以看出Bloom Filter存在误报的可能性还是比较大的，那么怎样能使这种误报率降到最低呢？从原理上可以看出Bloom Filter要靠多个哈希函数将集合映射到位数组中，那么哈希函数的个数和位数组的位数都会影响到误报率。在哈希函数方面存在一下两种情况：一是如果哈希函数的个数多，那么在对一个不属于集合的元素进行查询时得到0的概率就大，也就是误报率低；另外，如果哈希函数的个数少，那么位数组中的0就多。
3 Bloom Filter特点
优点：由于它的插入时间和查询时间都是常数因此具有很高的空间效率和查询效率；在查询过程中查询元素不被保存具有良好的安全性；不存在漏报（False Negative），即某个元素在某个集合中，肯定能报出来。
缺点：误识别率随着插入元素的增加而递增；任意元素都不能随意删除，删除将影响多个元素检测；可能存在误报（False Positive），即某个元素不在某个集合中，可能也被报出来。
4 结语
在计算机科学中，我们常常为了提高效率会碰到拿时间换空间或者空间换时间的情况。而Bloom Filter在时间和空间之外又引入了误识别率。在使用Bloom Filter判断一个元素是否属于某个集合时，会有一定的误识别率。Bloom Filter用少量的无识别率换来了时间和空间上的效率。自从70年代问世Bloom Filter之后，Bloom Filter就被广泛用于拼写检查和数据库系统中。随着网络的普及和发展，Bloom Filter在网络领域获得了更为广泛的应用，各种Bloom Filter的优化变种和新的应用不断涌现，在将来，Bloom Filter必将获得更大的发展。
参考文献
[1] 肖明忠，代亚非.Bloom Filter及应用综述[J].计算机科学，2004，31（4）.
[2] 谢鲲，文吉刚，张大方，等.布鲁姆过滤器查询算法[J].软件学报，2009，20（1）.
关键词：Bloom Filter 哈希函数 漏报 误报
中图分类号：TP311.12 文献标识码：A 文章编号：1672-3791（2013）04（a）-0011-01
1 Bloom Filter
Bloom Filter（布隆过滤器）是1970年由Howard Bloom提出的一个很长的二进制向量数据结构。布隆过滤器可以用于查询一个元素是否在某集合中。由于Bloom Filter在空间效率、查询效率以及安全性上的优势明显，因此被广泛的应用于各种需要查询的场合中，如Oracle的数据库，Google的Bit Table，web cache共享，拼写检查等都用了此技术。
2 Bloom Filter原理
假如要想判断一个元素是不是在某一个集合中，一般情况想到的是将所有元素保存起来，然后通过比较来确定。链表，树等数据结构就是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大，利用这种思路去检索查找，效率也会越来越低。
工作效率低下让人难以容忍，这时候我们可以考虑利用哈希表哈希函数这个数据结构。哈希函数在计算机领域，尤其是数据快速查找领域，加密领域用的极广。其作用是将一个大的数据集映射到一个小的数据集上面。哈希表是根据哈希值（Key value）而直接进行访问的数据结构。也就是说，它通过把哈希值映射到表中一个位置来访问记录，以加快查找的速度。或者也可以认为哈希表是通过一个Hash函数将一个元素映射到一个位阵列（Bit array）中的一个点。这样就简单了，只要看阵列中这个点是不是1就知道判断出他在不在集合中了。这实际上就是Bloom Filter的基本思路。
虽然了解了Bloom Filter的基本思路但是其中要用到哈希函数，哈希函数有个很大的问题就是冲突，那么在Bloom Filter算法是怎么解决的呢？那就是在其中用多个哈希函数来解决判断一个元素，只要有一个函数判断说该元素不在此集合中那么它肯定就不在此集合中。但也有一种可能就是其中的所有函数都说该元素在此集合中，但实际上它并不在其中，这种情况是从在的，但是概率非常低。那就是它的效率很高了。我们把这种有多个哈希函数组成的数据结构称为Bloom Filter。
下面我们举一简单的例子来看Bloom Filter是如何工作的。
Bloom Filter是一个包含n位的位数组，初始化时每一位都置为0。存在一个具有m个元素的集合W={x1，x2，…，xm}和k个最优的相互独立的哈希函数。我们利用k{h1，h2，…hk}个哈希函数把它们分别将W集合中的每个元素映射到位数组{1，…，n}的范围中。对任意一个W集合中的元素x，第i（1≤i≤k）个哈希函数映射的位置hi（x）就会被置为1。注意，如果同一个位置多次被置为1，那么只有第一次是起作用的，后面几次置位将没有任何效果。
如果n=20，k=3，W=（1，2），要判断3是否在W集合中的示意图（如图1）。
首先需要把位数组通过集合元素和哈希函数的运算来置位为1，如图1。
然后，我们开始判断3是否在w集合中。3与所有的k中的哈希函数进行运算，去看运算结果对应的位数组中的值是否为1，如果都为1则它在w中，如果有一个结果不为1，则它不在w中。图2所示是3不在集合w中，但如果碰巧3是一个误报那么就如图3所示了。
从上面的例子可以看出Bloom Filter存在误报的可能性还是比较大的，那么怎样能使这种误报率降到最低呢？从原理上可以看出Bloom Filter要靠多个哈希函数将集合映射到位数组中，那么哈希函数的个数和位数组的位数都会影响到误报率。在哈希函数方面存在一下两种情况：一是如果哈希函数的个数多，那么在对一个不属于集合的元素进行查询时得到0的概率就大，也就是误报率低；另外，如果哈希函数的个数少，那么位数组中的0就多。
3 Bloom Filter特点
优点：由于它的插入时间和查询时间都是常数因此具有很高的空间效率和查询效率；在查询过程中查询元素不被保存具有良好的安全性；不存在漏报（False Negative），即某个元素在某个集合中，肯定能报出来。
缺点：误识别率随着插入元素的增加而递增；任意元素都不能随意删除，删除将影响多个元素检测；可能存在误报（False Positive），即某个元素不在某个集合中，可能也被报出来。
4 结语
在计算机科学中，我们常常为了提高效率会碰到拿时间换空间或者空间换时间的情况。而Bloom Filter在时间和空间之外又引入了误识别率。在使用Bloom Filter判断一个元素是否属于某个集合时，会有一定的误识别率。Bloom Filter用少量的无识别率换来了时间和空间上的效率。自从70年代问世Bloom Filter之后，Bloom Filter就被广泛用于拼写检查和数据库系统中。随着网络的普及和发展，Bloom Filter在网络领域获得了更为广泛的应用，各种Bloom Filter的优化变种和新的应用不断涌现，在将来，Bloom Filter必将获得更大的发展。
参考文献
[1] 肖明忠，代亚非.Bloom Filter及应用综述[J].计算机科学，2004，31（4）.
[2] 谢鲲，文吉刚，张大方，等.布鲁姆过滤器查询算法[J].软件学报，2009，20（1）.