Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

BloomFilter布隆过滤器 简介

丈黑起恋秘
83 0 0
布隆过滤器3 O4 m5 W* M; {' x& }/ S" y# s: I( g
布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。' A2 W. O9 d$ x- K. c9 t
布隆过滤器 (Bloom Filter)是一种space efficient的概率型数据结构,在垃圾邮件过滤的黑白名单方法、爬虫(Crawler)的网址判重模块中等等经常被用到。哈希表也能用于判断元素是否在集合中,但是布隆过滤器只需要哈希表的1/8或1/4的空间复杂度就能完成同样的问题。布隆过滤器可以插入元素,但不可以删除已有元素。其中的元素越多,false positive rate(误报率)越大,但是false negative (漏报)是不可能的。: A' I8 V. Z  c* t7 \/ O
基本概念
( \3 O. n1 j; ^& w3 e) k2 d* @如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为 O(n),O(log n),O(n/k)。, c1 l+ j' Z/ ]: a' x+ [9 R  Z
布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。
; d9 @1 A$ N/ b4 ~, t  `! d算法描述
) t- }) c! x/ y, D8 W一个empty bloom filter是一个有m bits的bit array,每一个bit位都初始化为0。并且定义有k个不同的hash function,每个都以uniform random distribution将元素hash到m个不同位置中的一个。在下面的介绍中n为元素数,m为布隆过滤器或哈希表的slot数,k为布隆过滤器重hash function数。. ^" n" a3 q) u' ?1 _
为了add一个元素,用k个hash function将它hash得到bloom filter中k个bit位,将这k个bit位置1。
5 t4 z0 z& b4 n* y& ]4 }/ m# B为了query一个元素,即判断它是否在集合中,用k个hash function将它hash得到k个bit位。若这k bits全为1,则此元素在集合中;若其中任一位不为1,则此元素比不在集合中(因为如果在,则在add时已经把对应的k个bits位置为1)。: @# u; c% P4 S; X# l" h
不允许remove元素,因为那样的话会把相应的k个bits位置为0,而其中很有可能有其他元素对应的位。因此remove会引入false negative,这是绝对不被允许的。' e4 B& V1 u3 ?& F5 P7 t: _
当k很大时,设计k个独立的hash function是不现实并且困难的。对于一个输出范围很大的hash function(例如MD5产生的128 bits数),如果不同bit位的相关性很小,则可把此输出分割为k份。或者可将k个不同的初始值(例如0,1,2, … ,k-1)结合元素,feed给一个hash function从而产生k个不同的数。
8 B6 _; Z6 a* [$ w当add的元素过多时,即n/m过大时(n是元素数,m是bloom filter的bits数),会导致false positive过高,此时就需要重新组建filter,但这种情况相对少见。
. k& g9 j5 O5 K6 L' I& i; q% d- o优点
4 l9 R/ t3 Y0 t6 ]+ d相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数(O(k))。另外,散列函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。& ?- L7 v" S2 `5 [
布隆过滤器可以表示全集,其它任何数据结构都不能;
; V" d4 g2 Z; x% i缺点
! r8 O3 U9 c( T! Y7 |; P7 C0 W但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。$ n5 z- n- D5 w8 }2 g
另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。
' M2 o1 k* G( o, n" A$ ?在降低误算率方面,有不少工作,使得出现了很多布隆过滤器的变种。1 W) P( r' j  R
举例说明布隆过滤器的空间优势; q8 Z3 V7 Z5 l" n! f% f
先来一个结论:对于一个有1%误报率和一个最优k值的布隆过滤器来说,无论元素的类型及大小,每个元素只需要9.6 bits来存储。这个优点一部分继承自array的紧凑性,一部分来源于它的概率性。如果你认为1%的误报率太高,那么对每个元素每增加4.8 bits,我们就可将误报率降低为原来的1/10。add和query的时间复杂度都为O(k),与集合中元素的多少无关,这是其他数据结构都不能完成的。k是hash函数的个数。# ]6 ?% ^+ n8 Z2 \- b8 n
举例: 现有1亿个email的黑名单,元素的数量(即email列表)为 108。若采用布隆过滤器,取k=8(k为hash函数个数)。因为n为1亿,所以总共需要8*108。又因为在保证误判率低(后面解释)且k和m选取合适时,空间利用率为50%(后面会解释),所以总空间为6 L) h& ~, c/ n6 w

# H2 E# A; k( e5 u8 |空间优势0 R' y: l# P( Z8 i! p, Z5 L
所需空间比上述哈希结构或者数组小得多,并且误判率在万分之一以下。为什么可以这样算,可以看下面。. V% M$ u9 r( G0 Q6 q% Y4 p2 l
误判概率的证明和计算
' s$ _: r/ y  Z. G) W4 m该过程的详细说明来自于这个文章http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html,为了看懂求导过程,需要复习数学知识。0 i: `! c0 z( j4 ]; J7 o0 ?5 ~9 _
对某一特定bit位在一个元素由某特定hash function插入时没有被置位为1的概率为:
0 H) f( j) z9 y5 ~2 d# n
& B  k2 O1 h8 G1 i+ Y4 S则k个hash function中没有一个对其置位的概率为:, V/ c7 Q( ~/ P0 e. E4 x& ~* J+ @7 w

4 \: w8 p/ b. U* S* e9 H如果插入了n个元素,但都未将其置位的概率为:
8 K0 R% `- Z3 Z9 L6 `. U; _+ f' J6 b7 U- ]
现在考虑query阶段,若对应某个待query元素的k bits全部置位为1,则可判定其在集合中。因此将某元素误判的概率为:7 G/ Q! Z! S( s# M  T
1 @8 Y. U8 E; ]/ x" r: A) S
由于- M/ j1 }5 g' j% ]
7 U6 D5 |# i% w7 J
,并且1/m 当m很大时趋近于0,所以
  E$ z+ X* i$ g2 U6 A现在计算对于给定的m和n,k为何值时可以使得误判率最低。设误判率为k的函数为:5 W) v5 F  s4 s9 l5 J
! L, k. q6 P+ D6 W) I3 d! r
$ q6 q: r' Q) F# w9 y
1 A4 Z9 n/ a( m4 ~2 @- s6 _
则简化为
: E4 i2 Q0 D  Q" v( q5 N+ g1 a6 g" A" L- k/ b
因为等式右边的底数上是函数,指数上也是函数,没有方法求这样组合函数的导数,只能取对数之后,变成乘法。我们有两个函数相乘的求导方法,求导的几个方法可以看参考资料,有很好的视频说明。4 c+ \! h6 z- A2 K1 s
两边取对数得
  C) l3 ^3 v5 }9 @1 j  O. A$ ~) M0 V" x
