实用的算法之布隆过滤

1. 什么是布隆过滤

布隆过滤（Bloom Filter）是布隆在 1970 年提出的一种数据结构。将元素（x、y、z）通过一系列函数，映射到一个二进制向量（0101 序列），用于快速判断元素 w 是否在一个集合当中。如下图（来自维基百科）:相较于使用单个映射函数，在相同的地址空间下，多个映射函数能降低冲突率。因此，在相同冲突率下，多个映射函数比单个映射函数需要的地址空间更少。Bloom Filter 使用很短的二进制向量，通过牺牲准确率获得了极高的空间利用率。在大规模数据查询场景下，能有效避免磁盘 IO，具有很高地查询效率。其实，用于判断一个元素是否在一个大集合中，还可以使用 Bitmap 。将元素转换成整数类型 x ，x 在 Bitmap 中的索引值为 0（代表不存在） 或者 1（代表存在）。Bloom Filter 和 Bitmap 有所类似，都是利用二进制向量和映射函数判断元素是否存在。不同的是，Bitmap 只有一个映射函数，向量大小不能小于最大的整数；Bloom Filter 具有多个映射函数，根据不同要求的误判率场景，可以选择不同大小的二进制向量。

2. 常见的应用场景

Bloom Filter 具有一定的误判率，主要解决一定不存在和可能存在两类问题。

2.1 一定不存在问题 - False

• 单词拼写检查。拼写错误的单词一定不存在
• 防止数据库穿库。查询不存在的行或者列
• 缓存穿透。没查询到缓存时，穿透到数据库

2.2 可能存在 - True

• 爬虫对 URL 去重。跳过已经抓取的 URL
• 垃圾邮件过滤。黑名单中的地址将被屏蔽
• 避免重复推荐文章。跳过已经阅读的文章 URL/ID
• Web 拦截器。拦截在黑名单中的 URL 地址

3. 布隆过滤的参数选择

上面提到 ，根据不同要求的误判率场景，布隆过滤可以选择不同大小的二进制向量。在生产过程中，我们需要平衡误判率和效率。下面是维基百科中给出的公式:k = (m/n) ln2其中，

• m 是二进制向量的大小
• n 是元素的数量
• k 是映射函数的个数
• ln2 是常数，约等于 0.69

下表是不同 m/n 和 k 下的误判率。

在使用时，首先确定一个可接受的误判率，然后根据公式计算出二进制向量的大小:m = (k * n) / ln2例如，选择 0.003 的误判率，k = 4，m/n = 15 。如果有 100 W 条记录，那么需要二进制向量大小为 ( 4 * 10e6 ) / 0.693 ≈ 5.77 * 10e6 bit = 704.6 KB 。

4. 布隆过滤的缺点

布隆过滤的主要缺点:

对布隆过滤的优化算法很多，无非就是增加信息的冗余，但从效率上都比不上布隆过滤。下面是几种同类算法:

• 计数布隆过滤(Counting Bloom Filter)

在标准布隆过滤的基础上，将每一个 Bit 改为一个计数器，增加一个元素时，计数加一，删除一个元素时，计数减一。

• Spectral Bloom Filters

上面的计数布隆过滤，计数器是固定位数的。Spectral Bloom Filters 的计数位是动态变化的，更加灵活，避免计数溢出。

• 压缩布隆过滤（Compressed Bloom Filters）

通过减少映射函数的数量，减少网络传输的 Bit 位。为了换取相同的误判率，二进制向量将会变大。

• D-left 计算布隆过滤（D-left Counting Bloom Filters）

基于 D-left Hashing ，减少了存储空间，降低了误判率，可以删除元素。

• Dynamic Counting Filters

支持查询元素的存储频率

• 布谷鸟过滤

布谷鸟算法不同于布隆过滤，而是模仿布谷鸟解决映射冲突问题。当不同元素因素到同一个映射位时，最后映射的元素会踢走之前映射的元素。布谷鸟算法支持删除操作，空间利用率只有 50 %，只存储元素的指纹信息，查询效率很高。

5. Go 语言实现

这里引用 github.com/willf/bloom ，对 Bloom Filter 进行简单测试。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

package main

import (
	"fmt"
	"github.com/willf/bloom"
)

func main() {
	n := uint(10000)
	error_rate := 0.003
	need_m, need_k := bloom.EstimateParameters(n, error_rate)
	fmt.Printf("Set m = %d , k = %d \n", need_m, need_k)
	filter := bloom.New(need_m, need_k)
	for i := 0; i < int(n); i++ {
		filter.Add([]byte(fmt.Sprintf("https://www.chenshaowen.com/%d", i)))
	}
	fmt.Println(filter.Test([]byte(fmt.Sprintf("https://www.chenshaowen.com/%d", 10000))))
	fmt.Printf("Done")
}

执行结果:

1
2
3

Set m = 120910 , k = 9 
false
Done

6. 参考

• http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
• https://en.wikipedia.org/wiki/Bloom_filter
• https://github.com/willf/bloom