Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

BloomFilter布隆过滤器 简介

丈黑起恋秘
150 0 0
布隆过滤器
9 }- R! S) y/ [8 `$ T- D9 ^布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。1 z* G( B4 g* S" P
布隆过滤器 (Bloom Filter)是一种space efficient的概率型数据结构,在垃圾邮件过滤的黑白名单方法、爬虫(Crawler)的网址判重模块中等等经常被用到。哈希表也能用于判断元素是否在集合中,但是布隆过滤器只需要哈希表的1/8或1/4的空间复杂度就能完成同样的问题。布隆过滤器可以插入元素,但不可以删除已有元素。其中的元素越多,false positive rate(误报率)越大,但是false negative (漏报)是不可能的。
) }. ?6 I* a  M% ], `9 J基本概念
% T# e6 s/ t) ]; g8 V5 A7 f- _1 H如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为 O(n),O(log n),O(n/k)。5 _( ]3 T1 b5 `8 P
布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。: }9 d9 O' a$ K* l" e9 J& q& n2 Z
算法描述
: L8 b1 R  h8 d) z. |8 V一个empty bloom filter是一个有m bits的bit array,每一个bit位都初始化为0。并且定义有k个不同的hash function,每个都以uniform random distribution将元素hash到m个不同位置中的一个。在下面的介绍中n为元素数,m为布隆过滤器或哈希表的slot数,k为布隆过滤器重hash function数。9 U5 H; E+ B& y) x
为了add一个元素,用k个hash function将它hash得到bloom filter中k个bit位,将这k个bit位置1。
1 j0 C2 B6 B$ `, \2 |0 N- q8 Q1 d为了query一个元素,即判断它是否在集合中,用k个hash function将它hash得到k个bit位。若这k bits全为1,则此元素在集合中;若其中任一位不为1,则此元素比不在集合中(因为如果在,则在add时已经把对应的k个bits位置为1)。
) S( v" t4 {8 i( f) I% K不允许remove元素,因为那样的话会把相应的k个bits位置为0,而其中很有可能有其他元素对应的位。因此remove会引入false negative,这是绝对不被允许的。, S7 R- n' i! o  r8 v; L
当k很大时,设计k个独立的hash function是不现实并且困难的。对于一个输出范围很大的hash function(例如MD5产生的128 bits数),如果不同bit位的相关性很小,则可把此输出分割为k份。或者可将k个不同的初始值(例如0,1,2, … ,k-1)结合元素,feed给一个hash function从而产生k个不同的数。
5 l1 q) E" s- [# S! U% w! Y当add的元素过多时,即n/m过大时(n是元素数,m是bloom filter的bits数),会导致false positive过高,此时就需要重新组建filter,但这种情况相对少见。4 z( o" _0 S4 K6 N
优点
' e4 d  Y6 S7 u4 S9 C- h相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数(O(k))。另外,散列函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。
6 ]0 G3 Q: M0 \2 `; H* `" |布隆过滤器可以表示全集,其它任何数据结构都不能;
2 F8 s# Y7 L, R. D& c$ t缺点
0 i# g: \4 t/ I  V! @0 Q但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。
7 M3 D' v1 C& j: Y1 R另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。
! B+ C5 t5 |' T" C0 P0 j6 t( D在降低误算率方面,有不少工作,使得出现了很多布隆过滤器的变种。% Z& K9 Q' }( c! i1 N1 X
举例说明布隆过滤器的空间优势$ u- O: P' q+ M, z, l' I
先来一个结论:对于一个有1%误报率和一个最优k值的布隆过滤器来说,无论元素的类型及大小,每个元素只需要9.6 bits来存储。这个优点一部分继承自array的紧凑性,一部分来源于它的概率性。如果你认为1%的误报率太高,那么对每个元素每增加4.8 bits,我们就可将误报率降低为原来的1/10。add和query的时间复杂度都为O(k),与集合中元素的多少无关,这是其他数据结构都不能完成的。k是hash函数的个数。
  H$ ]1 ^) s/ W) C# B0 b举例: 现有1亿个email的黑名单,元素的数量(即email列表)为 108。若采用布隆过滤器,取k=8(k为hash函数个数)。因为n为1亿,所以总共需要8*108。又因为在保证误判率低(后面解释)且k和m选取合适时,空间利用率为50%(后面会解释),所以总空间为: I* q" Q5 c0 l5 M
4 O! Z( @2 d# Y* e* u
空间优势+ B5 D- U0 d. k  ~$ W+ f7 R
所需空间比上述哈希结构或者数组小得多,并且误判率在万分之一以下。为什么可以这样算,可以看下面。( e9 V3 v, L! Z4 [, m  c
误判概率的证明和计算6 d7 \1 J- c8 u- b; ~
该过程的详细说明来自于这个文章http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html,为了看懂求导过程,需要复习数学知识。
$ F; |7 U4 w0 I* s: u# }8 l4 d( \对某一特定bit位在一个元素由某特定hash function插入时没有被置位为1的概率为:
* d' [: [- `7 y6 n0 y- V
; O1 s. N, A$ K$ I3 k则k个hash function中没有一个对其置位的概率为:
4 `+ Q  K/ {0 c
2 N  A% T! |: \/ B+ G9 s如果插入了n个元素,但都未将其置位的概率为:# p. u( d: i; L) z: l
& l4 a- P* ?+ Y* `6 M+ K+ j7 \
现在考虑query阶段,若对应某个待query元素的k bits全部置位为1,则可判定其在集合中。因此将某元素误判的概率为:
( u4 E. n2 j3 ~) e+ x5 [
2 a0 C1 M) v5 P! }由于
. Y/ v" W8 t# o/ d: u$ r8 ?" \& K: |# A$ X+ g
,并且1/m 当m很大时趋近于0,所以
0 }: _' M& g) P. V# K+ f现在计算对于给定的m和n,k为何值时可以使得误判率最低。设误判率为k的函数为:% M5 F' I2 x9 k3 F4 h- @1 k