两边对k求导得,这边涉及到乘法求导,对数求导,幂函数求导:
2 z4 h5 |3 ]  c! [, l% r: Y# J, _5 Q% g) k4 v
下面求最值," i! r' j' I8 _
; n# e5 K8 ~  E1 N5 ]
红圈中的等式是把两边看成xln(x)这种形式得到的,和该函数的单调性相关。数学上能不能这么操作我还不太清楚。数学好的大神可以留言解释一下。2 d- u- }) f$ L& v3 y
因此,即当9 V% O; r6 c! F$ U6 a8 x

8 I5 @+ w; a( S时误判率最低,此时误判率为:
, j, k" N7 O! b+ Q) ~/ O6 L: j! J) w3 Z# [5 Z/ ^1 _5 ?
可以看出若要使得误判率≤1/2,则:
# j" e) g. S5 W/ w& i+ |  D
- Y7 j! \; a  ~这说明了若想保持某固定误判率不变,布隆过滤器的bit数m与被add的元素数n应该是线性同步增加的。
# v9 t% D1 z  w7 ?* h: U设计和应用布隆过滤器的方法
7 i: m! Q% B) w- A/ U: T3 X, B* b应用时首先要先由用户决定要add的元素数n和希望的误差率P。这也是一个设计完整的布隆过滤器需要用户输入的仅有的两个参数,之后的所有参数将由系统计算,并由此建立布隆过滤器。& {3 w" V% d* N, {+ T2 l# \
系统首先要计算需要的内存大小m bits:
% _6 L& D" Q+ s7 q. O: I8 H1 Z
( D2 t9 \; B. H; [" u再由m,n得到hash function的个数:: o7 t  S( s* j3 u9 I! l- v0 D

* d3 R* \6 N* q( h# }" G. n3 j' U至此系统所需的参数已经备齐,接下来add n个元素至布隆过滤器中,再进行query。
9 _# J0 h  `' G( D9 H2 d根据公式,当k最优时:
: r1 S" `6 O9 x
% u( b& ?  f1 ]: ]5 N因此可验证当P=1%时,存储每个元素需要9.6 bits:
. y0 y! a7 c3 A5 O7 V% o6 ~7 I  K- B: ~
( N$ ?1 e% X" v* U" t而每当想将误判率降低为原来的1/10,则存储每个元素需要增加4.8 bits:2 i3 G4 \( f* n! Q2 B
1 |) N- r  N  d
这里需要特别注意的是,9.6 bits/element不仅包含了被置为1的k位,还把包含了没有被置为1的一些位数。此时的, n1 B0 A* e4 C* ?+ n2 G+ E' N/ |) B7 q& K

# p" j, A3 z$ N* w$ J2 j. r: C才是每个元素对应的为1的bit位数。
4 m4 C( `2 F& ^3 A% l" d
$ k7 Q- P. s9 v0 j8 j" _4 I( E2 i从而使得P(error)最小时,我们注意到:
, ~9 N. }$ Z3 x! l  s9 i
- @2 a& R1 d5 }中的% b2 u: W  L4 {# `# o
,即# v$ Q8 x9 J0 x' B: M

3 R# p- F+ ?2 V2 x+ t此概率为某bit位在插入n个元素后未被置位的概率。因此,想保持错误率低,布隆过滤器的空间使用率需为50%。
# |( X1 z$ _! TNeo中的布隆过滤器% [. L9 ?# ?- o# o' l, X6 P( k
上面的内容大部分抄袭http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html,原作者写的太好了,我只是加上一些我的理解,方便数学不好的道友理解。下面我们看看Neo中的Bloom Filter。
7 O* ^/ M' D% y5 `& \3 l  X8 Eusing System.Collections;/ B( V) L0 d' m9 |! U8 }$ @
using System.Linq;
' j) J) @) ^+ O* `, l' ^+ s5 Cnamespace Neo.Cryptography
* h/ d, H) \0 e{
$ @- I5 f4 U+ f2 D, w    public class BloomFilter
! c9 r- s% N; u! S5 `    {; r6 N3 B+ V! K3 r# b/ T7 p. H
        private readonly uint[] seeds;
0 d/ c" U$ p) x9 ^        private readonly BitArray bits;: F! K. Z4 [! o" P4 ^% x2 O
        public int K => seeds.Length;6 G7 @; U6 N4 b7 F' v
        public int M => bits.Length;( M* ~( k" \) d. O* y; o8 U% I
        public uint Tweak { get; private set; }4 |- i9 g( s8 u! |$ a7 Y9 U4 o
        public BloomFilter(int m, int k, uint nTweak, byte[] elements = null)  ]  R( d) W+ T8 R
        {
  h& Q+ M  W1 X3 A4 J            this.seeds = Enumerable.Range(0, k).Select(p => (uint)p * 0xFBA4C795 + nTweak).ToArray();
  o  I0 t+ b+ |% Q0 r, a            this.bits = elements == null ? new BitArray(m) : new BitArray(elements);6 N3 ?( ^* W- s+ x- ^( `
            this.bits.Length = m;
1 `% H" u: V/ Y. H' `0 V            this.Tweak = nTweak;* |1 @; T4 V- p( G5 Y3 o
        }  k+ m" d. c+ j
        public void Add(byte[] element), p- q* l2 i+ u" a" J- m/ W9 y; Q
        {  D) L# D, v" z. J) P
            foreach (uint i in seeds.AsParallel().Select(s => element.Murmur32(s)))
$ Y- p! u9 s7 f. d# N  @                bits.Set((int)(i % (uint)bits.Length), true);
8 ]7 m3 ]7 w7 t/ s        }
5 y* Z3 S+ \7 ?5 p$ C: l9 N4 J        public bool Check(byte[] element)
4 x$ c9 u9 x( Q        {2 w; Q5 X& i$ A  V% j! V9 s4 x2 b9 d- e
            foreach (uint i in seeds.AsParallel().Select(s => element.Murmur32(s)))
  R$ }& m, r: l- t' r: w% ], {5 S                if (!bits.Get((int)(i % (uint)bits.Length)))$ j% @, l# _' m4 e' ^0 z
                    return false;
0 N1 @4 i2 ~7 G( }5 t            return true;
( F4 j. v6 w* M( y+ V        }
% P  l5 Y$ ^' W9 o( _3 o        public void GetBits(byte[] newBits)
/ B- Q& m6 g( Z( i        {1 A2 z1 Y* X( s2 @
            bits.CopyTo(newBits, 0);; V. K: v# m7 u( l& t" J/ x. R# ]8 J
        }: p  Y% M% D) L$ \$ A
    }
4 ~3 q) D: D! l* ~& i5 F}4 y* J- z: {0 ~3 ^  H7 q4 ~
前面讲了这么多,代码竟然这么短,分析分析。% E8 E( P- n4 f! ?% N9 @
构造函数传入了m(多少位),k(hash函数种类),这个和我们前面分析根据p(错误率),和n(要插入的元素)来构造的思路不一样。所以Neo的这个版本应该是一个简化版本,输入的数据n应该是有范围的,具体的范围我们后面运行整个区块链的时候在观察,现在不知道n的个数有多大。hash函数使用了Murmur32,然后传入不同的seed模拟不同的hash函数,这个是可以的。使用linq,函数式编程代码非常简洁,这也是C#的一个优势啊。add,check函数都很容易看懂,确实实现很简洁。
( Z) T3 V. P1 f' p0 ~% |$ N3 ]/ c6 {2 _5 l% N, `& q" ?
总结2 v% G4 ]3 d* E" e. R2 u( N8 M
Bloom Filter是牛逼的数据结构,因为有很多数学知识在里面,虽然代码不长,但是能看完这篇文章的人,会感受到代码之美。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

丈黑起恋秘 小学生
  • 粉丝

    0

  • 关注

    0

  • 主题

    2