Press "Enter" to skip to content

实用的算法之布隆过滤

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

布隆过滤(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/nkk=1k=2k=3k=4k=5k=6k=7k=8
21.390.3930.400
32.080.2830.2370.253
42.770.2210.1550.1470.160
53.460.1810.1090.0920.0920.101
64.160.1540.08040.06090.05610.05780.0638
74.850.1330.06180.04230.03590.03470.0364
85.550.1180.04890.03060.0240.02170.02160.0229
96.240.1050.03970.02280.01660.01410.01330.01350.0145
106.930.09520.03290.01740.01180.009430.008440.008190.00846
117.620.08690.02760.01360.008640.00650.005520.005130.00509
128.320.080.02360.01080.006460.004590.003710.003290.00314
139.010.0740.02030.008750.004920.003320.002550.002170.00199
149.70.06890.01770.007180.003810.002440.001790.001460.00129
1510.40.06450.01560.005960.0030.001830.001280.0010.000852
1611.10.06060.01380.0050.002390.001390.0009350.0007020.000574
1711.80.05710.01230.004230.001930.001070.0006920.0004990.000394
1812.50.0540.01110.003620.001580.0008390.0005190.000360.000275
1913.20.05130.009980.003120.00130.0006630.0003940.0002640.000194
2013.90.04880.009060.00270.001080.000530.0003030.0001960.00014
2114.60.04650.008250.002360.0009050.0004270.0002360.0001470.000101
2215.20.04440.007550.002070.0007640.0003470.0001850.0001127.46e-05
2315.90.04250.006940.001830.0006490.0002850.0001478.56e-055.55e-05
2416.60.04080.006390.001620.0005550.0002350.0001176.63e-054.17e-05
2517.30.03920.005910.001450.0004780.0001969.44e-055.18e-053.16e-05
26180.03770.005480.001290.0004130.0001647.66e-054.08e-052.42e-05
2718.70.03640.00510.001160.0003590.0001386.26e-053.24e-051.87e-05
2819.40.03510.004750.001050.0003140.0001175.15e-052.59e-051.46e-05
2920.10.03390.004440.0009490.0002769.96e-054.26e-052.09e-051.14e-05
3020.80.03280.004160.0008620.0002438.53e-053.55e-051.69e-059.01e-06
3121.50.03170.00390.0007850.0002157.33e-052.97e-051.38e-057.16e-06
3222.20.03080.003670.0007170.0001916.33e-052.5e-051.13e-055.73e-06

 

在使用时,首先确定一个可接受的误判率,然后根据公式计算出二进制向量的大小:

 

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. 布隆过滤的缺点

 

布隆过滤的主要缺点:

 

 

    1. 无法删除元素。因为一个二进制向量位,可能对应多个元素的映射,不能直接将其置 0 。

 

    1. 只适用于单机系统,内存开销随数据规模成线性关系。目前已经有一些中间件提供了布隆过滤,比如 Redis ,可以用于超大规模数据的场景。

 

 

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

计数布隆过滤(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 进行简单测试。

 

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")
}

 

执行结果:

 

Set m = 120910 , k = 9 
false
Done

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注