Algorithm
Algorithm

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