Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

BloomFilter布隆过滤器 简介

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

6 p; ~0 m& C$ u$ h3 _" d现在考虑query阶段,若对应某个待query元素的k bits全部置位为1,则可判定其在集合中。因此将某元素误判的概率为:
3 ]) {/ j) p% I' f* O# R, W& ~8 \0 X- ~8 P" \  o
由于& a3 a) c: D* q& U. U- z
9 |2 u0 }  t) j6 N
,并且1/m 当m很大时趋近于0,所以
& s, _0 E- B  K0 @, S0 {& c现在计算对于给定的m和n,k为何值时可以使得误判率最低。设误判率为k的函数为:
9 X- g6 M& [8 g; X: v" m8 D
) v7 y. }  ]8 y4 }: q6 f+ Q  G0 N* o! [2 y2 u8 `. m

0 X4 A9 G1 K) N7 V  J) d% R则简化为
/ n# |% t9 N; ]5 e( Z  h
$ U* y  l" ?$ M因为等式右边的底数上是函数,指数上也是函数,没有方法求这样组合函数的导数,只能取对数之后,变成乘法。我们有两个函数相乘的求导方法,求导的几个方法可以看参考资料,有很好的视频说明。; ~' O4 r3 r2 p; `+ S4 [/ I4 h. L7 P
两边取对数得
1 t, u% x( t4 k# k# v% S2 O/ Z2 y0 [: {3 g& b' G) ~
两边对k求导得,这边涉及到乘法求导,对数求导,幂函数求导:
$ I+ T% |( e9 m! M" F' A
6 Z, h( M) h" O/ w* ~下面求最值," T; o. R, a: z) u0 ]& X) n8 z% e
$ Z) j# O) `( v$ Y& B+ d: F7 T! B  a
红圈中的等式是把两边看成xln(x)这种形式得到的,和该函数的单调性相关。数学上能不能这么操作我还不太清楚。数学好的大神可以留言解释一下。
8 d* I. A. i& {. }. j因此,即当: p) [8 U  u' U% `( S) C: j7 n
7 o/ _8 Q! t0 q' l: U
时误判率最低,此时误判率为:0 \6 r" l2 E! N" d4 ~1 Q

; ]5 E# I1 Z/ g" x; S2 K可以看出若要使得误判率≤1/2,则:
  ]- }  v6 w2 ?8 J4 Q) J, ]) ?$ {% U5 `" E8 l0 V7 n
这说明了若想保持某固定误判率不变,布隆过滤器的bit数m与被add的元素数n应该是线性同步增加的。& k* H, @. H( T& q- R% f
设计和应用布隆过滤器的方法( M, T% t# M0 k6 F9 I
应用时首先要先由用户决定要add的元素数n和希望的误差率P。这也是一个设计完整的布隆过滤器需要用户输入的仅有的两个参数,之后的所有参数将由系统计算,并由此建立布隆过滤器。' Q: ^# n$ q6 o
系统首先要计算需要的内存大小m bits:
) ]' U$ ~  n' d' R, x+ Y+ f# ?1 k8 e0 h% e! F
再由m,n得到hash function的个数:
1 r- o( w3 w4 V3 t; M4 R6 K- I3 C6 I% `' C# M+ V  {9 n
至此系统所需的参数已经备齐,接下来add n个元素至布隆过滤器中,再进行query。
( n# d! ~: m; E* E- O7 A根据公式,当k最优时:
1 Y: b( U; ]. f1 Z7 C/ V) s% R: f& r" d) P
因此可验证当P=1%时,存储每个元素需要9.6 bits:7 [* J: y0 a+ }7 I" u% s

6 c3 L& C+ L, \7 x, m) i7 m# x而每当想将误判率降低为原来的1/10,则存储每个元素需要增加4.8 bits:) v0 B: x( X5 b  y
& ]; `+ r4 j& @7 w- {# V/ _" m: E! u
这里需要特别注意的是,9.6 bits/element不仅包含了被置为1的k位,还把包含了没有被置为1的一些位数。此时的5 C% F6 d$ K0 b* ]- |/ _# S
& l4 t) n' F1 M$ U1 b) r. ?  Z( M
才是每个元素对应的为1的bit位数。
6 y& B3 I; `3 r- E1 H; u
2 U5 ]( I/ _; }9 p. U2 |从而使得P(error)最小时,我们注意到:0 r( h8 i4 K! T0 v% w
) l7 A2 |+ g/ R$ K* Y
中的; m/ X0 b( q! A# p1 H
,即  I2 f  U0 r$ k' S: t2 w5 z# H# c( H9 @

  U0 H# q) v$ B$ A* V此概率为某bit位在插入n个元素后未被置位的概率。因此,想保持错误率低,布隆过滤器的空间使用率需为50%。
& n' H! d6 D7 N  F5 b- o3 P3 E! CNeo中的布隆过滤器) V# h' B$ n$ {' w3 z  q- ]% _
上面的内容大部分抄袭http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html,原作者写的太好了,我只是加上一些我的理解,方便数学不好的道友理解。下面我们看看Neo中的Bloom Filter。& C1 v1 b* v* V3 A9 w! C9 |& Z
using System.Collections;
0 [% W% Z- n. `$ A. jusing System.Linq;
( x+ v* v0 D9 K% K  Ynamespace Neo.Cryptography
- M# D5 M( w2 ^, i{0 Y- r. `5 @5 u6 d8 x9 d
    public class BloomFilter4 i; T) C) a0 y! W
    {1 S: @3 i& i$ c1 c& {* v+ _
        private readonly uint[] seeds;
7 ^/ ]5 I* I  S, p$ `8 i        private readonly BitArray bits;, n* f+ E/ e8 {3 e: Y' _
        public int K => seeds.Length;0 c) A' R2 p, o( h" p
        public int M => bits.Length;, u# S0 v) G) }! ]  l" c
        public uint Tweak { get; private set; }2 J; n- T. ?: L! z3 g; v
        public BloomFilter(int m, int k, uint nTweak, byte[] elements = null)+ `) w  @3 V; E3 k, L
        {2 u7 C% }% u/ v% ~
            this.seeds = Enumerable.Range(0, k).Select(p => (uint)p * 0xFBA4C795 + nTweak).ToArray();$ @) X+ Z' L# N2 Z
            this.bits = elements == null ? new BitArray(m) : new BitArray(elements);1 B. R' n" g6 V# ~
            this.bits.Length = m;6 D3 _- O% R/ F8 _
            this.Tweak = nTweak;: ~3 o/ K& w0 y
        }
