Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

BloomFilter布隆过滤器 简介

丈黑起恋秘
147 0 0
布隆过滤器
, k8 s6 t7 R& R% Y5 s$ L布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。
* _& p6 x0 Z# N: ~' M布隆过滤器 (Bloom Filter)是一种space efficient的概率型数据结构,在垃圾邮件过滤的黑白名单方法、爬虫(Crawler)的网址判重模块中等等经常被用到。哈希表也能用于判断元素是否在集合中,但是布隆过滤器只需要哈希表的1/8或1/4的空间复杂度就能完成同样的问题。布隆过滤器可以插入元素,但不可以删除已有元素。其中的元素越多,false positive rate(误报率)越大,但是false negative (漏报)是不可能的。0 `+ M+ }! J. t* e1 k
基本概念2 r+ }& V8 S* v: I2 e9 e/ N
如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为 O(n),O(log n),O(n/k)。$ B  F0 S3 D: d! w/ v; }9 `5 ?
布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。) [3 O/ H4 i3 B4 r5 s- F( _0 D
算法描述2 o3 T+ Q$ n( P
一个empty bloom filter是一个有m bits的bit array,每一个bit位都初始化为0。并且定义有k个不同的hash function,每个都以uniform random distribution将元素hash到m个不同位置中的一个。在下面的介绍中n为元素数,m为布隆过滤器或哈希表的slot数,k为布隆过滤器重hash function数。+ [' ?3 i* X8 V' k4 @) Y. @" P
为了add一个元素,用k个hash function将它hash得到bloom filter中k个bit位,将这k个bit位置1。% W$ l- u5 X9 Y* \
为了query一个元素,即判断它是否在集合中,用k个hash function将它hash得到k个bit位。若这k bits全为1,则此元素在集合中;若其中任一位不为1,则此元素比不在集合中(因为如果在,则在add时已经把对应的k个bits位置为1)。% @2 z, b; I( ?# x: B* L  W' W
不允许remove元素,因为那样的话会把相应的k个bits位置为0,而其中很有可能有其他元素对应的位。因此remove会引入false negative,这是绝对不被允许的。' T* r: r$ p  L6 z0 p9 N
当k很大时,设计k个独立的hash function是不现实并且困难的。对于一个输出范围很大的hash function(例如MD5产生的128 bits数),如果不同bit位的相关性很小,则可把此输出分割为k份。或者可将k个不同的初始值(例如0,1,2, … ,k-1)结合元素,feed给一个hash function从而产生k个不同的数。
( q7 {2 m, h$ F( H当add的元素过多时,即n/m过大时(n是元素数,m是bloom filter的bits数),会导致false positive过高,此时就需要重新组建filter,但这种情况相对少见。5 s, b8 k) M. Q& Y) p8 w0 R
优点
7 ~3 @- ?) k7 S" r2 c  }1 Z, \相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数(O(k))。另外,散列函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。
2 z+ v) N- s, k! V' u布隆过滤器可以表示全集,其它任何数据结构都不能;/ n: i& x4 \9 M* ~( o9 t8 S+ t
缺点) j3 B% }6 c! }, B4 Z/ r& _+ s" G5 M
但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。/ i9 @' J& y  A: c+ @' @+ E
另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。
" \8 {% x2 }  H/ W) r在降低误算率方面,有不少工作,使得出现了很多布隆过滤器的变种。
6 S" ?* x) Y* c% F9 _3 t6 s  v举例说明布隆过滤器的空间优势3 [  z2 m: c! W, h  n3 z6 Z
先来一个结论:对于一个有1%误报率和一个最优k值的布隆过滤器来说,无论元素的类型及大小,每个元素只需要9.6 bits来存储。这个优点一部分继承自array的紧凑性,一部分来源于它的概率性。如果你认为1%的误报率太高,那么对每个元素每增加4.8 bits,我们就可将误报率降低为原来的1/10。add和query的时间复杂度都为O(k),与集合中元素的多少无关,这是其他数据结构都不能完成的。k是hash函数的个数。' L/ y9 ^# w5 _% m* Y; C
举例: 现有1亿个email的黑名单,元素的数量(即email列表)为 108。若采用布隆过滤器,取k=8(k为hash函数个数)。因为n为1亿,所以总共需要8*108。又因为在保证误判率低(后面解释)且k和m选取合适时,空间利用率为50%(后面会解释),所以总空间为( X6 q- e2 x, i/ A3 n) ]) o! Y& G
) n3 Z$ }4 t0 _7 R' t$ M, T
空间优势
. Q! Q+ j& w1 A所需空间比上述哈希结构或者数组小得多,并且误判率在万分之一以下。为什么可以这样算,可以看下面。* ?$ @+ J6 Q& H5 ?! X0 A9 ]
误判概率的证明和计算
+ w- q: {/ b+ ~! v/ B' w该过程的详细说明来自于这个文章http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html,为了看懂求导过程,需要复习数学知识。
  a' F+ G) G9 b对某一特定bit位在一个元素由某特定hash function插入时没有被置位为1的概率为:
3 C. |0 z5 B' n; i) ~; c
. e5 M6 i% f, I6 I则k个hash function中没有一个对其置位的概率为:3 l% Y" L% S& L% a

% ~& y0 r, y$ w# F: D* A如果插入了n个元素,但都未将其置位的概率为:
5 H2 h& B$ ^, x5 y2 L  I& E. g/ W+ F- g; z/ L1 i1 r
现在考虑query阶段,若对应某个待query元素的k bits全部置位为1,则可判定其在集合中。因此将某元素误判的概率为:9 v$ {- L8 a7 w& A+ h7 `/ l" I' u5 q3 T
. d- g1 J; a& q. t
由于7 q, _  C' f6 I4 \
1 Z" y4 c" q8 V9 w4 V
,并且1/m 当m很大时趋近于0,所以
8 Z- q0 l/ i3 F* j: A. f现在计算对于给定的m和n,k为何值时可以使得误判率最低。设误判率为k的函数为:+ }. F4 ]. L3 {; z

  i+ F! O* d0 @& j. I& M3 V
. L# U7 D2 D- D9 G; y1 }( D7 U
- L. X$ k6 T- O" V+ \0 u则简化为
& k! G. Y. \6 R' Y9 r, b: @$ P* k, P9 ~8 }4 |2 V/ r
因为等式右边的底数上是函数,指数上也是函数,没有方法求这样组合函数的导数,只能取对数之后,变成乘法。我们有两个函数相乘的求导方法,求导的几个方法可以看参考资料,有很好的视频说明。
& s' W, f/ ^3 M  R0 }2 O两边取对数得
5 p% V: o+ N  ]% ~6 c1 K: ~- Q, a
两边对k求导得,这边涉及到乘法求导,对数求导,幂函数求导:8 _4 \' u  f4 S9 V! _# }

