QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1453|回复: 0
打印 上一主题 下一主题

[其他经验] 【转】BloomFilter——大规模数据处理利器

[复制链接]
字体大小: 正常 放大

86

主题

13

听众

160

积分

升级  30%

  • TA的每日心情

    2016-4-25 17:12
  • 签到天数: 22 天

    [LV.4]偶尔看看III

    自我介绍
    萌萌哒

    社区QQ达人

    群组2015国赛优秀论文解析

    群组2015年国赛优秀论文解

    跳转到指定楼层
    1#
    发表于 2016-4-8 12:03 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    那些优雅的数据结构(1) : BloomFilter——大规模数据处理利器Posted on 2011-01-02 19:08 苍梧 阅读(37504) 评论(25) 编辑 收藏& F4 q2 r* Q( b6 q( C
    BloomFilter——大规模数据处理利器
      Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。
    7 w& K7 M: N* f% k8 h! o
    . 实例
      为了说明Bloom Filter存在的重要意义,举一个实例:
      假设要你写一个网络蜘蛛(web crawler)。由于网络间的链接错综复杂,蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”,就需要知道蜘蛛已经访问过那些URL。给一个URL,怎样知道蜘蛛是否已经访问过呢?稍微想想,就会有如下几种方案:
      1. 将访问过的URL保存到数据库。
      2. 用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。
      3. URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。
      4. Bit-Map方法。建立一个BitSet,将每个URL经过一个哈希函数映射到某一位。
      方法1~3都是将访问过的URL完整保存,方法4则只标记URL的一个映射位。

    " o2 o3 l2 F5 p1 n. U& E4 n5 x, B
      以上方法在数据量较小的情况下都能完美解决问题,但是当数据量变得非常庞大时问题就来了。
      方法1的缺点:数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了?
      方法2的缺点:太消耗内存。随着URL的增多,占用的内存会越来越多。就算只有1亿个URL,每个URL只算50个字符,就需要5GB内存。
      方法3:由于字符串经过MD5处理后的信息摘要长度只有128Bit,SHA-1处理后也只有160Bit,因此方法3比方法2节省了好几倍的内存。
      方法4消耗内存是相对较少的,但缺点是单一哈希函数发生冲突的概率太高。还记得数据结构课上学过的Hash表冲突的各种解决方法么?若要降低冲突发生的概率到1%,就要将BitSet的长度设置为URL个数的100倍。
      实质上上面的算法都忽略了一个重要的隐含条件:允许小概率的出错,不一定要100%准确!也就是说少量url实际上没有没网络蜘蛛访问,而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。
    ! U5 m, \" M! n5 @: O" I* O- Y% d5 v
    . Bloom Filter的算法
      废话说到这里,下面引入本篇的主角——Bloom Filter。其实上面方法4的思想已经很接近Bloom Filter了。方法四的致命缺点是冲突概率高,为了降低冲突的概念,Bloom Filter使用了多个哈希函数,而不是一个。
        Bloom Filter算法如下:
        创建一个m位BitSet,先将所有位初始化为0,然后选择k个不同的哈希函数。第i个哈希函数对字符串str哈希的结果记为h(i,str),且h(i,str)的范围是0到m-1 。
    ! a; i+ b* Q5 k5 Y
    (1) 加入字符串过程
      下面是每个字符串处理的过程,首先是将字符串str“记录”到BitSet中的过程:
      对于字符串str,分别计算h(1,str),h(2,str)…… h(k,str)。然后将BitSet的第h(1,str)、h(2,str)…… h(k,str)位设为1。
      图1.Bloom Filter加入字符串过程
      很简单吧?这样就将字符串str映射到BitSet中的k个二进制位了。
    7 c4 T. v  M. {% {% e
    (2) 检查字符串是否存在的过程

    : m& k6 U. G" h. [
      下面是检查字符串str是否被BitSet记录过的过程:
      对于字符串str,分别计算h(1,str),h(2,str)…… h(k,str)。然后检查BitSet的第h(1,str)、h(2,str)…… h(k,str)位是否为1,若其中任何一位不为1则可以判定str一定没有被记录过。若全部位都是1,则“认为”字符串str存在。

    & R6 f! j) Z8 T- k4 y
      若一个字符串对应的Bit不全为1,则可以肯定该字符串一定没有被Bloom Filter记录过。(这是显然的,因为字符串被记录过,其对应的二进制位肯定全部被设为1了)
      但是若一个字符串对应的Bit全为1,实际上是不能100%的肯定该字符串被Bloom Filter记录过的。(因为有可能该字符串的所有位都刚好是被其他字符串所对应)这种将该字符串划分错的情况,称为false positive 。
    $ l) C6 C" O" Y' V- ~
    (3) 删除字符串过程
       字符串加入了就被不能删除了,因为删除会影响到其他字符串。实在需要删除字符串的可以使用Counting bloomfilter(CBF),这是一种基本Bloom Filter的变体,CBF将基本Bloom Filter每一个Bit改为一个计数器,这样就可以实现删除字符串的功能了。
    8 G/ {& ?4 t, b
      Bloom Filter跟单哈希函数Bit-Map不同之处在于:Bloom Filter使用了k个哈希函数,每个字符串跟k个bit对应。从而降低了冲突的概率。

    / g+ t$ G, h; ~( Y$ b
    . Bloom Filter参数选择

    # h9 x) q) q( i+ v. H) m/ d2 d! `
       (1)哈希函数选择
         哈希函数的选择对性能的影响应该是很大的,一个好的哈希函数要能近似等概率的将字符串映射到各个Bit。选择k个不同的哈希函数比较麻烦,一种简单的方法是选择一个哈希函数,然后送入k个不同的参数。
       (2)Bit数组大小选择
         哈希函数个数k、位数组大小m、加入的字符串数量n的关系可以参考参考文献1。该文献证明了对于给定的m、n,当 k = ln(2)* m/n 时出错的概率是最小的。
         同时该文献还给出特定的k,m,n的出错概率。例如:根据参考文献1,哈希函数个数k取10,位数组大小m设为字符串个数n的20倍时,false positive发生的概率是0.0000889 ,这个概率基本能满足网络爬虫的需求了。  

    ' V; _- z4 ]3 B6 ?8 w8 K9 J
    . Bloom Filter实现代码
        下面给出一个简单的Bloom Filter的Java实现代码:

    , i2 r7 q2 P% k* ]3 o0 O[url=][/url]
    1 {/ h8 l$ T  ^9 ~6 N2 m5 X, bimport java.util.BitSet;3 m1 E+ ~7 v1 A/ T% W

    + d( A+ d! N( a9 f% M  s7 opublicclass BloomFilter $ M' ]6 g2 x, G) S* ~' d
    {; A$ F% K+ q' }0 f4 N4 n
    /* BitSet初始分配2^24个bit */ 2 Y: K- D& j5 @' y, \# r/ P
    privatestaticfinalint DEFAULT_SIZE =1<<25; + q' u' C! _- c' ~9 P
    /* 不同哈希函数的种子,一般应取质数 */
    , L+ Y' Z, G2 q7 _privatestaticfinalint[] seeds =newint[] { 5, 7, 11, 13, 31, 37, 61 };
      S% n* k+ G0 M( G- }# J. Y" f; Dprivate BitSet bits =new BitSet(DEFAULT_SIZE);: K% _+ [, u; d, u; _
    /* 哈希函数对象 */
    4 s+ n3 v( d- F: e: Iprivate SimpleHash[] func =new SimpleHash[seeds.length];3 J8 ?1 W( \9 W" w3 n. l
    + V3 C) Z% s( z3 G1 ]2 h0 U% L( T
    public BloomFilter() , _: L2 \4 @, Q
    {
    ) f) n9 l5 X: M* G5 c# {for (int i =0; i < seeds.length; i++)  B; M$ V: G# `7 _- ~
    {" h. W9 Y9 j1 Y" E6 L9 ]) o% S
    func =new SimpleHash(DEFAULT_SIZE, seeds);" s+ F; ^* c2 a, [: ~
    }$ n3 ]# a8 b" _! H, ~" G  X1 n
    }
    & x: c0 F. d( ^; [" }/ N" ]" }0 h4 w( O9 B
    // 将字符串标记到bits中* J6 q# k6 p; D+ h8 l1 e
    publicvoid add(String value) + {7 @2 n9 Y7 o, {
    {# h# B) B' o; P. i
    for (SimpleHash f : func)
    ! c3 }3 m! M( |! T{
    ; q: w- @1 U- t  E# Ibits.set(f.hash(value), true);8 z% s! T5 T9 a" d
    }* p% W% b: C; o  G* l# Y- V
    }
    8 h+ p* d4 V4 `. `8 Z, k+ X' J. p( d
    //判断字符串是否已经被bits标记
    4 w: j7 ?( T& T2 A  Y4 Lpublicboolean contains(String value)
    # r% r/ a# F2 P; N2 o' s5 K6 G5 G& ^6 t{& y: n% Q' j' Z3 T8 A3 l* z5 X( c9 f
    if (value ==null) 0 C- z( [9 Y6 q, ^: e8 B
    {
    ) i" ^" I+ m7 @2 _" f/ nreturnfalse;
    3 k4 D& z4 x7 H+ \8 c}
      w! S: \' C8 `boolean ret =true;
    : `4 G$ e$ g) o1 Z7 `for (SimpleHash f : func) ( \; i' Q4 {8 z+ G! S) e
    {
    4 _) t/ X% B, C2 E3 W- v; ^; Gret = ret && bits.get(f.hash(value));
    8 P* V1 J$ k* S1 p8 }" R& G  I% T}
    + E3 a8 n2 r) N* \4 V/ V% wreturn ret;+ @; S0 m) \* E$ @
    }( k" c, C  Y6 |& N- W" F
      V# }6 u7 u9 ?
    /* 哈希函数类 */+ Z; C/ O& ~6 \% `+ L
    publicstaticclass SimpleHash $ Y! [  L  v/ m' C( Y
    {* L7 b# F3 U( [4 R9 H
    privateint cap;  L! v* t- z3 ]
    privateint seed;4 _$ B+ y. q% T
    . E7 \, @% k  E# W: \3 c
    public SimpleHash(int cap, int seed)
    + G" g3 c$ y& |6 z; E, K% x{
    # i, L  M3 q: P8 ithis.cap = cap;
    & I: c/ ?/ H9 {$ @this.seed = seed;
    4 M0 C  P& K/ `+ m8 s0 {}1 V: l/ u/ ^( o+ _+ O, h  ]
    + s- m# ]$ ^2 a- j( x7 F
    //hash函数,采用简单的加权和hash& A! \& N  H: E/ T, v+ \
    publicint hash(String value)
    + X( K# k. q* E7 G{9 W6 P2 F+ R" n) W
    int result =0;$ K; S2 C$ N4 V! C3 V
    int len = value.length();
    ' }, m( N) E& _( k. D# f$ B6 cfor (int i =0; i < len; i++) " A8 I) [, M0 z* K1 j
    {
    6 ^0 c, l! P3 o3 K: C' G0 wresult = seed * result + value.charAt(i);
    6 ]$ F, N0 S0 _}
    & @- E: a0 F6 @6 W  Freturn (cap -1) & result;
    2 j" q5 B& _' N* @! \. }) ?}$ G$ j; _' P" f5 u0 c
    }; y% i3 ^1 ?. H5 [9 k2 i! U
    }2 n8 }  N& o0 ~8 M
    + a1 i9 V  S! K2 w: O
    [url=][/url]2 i% l6 s* D' U3 w" S5 @

    , R( M7 |, J! F6 A1 k* P5 p* r7 O& `/ z
    . \; d' H( L* o6 s8 Z6 x1 X
    7 `8 d* g% B  [" o+ h
    参考文献:

    6 M- d" B% P8 E/ R/ b/ m
    [1]Pei Cao. Bloom Filters - the math.
    http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
    [2]Wikipedia. Bloom filter.
    - l: J- V5 e$ U" X/ }6 W- |

    ; a( o3 D5 \$ r; T# z) f( S
    ! B# x7 l* b+ p* S; T
    1 ]: h* L7 V5 ^, z* r2 ~+ B6 r
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-4-12 17:41 , Processed in 0.865568 second(s), 51 queries .

    回顶部