QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1484|回复: 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) 编辑 收藏  |: Z4 G/ }# a0 x- [
    BloomFilter——大规模数据处理利器
      Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。
    9 N  m* P9 ?/ H, [
    . 实例
      为了说明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的一个映射位。
    ; j7 O1 Y. E; ]
      以上方法在数据量较小的情况下都能完美解决问题,但是当数据量变得非常庞大时问题就来了。
      方法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实际上没有没网络蜘蛛访问,而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。
    5 U* q$ P1 G9 f
    . 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 。

    - w1 J( M' s# e9 g4 Z: L4 i
    (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个二进制位了。

    , e$ _  o3 k% W" `4 A
    (2) 检查字符串是否存在的过程
    , i* l, }; T7 `, M7 @6 q2 e
      下面是检查字符串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存在。
      w1 o) k8 w8 ~3 Y) S) q- d
      若一个字符串对应的Bit不全为1,则可以肯定该字符串一定没有被Bloom Filter记录过。(这是显然的,因为字符串被记录过,其对应的二进制位肯定全部被设为1了)
      但是若一个字符串对应的Bit全为1,实际上是不能100%的肯定该字符串被Bloom Filter记录过的。(因为有可能该字符串的所有位都刚好是被其他字符串所对应)这种将该字符串划分错的情况,称为false positive 。

    % G) t8 C3 v+ Y
    (3) 删除字符串过程
       字符串加入了就被不能删除了,因为删除会影响到其他字符串。实在需要删除字符串的可以使用Counting bloomfilter(CBF),这是一种基本Bloom Filter的变体,CBF将基本Bloom Filter每一个Bit改为一个计数器,这样就可以实现删除字符串的功能了。

    & ]7 z/ E9 Z0 J
      Bloom Filter跟单哈希函数Bit-Map不同之处在于:Bloom Filter使用了k个哈希函数,每个字符串跟k个bit对应。从而降低了冲突的概率。
    1 i+ w% l5 k/ ^8 |+ ^& g& s; U
    . Bloom Filter参数选择
    5 ^0 R. j8 d) L/ o+ t
       (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 ,这个概率基本能满足网络爬虫的需求了。  

    3 Y& b9 F, ?# o
    . Bloom Filter实现代码
        下面给出一个简单的Bloom Filter的Java实现代码:
    ' A6 J/ q1 q( k# X- W& o
    [url=][/url]
    $ D) O. `* a. ^/ K# ~; Q% ~import java.util.BitSet;
    + O% c8 t  I! M: |. S; V( v+ Z" d4 e6 @- W" `
    publicclass BloomFilter $ a( C$ f. O" O1 d  R
    {& Y" l) M' ^- L
    /* BitSet初始分配2^24个bit */
    ( O- Z; m6 r. G* r8 ^9 H$ tprivatestaticfinalint DEFAULT_SIZE =1<<25;
    4 @8 J  j9 t- n$ T$ v* C1 o/* 不同哈希函数的种子,一般应取质数 */; \) r$ }7 e, i. ~/ J
    privatestaticfinalint[] seeds =newint[] { 5, 7, 11, 13, 31, 37, 61 };
    7 U+ n) x$ A+ X% i# m" _private BitSet bits =new BitSet(DEFAULT_SIZE);
    ' p+ D3 ?  D/ Y" Y5 }% g! r4 q" v/* 哈希函数对象 */
    : R' A3 Z3 ]4 w$ L- ]private SimpleHash[] func =new SimpleHash[seeds.length];
    - v# i0 b8 c' a- M) f
    2 f/ @1 R- F- M  c3 K: f+ _public BloomFilter()
    8 E/ S/ P( L9 C2 a8 G{
    7 _; R3 H5 e: Q9 O4 [" p! `0 ?for (int i =0; i < seeds.length; i++): U! E) ~7 }4 C3 p
    {
    / x( a% i! g  Nfunc =new SimpleHash(DEFAULT_SIZE, seeds);% Z4 Q: @8 }7 d  q% y
    }
    5 U$ u# r) }  A, V/ }$ X}& X+ f- a. d4 @
    8 F# B" `4 _: u* F, \7 H% u
    // 将字符串标记到bits中
    1 Q2 p/ M& b$ K% [$ M, {  s, S' Z& ypublicvoid add(String value) . {# @2 l8 Q/ X
    {
    # v% _# X# p  J$ Ofor (SimpleHash f : func)
    0 [. A3 ?- j) p% n3 [5 A) H{
    8 [6 S/ z  U  xbits.set(f.hash(value), true);4 k. s) }. q9 B( t
    }
    2 H3 C7 w) x: c( e! i- H' `}; [8 y* M  d& \# T" i

    : ?2 u* l, j: I* n: Q//判断字符串是否已经被bits标记% p) X+ {% s( X9 b& I" e) J
    publicboolean contains(String value)
    * b9 @; s) j: m% {9 e5 Y{; K) d, K9 z; Y" }$ E% g9 x
    if (value ==null)
    $ z8 _# j8 h! j1 j{8 X, ]3 V) F$ f  z* {  [/ Y
    returnfalse;- Q7 [' I2 Z: Z( b" ?3 S" B( k
    }
    % t/ @; I! _: K1 U6 H# ^8 H4 lboolean ret =true;$ @  I3 ?# `* z3 g' L  Q6 o1 z
    for (SimpleHash f : func)
    8 q# S* `5 u. b4 i{: R9 d2 W) I* |; M
    ret = ret && bits.get(f.hash(value));
    8 T, r1 j2 @; Q7 Y3 b/ u. Q1 M' i}
    " k' y) a" s+ t0 M' \8 Rreturn ret;* [9 q3 z: z, l( V( G8 r" Y- b/ Y
    }
    * }4 ]; r: [7 @0 T- o7 D
    7 d2 c( p; X4 j2 u7 P( Z/* 哈希函数类 */
    0 b3 N9 `9 e2 q% G, Z0 Dpublicstaticclass SimpleHash
    & H. E# y, @2 l  H& R8 p  ~% G{
    % D7 W- G/ r/ aprivateint cap;
    3 \9 b) j" X- jprivateint seed;4 J! Z& N6 S) L: E% x; d$ q4 C$ k

    , |5 t0 {/ g: F, ]2 W! bpublic SimpleHash(int cap, int seed)
    5 ^, N7 o' W. P8 x{
    * I: a- v. K2 i6 l1 ^8 Fthis.cap = cap;3 |0 A/ r1 K  I' j5 T" G& O8 f
    this.seed = seed;
    ; X0 i0 l4 e- |! |+ N}) ]: g! Q- K- a' H! _. ]

    . E6 u! H& s7 i& ?! m) S& X6 k//hash函数,采用简单的加权和hash
    $ s6 ~7 U: \# Y( V, spublicint hash(String value)
    . L+ ?* p  @) w# I/ b2 R{! w3 b  k6 u5 c$ t
    int result =0;
    * \/ w& t/ h; Rint len = value.length();
    3 y- r) z1 m# efor (int i =0; i < len; i++) 7 }1 i1 M5 h& x- j
    {
    $ i9 a! l8 }# ?' }0 _3 Lresult = seed * result + value.charAt(i);
    5 |* l- J2 b8 z% v}
    ' z% M+ z: A' L. O/ ereturn (cap -1) & result;
    5 v# @; Z" X  ~4 \- R}; w0 X- K; W7 l# h
    }; [$ B+ B! Z" t8 ~, x6 ~' F9 p) E2 F
    }
      b6 P7 t  Q4 ^6 D- Y

    ) ?8 H! `& X# s) k  j1 K[url=][/url]
    * ?( ?$ w8 O# a5 B" p8 t2 x( r' Q" |, q) J, B7 L7 b* x; _
    . n4 Y, z2 l3 S! T' ^

    ) j. C/ h1 k/ A
    : m( i1 [3 W) n+ j
    参考文献:
      u4 I, X: r3 }4 e
    [1]Pei Cao. Bloom Filters - the math.
    http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
    [2]Wikipedia. Bloom filter.
    , i4 q4 `6 K/ t1 L) Z+ ~; [

    ) s% n* _1 e8 K) ^) E9 K6 J+ ~
    : L1 s4 s# i: g2 ?& ?+ Y- n. q: j. q2 u. I3 `$ W0 Y3 @
    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-6-14 13:46 , Processed in 0.304475 second(s), 50 queries .

    回顶部