0 K8 j5 u1 ?: }/ \. a2 D下面求最值,  W& O* T7 N" ?8 K6 X' u" q

  G7 A$ V  M0 [3 t6 y" O红圈中的等式是把两边看成xln(x)这种形式得到的,和该函数的单调性相关。数学上能不能这么操作我还不太清楚。数学好的大神可以留言解释一下。
: Y5 p/ g, m5 W9 P- h因此,即当! g3 T. t3 }7 m: z7 O
+ z. i& a; r8 r/ S% x5 z. Q% f
时误判率最低,此时误判率为:
% `7 {0 ^7 d6 ?0 A. A
! T! K+ E6 i( m1 z" H) d2 @可以看出若要使得误判率≤1/2,则:
; F1 j/ @: U" S0 \) n$ E. j
( @' {: G# t3 E) r" r这说明了若想保持某固定误判率不变,布隆过滤器的bit数m与被add的元素数n应该是线性同步增加的。
* T; ^! w6 K, Y, X设计和应用布隆过滤器的方法
, k. R3 r* d0 j2 p- k6 \& n应用时首先要先由用户决定要add的元素数n和希望的误差率P。这也是一个设计完整的布隆过滤器需要用户输入的仅有的两个参数,之后的所有参数将由系统计算,并由此建立布隆过滤器。# k/ V3 O# A* f
系统首先要计算需要的内存大小m bits:
/ |) W" S7 O7 M' l8 S$ k
5 m0 E8 p0 N* t再由m,n得到hash function的个数:' \" R# ]+ p0 B. Y

- H* O  z+ Z4 a4 B; M至此系统所需的参数已经备齐,接下来add n个元素至布隆过滤器中,再进行query。
; E3 h4 l% D4 L2 {: ]& {根据公式,当k最优时:
5 N8 O1 w, ^3 l" j4 g* r0 J+ N2 K* F
因此可验证当P=1%时,存储每个元素需要9.6 bits:( O& r& g& S1 y% q" F$ C2 B

# L  r1 R/ C) _! U而每当想将误判率降低为原来的1/10,则存储每个元素需要增加4.8 bits:
. }' V0 e5 q- [% M2 A- p# g- I8 c+ q$ V0 x7 G
这里需要特别注意的是,9.6 bits/element不仅包含了被置为1的k位,还把包含了没有被置为1的一些位数。此时的2 l4 A/ s3 g. ]' Q3 u: V

; r! u# {# e! T4 p0 ]. p才是每个元素对应的为1的bit位数。" q  t2 o$ q& m, D0 G1 T

6 L6 C% ^7 c, _# A7 A! `+ a+ S从而使得P(error)最小时,我们注意到:# |" v$ W6 ?5 ~) l) I4 |
9 j% R" t  {3 ?
中的: M/ |9 B" x% q/ P9 k
,即( E4 {: R% U8 ], P+ {1 p

8 [6 N! O- ~* ^4 G) k此概率为某bit位在插入n个元素后未被置位的概率。因此,想保持错误率低,布隆过滤器的空间使用率需为50%。
8 o* A. e# ~0 P) L: D0 [Neo中的布隆过滤器$ H, E( _4 M1 F% ^/ L6 h
上面的内容大部分抄袭http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html,原作者写的太好了,我只是加上一些我的理解,方便数学不好的道友理解。下面我们看看Neo中的Bloom Filter。* ?& M7 k5 p4 n$ r
using System.Collections;
/ \+ \" f- c2 D* H; T' j( \: dusing System.Linq;
# |7 m4 o" h5 [7 U! f; w" n# ~namespace Neo.Cryptography
: S* I: q( R" K( g& ]8 j{5 J& r# g/ ?% c' W6 Y
    public class BloomFilter6 T2 T: I8 `* ]' ^, r' L& z
    {
8 t. s6 A3 a, s3 q! T$ n        private readonly uint[] seeds;3 z2 V+ Y% C0 W; p% B" w
        private readonly BitArray bits;
2 J! c1 L  Q0 |        public int K => seeds.Length;! Z2 x! a" h0 |  j# c+ n
        public int M => bits.Length;
) y6 F1 W* @, c* W- o! v' n        public uint Tweak { get; private set; }
* z  O! e( y9 e" \- s* b% S( D% J        public BloomFilter(int m, int k, uint nTweak, byte[] elements = null)  ]: S0 J9 _3 ~5 |( x! K& @
        {5 y0 s5 Q: U) J$ W1 A$ j+ v& x
            this.seeds = Enumerable.Range(0, k).Select(p => (uint)p * 0xFBA4C795 + nTweak).ToArray();
, e4 Y6 W7 v9 ]3 G/ g            this.bits = elements == null ? new BitArray(m) : new BitArray(elements);
: a0 E) z+ _( a& ~) {4 K1 @            this.bits.Length = m;
+ d$ G/ h- J7 u' R* u: Q) t            this.Tweak = nTweak;2 J, P! R6 p9 w4 h$ |1 m; l4 p" w
        }
/ H, I  M2 U0 m: L9 X3 \        public void Add(byte[] element)3 d4 y7 Y1 A( @" d  w
        {
/ g' p4 z1 C" d) N, T8 ~3 w            foreach (uint i in seeds.AsParallel().Select(s => element.Murmur32(s)))+ h: g; j( x- ?  M- i$ \
                bits.Set((int)(i % (uint)bits.Length), true);
5 ^) V: o* a/ \4 ^% F3 i        }! J2 C! O9 w  q- e
        public bool Check(byte[] element)! x2 o8 o2 S. d" U1 J, \
        {. j" H8 k9 @( D* K) _
            foreach (uint i in seeds.AsParallel().Select(s => element.Murmur32(s)))
4 ]% v8 p% C$ f9 \2 D+ G+ Z0 P                if (!bits.Get((int)(i % (uint)bits.Length)))- Y. q) d7 s5 a6 j+ M1 W
                    return false;0 e: C4 J7 L; H+ N# p
            return true;
  o% R$ c% Z( }! Y& k1 \6 R        }) N$ D' e  H" x' ]/ @) P( [
        public void GetBits(byte[] newBits)
1 ?- J8 A- ^% Z" j" `% [        {
, q* B* @2 G1 H  H            bits.CopyTo(newBits, 0);
% `( k* k6 c8 V" G8 u4 |: t        }
% s, d) e5 p, W' Z, N" D5 `    }" [" J9 x7 i) {; L; Q! e+ ]
}
3 ^; n2 N+ S3 c( L1 m前面讲了这么多,代码竟然这么短,分析分析。
4 k: X9 o+ S2 }6 Z构造函数传入了m(多少位),k(hash函数种类),这个和我们前面分析根据p(错误率),和n(要插入的元素)来构造的思路不一样。所以Neo的这个版本应该是一个简化版本,输入的数据n应该是有范围的,具体的范围我们后面运行整个区块链的时候在观察,现在不知道n的个数有多大。hash函数使用了Murmur32,然后传入不同的seed模拟不同的hash函数,这个是可以的。使用linq,函数式编程代码非常简洁,这也是C#的一个优势啊。add,check函数都很容易看懂,确实实现很简洁。0 [3 P( H) E  w4 Y* L
/ Q( F# ?( c; B/ Z- {) ~
总结
# T# L& E! T- M& @7 oBloom Filter是牛逼的数据结构,因为有很多数学知识在里面,虽然代码不长,但是能看完这篇文章的人,会感受到代码之美。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

丈黑起恋秘 小学生
  • 粉丝

    0

  • 关注

    0

  • 主题

    2