【布隆过滤器】过滤器中的战斗机

转载请表明出处

背景

对 布隆过滤器 画个重点,它应该在 “过滤” 二字上,这个算法的重点在于把曾经来过跟从未来过的事物区分开,具体过滤那种事物(曾经来过or从未来过),由具体场景决定。它一般用于数据库存储中过滤不存在的行(减少访问磁盘),推荐系统去重等等场景。

SET

说到去重,很容易想到STL中的SET容器,它本身自带去重功能,而且还能查询。
那么最简单的方式,直接用SET。每次操作的时候,先查询该事物是否存在?

  • 如果存在直接返回“存在”结果。
  • 如果不存在就插入其中,然后再返回“不存在”结果。

具体如下图所示:

【布隆过滤器】过滤器中的战斗机

这种方式准确率是绝对准确的,但是这种方式耗费的内存也是巨大的。
假设每个事物需要 K 字节,那么如果有 M 个事物,一共需要 K * M 字节。那么我们能不能缩小这里的内存呢?
稍微损失一点准确率换取内存?具体见下面HashMap的方式

HashMap

在上一种方式中,它存储了具体的事物信息,其实在我们这个场景中是不需要的。我们需要的只是这个事物是否存在就行了,所以HashMap的方式诞生了。
这种算法在每次操作的时候,先查询该事物是否存在,

  • 如果存在返回“存在”结果。
  • 如果不存在就在特定位置置1,然后再返回“不存在”结果。

【布隆过滤器】过滤器中的战斗机

众所周知,hash都是有一定概率冲突的,而且当哈希桶快满的时候,冲突率更高。
接下来我们来看看这里的冲突率有多少?假设哈希桶长度为M,那么每次插入到特定一个桶的概率是:$$(1-\frac{1}{M})$$
而没有插入特定桶的概率是:$$1-(1-\frac{1}{M})$$
然后假设目前已经插入N个事物,那么特定桶中为0的概率是:$$(1-\frac{1}{M})^N$$
特定桶中为1的概率是:$$1-(1-\frac{1}{M})^N$$

假设现在要新插入一个事物,这次插入的冲突率就是:

\[1-(1-\frac{1}{M})^N = 1- ((1+\frac{1}{-M})^{-M})^{-\frac{N}{M}} \approx 1 - e^{-\frac{N}{M}} \]

所以这里在N接近M的时候,冲突率是很高的,这种算法就完全失效了。
有没有办法解决这种情况呢?布隆过滤器能降低这里冲突率。

布隆过滤器

布隆过滤器是用了多hash的方式降低了冲突率的。
这种算法在每次操作的时候,先查询该事物在K个hash桶中是否都存在,

  • 如果存在返回“存在”结果。
  • 如果有一个桶不存在,就在K个hash桶中全部置1,然后再返回“不存在”结果。

【布隆过滤器】过滤器中的战斗机

接下来我们来看看这种有K个Hash加持的算法,冲突率有多少?假设哈希桶长度为M,那么每次插入到特定一个桶的概率是:$$K (1-\frac{1}{M})$$
而没有插入特定桶的概率是:$$(1-(1-\frac{1}{M}))^K$$
然后假设目前已经插入N个事物,那么特定桶中为0的概率是:$$(1-\frac{1}{M})^{NK}$$
特定桶中为1的概率是:$$1-(1-\frac{1}{M})^{NK}$$
假设现在要新插入一个事物,这次插入的冲突率就是:

\[(1-(1-\frac{1}{M})^{NK})^K= (1- ((1+\frac{1}{-M})^{-M})^{-\frac{NK}{M}} )\approx (1 - e^{-\frac{NK}{M}})^K \]

由于这里有K次方的加持,它的冲突率小很多的。
一般来说,在使用布隆过滤器的时候,N是由场景已经决定了的,怎么选择M跟K呢?
P为冲突率

\[M=-\frac{NlnP}{(ln2)^2} \]

\[K=\frac{M}{N}ln2 \]

由于布隆过滤器都是直接置1,所以它根本无法删除一个事物的。有没有办法支持它删除+统计个数呢?

布隆过滤器升级版

想要删除特定事物,那其实也很简单。
直接把布隆过滤器的位存储改成数字存储就行了。
那么在每次操作的时候,跟布隆过滤器差别的点在于:

  • 无论是否存在都在K个hash桶中加1,
  • 然后在需要删除的时候,就在K个hash桶中减1。
    具体如下图所示:
    【布隆过滤器】过滤器中的战斗机

这种算法是已经支持删除+统计了,相应的它的内存占用可不是翻倍这么简单的。
不同的场景用不同的算法吧,最合适的才是效果最好滴。

发表评论

相关文章