/ N& r+ z  o  S1 i3 E" l
  n- Y' P+ o! G" j, P7 t0 q' m* m% P' Y( T) e
则简化为
+ r- `( T5 D4 w
9 x$ O% P8 k. E2 P因为等式右边的底数上是函数,指数上也是函数,没有方法求这样组合函数的导数,只能取对数之后,变成乘法。我们有两个函数相乘的求导方法,求导的几个方法可以看参考资料,有很好的视频说明。! Z3 \0 r+ S5 I, Z/ V' M- g" y- G) ^
两边取对数得( q3 B' L5 S2 e5 U
; p3 r8 x- _9 J" J0 v( H( E; D
两边对k求导得,这边涉及到乘法求导,对数求导,幂函数求导:
9 j1 p& a) n! h8 _( k: N- D3 [5 O3 e8 ?1 d! Y" z: R
下面求最值,, M7 |5 N4 k( j

+ L7 x7 r2 M! g* P红圈中的等式是把两边看成xln(x)这种形式得到的,和该函数的单调性相关。数学上能不能这么操作我还不太清楚。数学好的大神可以留言解释一下。9 h6 T- S( I+ C) {; m
因此,即当( ^7 G) B5 z" Y7 P3 ^6 [* \3 X
- T7 h" k7 @; g+ n
时误判率最低,此时误判率为:5 B& J0 P. Q0 G. b% G
' A4 @) d, U3 Z6 C
可以看出若要使得误判率≤1/2,则:9 V! b4 y! r4 _2 F+ R( u
  R$ \  }% {8 X" K# S; k$ c: K! @( c
这说明了若想保持某固定误判率不变,布隆过滤器的bit数m与被add的元素数n应该是线性同步增加的。8 t) l% y+ e! C: q1 i
设计和应用布隆过滤器的方法
9 {; `/ b4 V( {$ H3 K3 l+ e! r应用时首先要先由用户决定要add的元素数n和希望的误差率P。这也是一个设计完整的布隆过滤器需要用户输入的仅有的两个参数,之后的所有参数将由系统计算,并由此建立布隆过滤器。+ z& T7 W. Q4 b$ n& x& U
系统首先要计算需要的内存大小m bits:. ?) X+ ^- A; U
$ n) u% o8 w8 M: I) b5 j
再由m,n得到hash function的个数:
) k# o# J  `6 a; a8 ^  |, Y/ B9 E# F# P8 V
至此系统所需的参数已经备齐,接下来add n个元素至布隆过滤器中,再进行query。, j/ y6 i$ I* }0 J2 K
根据公式,当k最优时:# a% }6 d, A5 o, o

$ F; F8 t2 b, A0 @因此可验证当P=1%时,存储每个元素需要9.6 bits:& w' z1 F2 A1 w

: F3 K1 W- |" X而每当想将误判率降低为原来的1/10,则存储每个元素需要增加4.8 bits:
: L- |& a! b7 {" F- {; P. F' f4 N/ X2 e; `
这里需要特别注意的是,9.6 bits/element不仅包含了被置为1的k位,还把包含了没有被置为1的一些位数。此时的
) H" k" m7 P2 r. S5 Q3 H
) O/ _. Z2 c& S  g& B才是每个元素对应的为1的bit位数。
  d$ w, \; t/ |$ v0 |5 J9 L0 V
