因为要做过滤器相关内容,最近读了一些过滤器方面的文章,准备从中提取主要思想写几篇博客。

作为这系列的第一篇文章,首先得讲一下过滤器是干什么用的。从历史发展来看,过滤器最早出现是作为散列表的替代品,那么功能就要和散列表差不多,主要是查询当前的元素是否在我已知的集合里。但是随着数据量不断增大,散列表相对来说占用空间过大,而空间占用小的查找树的$O(logn)$时间复杂度又太高。于是有人想出来能否用正确率做代价,换取较高的查询速度和较小的存储占用,这就是过滤器。当然,这里所允许的错误仅限假阳性,例如我们做一个关于代理ip地址的过滤器,当有一个不是代理的ip地址发来,我们也许会把它错认成是代理ip,但是我们不会允许一个代理ip被错认成非代理ip,简单的说,就是宁可错杀,不可放过。

作为第一篇,按照历史角度,先说布隆过滤器(bloom filter)。原版的布隆过滤器很朴素,只支持插入和查询两个操作,下面我们看它的原理。

首先,布隆过滤器申请了一片空间,存了一个数组,每个元素都只有1个bit,共有N个元素,初始化每个值都为0。如下图所示。(实际并没有index这一行,仅仅是为了方便观看) image1

插入操作

下一步就是如何插入数据。布隆过滤器要求你事先定义K个Hash函数,这K个Hash函数都是从定义域映射到上图中的index空间(即N)。通过这K个Hash函数,我们对一条新的数据x,计算出$h_0(x),h_1(x),….h_{k-1}(x)$,这样就得到了K个地址。我们将这K个地址的比特位置1.这里就有值得注意的地方,因为我们的过滤器的大小远远小于数据集大小,那么常常会有Hash之后映射到同一个位置的数据,不要担心,照常置1。

下面的例子是K=3,$h_0(x)=2,h_1(x)=5,h_2(x)=7$。如图所示 image2

查找操作

当插入其他一些数据后,过滤器可能变成下图所示,我们不关心中间经历了什么。

image3 我们现在查找刚才第一次插入的数据是否在过滤器中,那么同样计算$h_0(x),h_1(x),h_2(x)$,算出3个地址,2,5,7,去表中查找,若3个地址的数据都为1,则判断在过滤器中,否则判断不在过滤器中。

算法和数据结构都很简单,我们下面说的是对布隆过滤器的一些分析和题外话,有兴趣的读者可以继续阅读。

我们在过滤器上很关注三个指标,一个是操作的时间复杂度,一个是平均每条数据占用的比特数,最后是错误率。下面我们分析一下。

时间复杂度

布隆过滤器上的两个操作,插入和查询,都只是计算一下K个Hash函数的值,然后进行K次访存操作。那么时间上很明显是$O(K)$,其实不算也知道,一个替代Hash表的过滤器,操作代价必须是常数级别。

平均每条数据占用的比特数 and 错误率

直觉上,很容易得出这两个衡量指标其实是矛盾的,当想要较低错误率时就要增大空间;想要减小占用空间时,那么由于Hash碰撞的次数变多,错误率也会提高。我们在这里将错误率作为已知来计算平均每条数据占用的比特数。为什么这么做?因为在实际应用中我们可以对过滤器设定一个错误率作为标准,通常情况下我们对这一点要求更严格。

我们设数组总大小为$N$,插入n条数据后表中还为0的数据占全部的比例为$\phi$。那么

$\phi = (1-K / N)^n$————————-(1)

读者可以想想为什么不是$K * n / N$,在这里,我们其实省略了Hash函数默认是随机分布到全空间的。

设错误率为$P$,

$P = (1-\phi)^K$ —————————-(2)

错误只发生随机分布到K个地址,结果在K个地址都有数据用了,那么不管你是否在过滤器中,布隆过滤器都会判断你在其中,这就是错误来源。

然后我们对(1)式两边取对数

$log_2^\phi = log_2^{(1-K/N)^n}$

使用换底公式

$log_2^\phi = log_2^{(1-K/N)^n} = log_e^{(1-d/N)^n} * log_2^e = -n * K / N *log_2^e$ —(3)

我们要求的平均每条数据占用的比特数$N(bit) / n = log_2^{1/P} * log_2^e / (log_2^\phi * log_2^{(1-\phi)})$,通过极值点计算可以得到分母最大时,$\phi=0.5$,分母为1,则结果为$N/n = log_2^{1/P} / ln2$

可以看到,每条数据占用的比特数与错误率的对数成反比。

之后我会先把几个不同思想的过滤器介绍一遍,最后会有关于布隆过滤器的一些变形