0 ]0 m, \; `' u; b5 U        public void Add(byte[] element)
5 F, R1 J! L3 K/ `, y3 b0 S0 q' V6 v8 ?        {% t4 {( |& @0 Q' }7 F
            foreach (uint i in seeds.AsParallel().Select(s => element.Murmur32(s)))+ Y5 G5 V0 e& u. U7 O+ k" R
                bits.Set((int)(i % (uint)bits.Length), true);3 P, s+ Z4 W% x) V( F
        }( x# f( j6 b0 y7 r  |
        public bool Check(byte[] element)
+ q& T* v) Q% a8 x' a, H! M3 ~        {
2 W( p) t; w8 s4 t            foreach (uint i in seeds.AsParallel().Select(s => element.Murmur32(s)))
+ P* V$ x5 f/ w6 I- t                if (!bits.Get((int)(i % (uint)bits.Length)))
1 j7 U# @# \! [) l/ i) x                    return false;3 b; S( G0 J3 z4 A0 \" |# H  t
            return true;. O" \0 B* [; T0 s% q& p
        }
1 `* E- E, {0 B6 m0 K% ]        public void GetBits(byte[] newBits)5 [4 w* ]1 `# S' {$ _8 [: \: F
        {
* @# n$ `% `% a7 O) B            bits.CopyTo(newBits, 0);, S3 n$ S; E: ~" J" h. k5 W
        }  Z) n" A2 g, t" g* z
    }. t+ b  h6 U9 b" b) T
}
& L0 A0 V0 e5 C8 r前面讲了这么多,代码竟然这么短,分析分析。  Z6 z/ s- A0 C
构造函数传入了m(多少位),k(hash函数种类),这个和我们前面分析根据p(错误率),和n(要插入的元素)来构造的思路不一样。所以Neo的这个版本应该是一个简化版本,输入的数据n应该是有范围的,具体的范围我们后面运行整个区块链的时候在观察,现在不知道n的个数有多大。hash函数使用了Murmur32,然后传入不同的seed模拟不同的hash函数,这个是可以的。使用linq,函数式编程代码非常简洁,这也是C#的一个优势啊。add,check函数都很容易看懂,确实实现很简洁。9 n% z8 d4 U$ z2 g) t

, h7 C( s; c' f0 E总结; ~9 N" `, t. B" @* U" H2 S2 {; x
Bloom Filter是牛逼的数据结构,因为有很多数学知识在里面,虽然代码不长,但是能看完这篇文章的人,会感受到代码之美。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

丈黑起恋秘 小学生
  • 粉丝

    0

  • 关注

    0

  • 主题

    2