% C, t! G  k, u5 r' T* N: y3 `从而使得P(error)最小时,我们注意到:9 @3 E7 P3 C3 Q- H: {
1 E! s% \2 S2 H$ l
中的# P# v8 K+ ~& d; l: k$ g
,即4 a- k' O: y- O# Z
3 q' C- y. R2 K( Y( J
此概率为某bit位在插入n个元素后未被置位的概率。因此,想保持错误率低,布隆过滤器的空间使用率需为50%。
/ |0 ?8 X) X9 o- f5 c" XNeo中的布隆过滤器
( K- P  I1 a* o7 ^3 |- f0 l; G上面的内容大部分抄袭http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html,原作者写的太好了,我只是加上一些我的理解,方便数学不好的道友理解。下面我们看看Neo中的Bloom Filter。1 Q/ q! q- Y2 y9 \2 ?) c
using System.Collections;
* T( j: T  e/ x0 L7 T8 husing System.Linq;. W- x7 S8 |% [, F) m4 f
namespace Neo.Cryptography0 Z' S* e" X# _5 c
{7 m- }' h3 f0 |% _! ]( H, c
    public class BloomFilter
/ M! Q3 r, x* k9 ]! z6 K    {# [/ ~* V! E! t  c8 p, s# p8 V
        private readonly uint[] seeds;; v/ U4 e6 n. g+ K
        private readonly BitArray bits;7 }/ ?6 D' Y. |
        public int K => seeds.Length;9 w( X; A/ t% R0 G' K
        public int M => bits.Length;
) ^) R! N# G- B+ D/ U1 L        public uint Tweak { get; private set; }) c4 y! J8 @) \, [
        public BloomFilter(int m, int k, uint nTweak, byte[] elements = null)
- [6 K1 y1 E$ t" @) `        {
1 e6 @/ i  @- C            this.seeds = Enumerable.Range(0, k).Select(p => (uint)p * 0xFBA4C795 + nTweak).ToArray();
1 @* i- U  S& N6 M            this.bits = elements == null ? new BitArray(m) : new BitArray(elements);
& F- D" L/ S9 |' a" Y            this.bits.Length = m;  r( l1 ]* [1 G8 |
            this.Tweak = nTweak;. }7 A# v# j5 n2 B- t* n
        }  b! n( ^& @$ l  I5 `& g
        public void Add(byte[] element)
  A9 Z6 u% {* C" Q4 S5 ?3 d        {; G! n7 r) a$ N; f: {! g
            foreach (uint i in seeds.AsParallel().Select(s => element.Murmur32(s)))
8 P0 J3 I1 f+ @/ G* Y  h/ J+ L                bits.Set((int)(i % (uint)bits.Length), true);% d% ~3 t: p" S) Q% D8 d9 _
        }# f9 ^+ A1 S  x+ J2 U, }# Z
        public bool Check(byte[] element)
- m4 d) j* A2 m8 \8 p( G: I2 y        {5 Q  _/ }+ E( D7 f) y
            foreach (uint i in seeds.AsParallel().Select(s => element.Murmur32(s)))
2 U. E. l6 @" C6 w* ^                if (!bits.Get((int)(i % (uint)bits.Length)))
* S% f: B5 n! o9 m/ I                    return false;: P! b" T7 L; b+ M
            return true;) H1 p7 |& O' {. K
        }% J# G. T& r$ Z* a4 L
        public void GetBits(byte[] newBits)' M4 G8 D* J* z
        {' p& a+ Y( R; V, K- |$ p
            bits.CopyTo(newBits, 0);
& w4 f' N0 \+ N. ^        }( Y5 n+ p0 s( D% i6 g2 k" k$ {, k# A
    }
+ b5 g& V) I. j% ]: E) I0 y}
: _% g1 p. _6 M9 u前面讲了这么多,代码竟然这么短,分析分析。0 d8 x: p, u4 v2 H8 b0 @5 N/ r
构造函数传入了m(多少位),k(hash函数种类),这个和我们前面分析根据p(错误率),和n(要插入的元素)来构造的思路不一样。所以Neo的这个版本应该是一个简化版本,输入的数据n应该是有范围的,具体的范围我们后面运行整个区块链的时候在观察,现在不知道n的个数有多大。hash函数使用了Murmur32,然后传入不同的seed模拟不同的hash函数,这个是可以的。使用linq,函数式编程代码非常简洁,这也是C#的一个优势啊。add,check函数都很容易看懂,确实实现很简洁。
# J- @0 B! c* [
+ L2 Q+ u" V4 D* D$ s7 Z! P总结
8 I! @0 _* I7 w9 u: n4 R7 O* SBloom Filter是牛逼的数据结构,因为有很多数学知识在里面,虽然代码不长,但是能看完这篇文章的人,会感受到代码之美。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

丈黑起恋秘 小学生
  • 粉丝

    0

  • 关注

    0

  • 主题

    2