`
daniel_tu
  • 浏览: 177848 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

布隆过滤器:Bloom Filter

阅读更多

Bloom Filter是由 Howard Bloom在 1970 年提出的一种多哈希函数映射的快速查找算法,包括一个很长的二进制向量和K个哈希函数。每个哈希函数将某元素映射成二进制向量中的某一位。

Bloom Filter常见的应用场景是判断某元素是否属于某个集合A。假设二进制向量共有M位,使用K个哈希函数,集合A的大小为N,其中M往往远大于K和N:

【1】首先需要事先将A中的每个元素被K个哈希函数映射的K个位全部赋为真,令相应位上的值等于1。例如下图表示的是M=16,K=2的Bloom Filter。集合A中只包含a和b,a和b的哈希值分别为(3, 6)和(10, 3),所以我们就将位3、6、10标记为真。

【2】然后,我们查看待查元素的哈希值。如果有一位不为真,那么这个元素肯定不在集合A中。如果该元素被K个哈希函数映射的K个位全部为真,那么我们认为这 元素在这一个集合中,这时存在一定的误判率。所谓误判(False Positive)就是某元素不在Bloom Filter中,但是它所有哈希值的位置均被设为真,我们仍认为集合包含该元素。例如,上一步中,我们的集合A中只含元素a和b,但我们的判断是d也在集 合A中,应为d的哈希值对应的位都为真。

Bloom Filter的优点是空间效率和查询时间都远远超过一般的算法,然而这种高效是有一定代价的:在判断一个元素是否属于某个集合时,虽然不可能把属于这个集 合的元素误判为不属于这个集合,但有可能会把不属于这个集合的元素误认为属于这个集合。下面我们看下这个误判率到底有多大。

  1. 一个元素被K次哈希后,该特定位仍然为0的概率为(1-1/M)K
  2. 在集合A的N个元素都被哈希完之后,该特定位为1的概率为1-(1-1/M)NK
  3. 判断一个元素是否属于这个集合,考察的是映射的K个位是否都是1。K个位都是1的概率,即误判率P为[1-(1-1/M)NK]K。当x趋于无穷大时,(1+1/x)= e,故误判率P=[1-(1-1/M)NK]K = (1-e-KN/M)K

那么对于给定的M、N,那么应该选择几个哈希函数才能使元素查询时的错误率P降到最低呢?数学上可以证明,当K为ln2*M/N,约为0.7*M/N时,误判率最小为P=0.5K=0.6185M/N。最小值往往不能达到,因为实际中K为整数。

 

在不同M/N和K的情况下,误判率的概率情况详见这里

BloomFilter的Python是实现详见这里

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics