Bloom Filter

最近学习中老师总是提到Bloom Filter,但一直都没系统学过,今天花点时间仔细研究一下。


基本概念

当一个元素被加入到集合中时,通过K个散列函数将这个元素映射成一个位数组中的K个点,并将这些点置位1,当检索时只要检查这些散列点是否全为1就可以判断集合中有没有这个元素了。

  • 优点:
    1. 空间效率,时间效率都是(O(k))
    2. 可以表示全集,其他数据结构均不能表示全集
  • 缺点:
    1. 有一定误识别率
    2. 很难将元素从集合中删除

算法描述

元素加入

  1. 创建一个m位的二进制串并将每一位都初始化为0,选择k个不同的哈希函数
  2. 利用相互独立的哈希函数将集合中的每一个元素映射到{1...m}的范围当中,对于元素x,第i个哈希函数映射的位置hi(x) = 1,其中 1<=i<=k。如果一个位置被多次映射,那么只有第一次置位1,后面的不起作用。

下图中m = 18, k = 3。 维基百科

元素查询

  1. 对查询元素y应用k次哈希函数
  2. 如果所有hi(y) = 1,那么y是集合中元素,否则不是

错误率估计

由算法可知,所有元素通过k个哈希函数哈希后,二进制串中某一位还为0的概率是
p' = (1-1/m)kn
错误率则可以表示成k次哈希都刚好选中1的区域(false positive rate),表示成下面的公式
(1-p')k

基本Bloom Filter的内容就这样了,详细的扩展内容包括最优哈希函数,位串的选取可以参看维基百科,总的来说还是相当简单易用的一种数据结构,在数据挖据等方面使用较为广泛。