BloomFilter布隆过滤器 简介
丈黑起恋秘
发表于 2022-12-2 10:19:44
106
0
0
布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。
布隆过滤器 (Bloom Filter)是一种space efficient的概率型数据结构,在垃圾邮件过滤的黑白名单方法、爬虫(Crawler)的网址判重模块中等等经常被用到。哈希表也能用于判断元素是否在集合中,但是布隆过滤器只需要哈希表的1/8或1/4的空间复杂度就能完成同样的问题。布隆过滤器可以插入元素,但不可以删除已有元素。其中的元素越多,false positive rate(误报率)越大,但是false negative (漏报)是不可能的。
基本概念
如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为 O(n),O(log n),O(n/k)。1 V( R# p! G( N8 ?3 V8 O$ a
布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。3 D, I; f" M. j L
算法描述8 J6 Q4 E- ]& A" V, Q
一个empty bloom filter是一个有m bits的bit array,每一个bit位都初始化为0。并且定义有k个不同的hash function,每个都以uniform random distribution将元素hash到m个不同位置中的一个。在下面的介绍中n为元素数,m为布隆过滤器或哈希表的slot数,k为布隆过滤器重hash function数。! ~9 f" o! W+ [; v; M& Y
为了add一个元素,用k个hash function将它hash得到bloom filter中k个bit位,将这k个bit位置1。
为了query一个元素,即判断它是否在集合中,用k个hash function将它hash得到k个bit位。若这k bits全为1,则此元素在集合中;若其中任一位不为1,则此元素比不在集合中(因为如果在,则在add时已经把对应的k个bits位置为1)。$ P3 `9 r. j# ^: ^7 A1 _5 X n; X+ [3 z
不允许remove元素,因为那样的话会把相应的k个bits位置为0,而其中很有可能有其他元素对应的位。因此remove会引入false negative,这是绝对不被允许的。
当k很大时,设计k个独立的hash function是不现实并且困难的。对于一个输出范围很大的hash function(例如MD5产生的128 bits数),如果不同bit位的相关性很小,则可把此输出分割为k份。或者可将k个不同的初始值(例如0,1,2, … ,k-1)结合元素,feed给一个hash function从而产生k个不同的数。6 r: }8 b/ m: ?# t
当add的元素过多时,即n/m过大时(n是元素数,m是bloom filter的bits数),会导致false positive过高,此时就需要重新组建filter,但这种情况相对少见。
优点, F$ s* t, {4 @2 f
相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数(O(k))。另外,散列函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。
布隆过滤器可以表示全集,其它任何数据结构都不能;
缺点
但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。/ b, B; p8 I% |* k
另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。
在降低误算率方面,有不少工作,使得出现了很多布隆过滤器的变种。
举例说明布隆过滤器的空间优势- U2 E" r% Q g$ p8 g0 N* w# c/ T
先来一个结论:对于一个有1%误报率和一个最优k值的布隆过滤器来说,无论元素的类型及大小,每个元素只需要9.6 bits来存储。这个优点一部分继承自array的紧凑性,一部分来源于它的概率性。如果你认为1%的误报率太高,那么对每个元素每增加4.8 bits,我们就可将误报率降低为原来的1/10。add和query的时间复杂度都为O(k),与集合中元素的多少无关,这是其他数据结构都不能完成的。k是hash函数的个数。2 d# A, y3 w4 ?5 }- w7 D0 m" n
举例: 现有1亿个email的黑名单,元素的数量(即email列表)为 108。若采用布隆过滤器,取k=8(k为hash函数个数)。因为n为1亿,所以总共需要8*108。又因为在保证误判率低(后面解释)且k和m选取合适时,空间利用率为50%(后面会解释),所以总空间为
# E' T- V4 s' i& S2 h3 e3 O7 t$ k
空间优势
所需空间比上述哈希结构或者数组小得多,并且误判率在万分之一以下。为什么可以这样算,可以看下面。
误判概率的证明和计算5 g2 E D. N" w$ \* f) P- F
该过程的详细说明来自于这个文章http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html,为了看懂求导过程,需要复习数学知识。1 V. N2 Z! I3 H$ l
对某一特定bit位在一个元素由某特定hash function插入时没有被置位为1的概率为:
- V) y5 a2 b* v, f# ?
则k个hash function中没有一个对其置位的概率为:
如果插入了n个元素,但都未将其置位的概率为:
$ |8 z* v+ x! Z0 t- b% r, ~
现在考虑query阶段,若对应某个待query元素的k bits全部置位为1,则可判定其在集合中。因此将某元素误判的概率为:% L% ~* v; n! w4 y# X* F
由于
1 Y3 P! c( t# m& d* L( \* O8 s; }
,并且1/m 当m很大时趋近于0,所以
现在计算对于给定的m和n,k为何值时可以使得误判率最低。设误判率为k的函数为:
7 r' g/ Y+ n; ?( i. N" n
设
$ R% u% B% D6 k7 a: Y/ ?2 [9 g2 I
则简化为
C0 Z: i1 X/ m2 Z. l( K7 B% B
因为等式右边的底数上是函数,指数上也是函数,没有方法求这样组合函数的导数,只能取对数之后,变成乘法。我们有两个函数相乘的求导方法,求导的几个方法可以看参考资料,有很好的视频说明。
两边取对数得
& p8 J1 q3 L0 |" F
两边对k求导得,这边涉及到乘法求导,对数求导,幂函数求导:- ^6 g) z& ?" |$ B8 d
下面求最值,
+ }. e' A2 D5 K% c0 y6 S
红圈中的等式是把两边看成xln(x)这种形式得到的,和该函数的单调性相关。数学上能不能这么操作我还不太清楚。数学好的大神可以留言解释一下。+ ]& q8 M6 `! u9 q4 o# M# g
因此,即当# y+ F. M% m2 f8 f' U4 J' q( `
1 E* o$ }2 ~4 }7 f" }# p7 L
时误判率最低,此时误判率为:- i" s1 m& u; E9 M8 H( P
可以看出若要使得误判率≤1/2,则:+ C8 v. p% ^/ q3 m. w1 l
$ N! ]; G$ v5 C' f& o
这说明了若想保持某固定误判率不变,布隆过滤器的bit数m与被add的元素数n应该是线性同步增加的。8 l9 B5 Y+ l6 [
设计和应用布隆过滤器的方法1 ^/ R4 V# N# L
应用时首先要先由用户决定要add的元素数n和希望的误差率P。这也是一个设计完整的布隆过滤器需要用户输入的仅有的两个参数,之后的所有参数将由系统计算,并由此建立布隆过滤器。
系统首先要计算需要的内存大小m bits:- K0 u% I. L2 M+ t( r( ?' M
再由m,n得到hash function的个数:7 F* x9 E* p$ F- Y6 I
至此系统所需的参数已经备齐,接下来add n个元素至布隆过滤器中,再进行query。" a) q ]' I' A' Q: I
根据公式,当k最优时:& [) M0 k6 ~9 O& U2 x- U
因此可验证当P=1%时,存储每个元素需要9.6 bits:6 W W+ b$ l+ R; B0 |0 j
1 y1 @8 O% v$ { [! E& v- P6 T+ ?( s
而每当想将误判率降低为原来的1/10,则存储每个元素需要增加4.8 bits:
* G- S5 }0 }. n& H" A6 H( C
这里需要特别注意的是,9.6 bits/element不仅包含了被置为1的k位,还把包含了没有被置为1的一些位数。此时的3 n6 n) W) L5 l8 O% O
才是每个元素对应的为1的bit位数。$ y( c% d. v6 y
5 T1 O Z7 t7 _5 g$ f8 e) j( j
从而使得P(error)最小时,我们注意到:
中的, t; r, c6 D% q
,即
* w( c: S$ V2 F* m) t# [/ g
此概率为某bit位在插入n个元素后未被置位的概率。因此,想保持错误率低,布隆过滤器的空间使用率需为50%。, P+ `, q. y% z5 }0 J6 U' U* f
Neo中的布隆过滤器/ r% m, s2 T# R3 P
上面的内容大部分抄袭http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html,原作者写的太好了,我只是加上一些我的理解,方便数学不好的道友理解。下面我们看看Neo中的Bloom Filter。2 v( a' P4 }6 s, A5 S- B
using System.Collections;6 Q- x' e# E3 r7 W3 C# S* J
using System.Linq;5 u! B' P9 Q# C w7 ]
namespace Neo.Cryptography' G% p0 K& d; O1 s9 l* F
{& x. A8 I4 Y @/ k- B" c0 ~/ m9 b
public class BloomFilter
{$ B3 T1 f1 x/ L' d/ ~
private readonly uint[] seeds;
private readonly BitArray bits;- c" t: M! [- {! _ t+ m
public int K => seeds.Length;) N; G0 U: L* k8 s* V/ _ Q! w: R
public int M => bits.Length;, h: m0 S9 j9 S, ^/ @2 C/ f
public uint Tweak { get; private set; }
public BloomFilter(int m, int k, uint nTweak, byte[] elements = null)
{1 T" H9 N0 ]* t" K; S
this.seeds = Enumerable.Range(0, k).Select(p => (uint)p * 0xFBA4C795 + nTweak).ToArray();/ _8 ]: [3 `( o4 [, }9 F
this.bits = elements == null ? new BitArray(m) : new BitArray(elements);: R9 J1 {4 q/ d7 D+ l
this.bits.Length = m; }# A. j# d# W7 [; r
this.Tweak = nTweak;! F! ?. H& ?( L/ N/ ^
}3 C# z. E8 p% Q) V% n/ [
public void Add(byte[] element)8 R( G: P; u+ G* ~* Q8 E4 r
{* R% I. n. _2 W# k+ x4 g) R
foreach (uint i in seeds.AsParallel().Select(s => element.Murmur32(s)))
bits.Set((int)(i % (uint)bits.Length), true);
}
public bool Check(byte[] element)
{" D. C/ [ V1 E5 T( |
foreach (uint i in seeds.AsParallel().Select(s => element.Murmur32(s)))
if (!bits.Get((int)(i % (uint)bits.Length)))
return false;0 |" a" i% ^! O! C. P
return true;
}" m. c# m7 S/ z, D
public void GetBits(byte[] newBits)
{0 P/ b. l) o& E( Y7 T1 d7 Z: g& }
bits.CopyTo(newBits, 0);
}
}
}
前面讲了这么多,代码竟然这么短,分析分析。+ D1 X4 i. a1 L ^' u% N
构造函数传入了m(多少位),k(hash函数种类),这个和我们前面分析根据p(错误率),和n(要插入的元素)来构造的思路不一样。所以Neo的这个版本应该是一个简化版本,输入的数据n应该是有范围的,具体的范围我们后面运行整个区块链的时候在观察,现在不知道n的个数有多大。hash函数使用了Murmur32,然后传入不同的seed模拟不同的hash函数,这个是可以的。使用linq,函数式编程代码非常简洁,这也是C#的一个优势啊。add,check函数都很容易看懂,确实实现很简洁。
总结' c6 H5 P( T. y1 P. _
Bloom Filter是牛逼的数据结构,因为有很多数学知识在里面,虽然代码不长,但是能看完这篇文章的人,会感受到代码之美。
成为第一个吐槽的人