BloomFilter(布隆过滤器)

页面导航:首页 > 数据库 > DB2 > BloomFilter(布隆过滤器)

BloomFilter(布隆过滤器)

来源: 作者: 时间:2016-01-13 16:35 【

布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制矢量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间

  布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制矢量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。
  如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为O(n),O(log n),O(n/k)。

  布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。

  \

  若一个字符串对应的bit不全为1,则肯定没有;
  若一个字符串对应的Bit全为1,不一定有,因为有可能该字符串的所有位都刚好是被其他字符串所对应,这种情况称为false positive 。<喎"http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPqGhoaHXotLio7rX1rf7tK6808jruvO+zbG7srvE3Mm+s/3By6Os0vLOqsm+s/274dOwz+y1vcbky/vX1rf7tK6hozxiciAvPg0KoaGhocj00OjSqsm+s/3X1rf7tK6jrL/J0tTKudPDY291bnRpbmcgYmxvb20gZmlsdGVyKENCRimjrNXiysfSu9bWu/mxvmJsb29tIGZpbHRlcrXEseTM5aOsQ0JGvau7+bG+Ymxvb20gZmlsdGVyw7/Su7j2Yml0uMTOqtK7uPa8xsr9xvejrNXi0fm+zb/J0tTKtc/Wyb6z/dfWt/u0rrXEuabE3MHLoaM8YnIgLz4NCqGhoaE8YnIgLz4NCqGhoaG008nPw+bO0sPHv8nS1L+0tb1ibG9vbSBmaWx0ZXLW99Kq09DI/bj2ss7K/aO6PGJyIC8+DQqhoaGho7GjqbTmtKLX1rf7tK61xLj2yv1uPGJyIC8+DQqhoaGho7KjqSC5/s+juq/K/bj2yv1rPGJyIC8+DQqhoaGho7Ojqc67yv3X6bTz0KFtPC9wPg0KPHA+oaGhoc7Sw8fAtLfWzvbPwqO6PGJyIC8+DQqhoaGhyPSy5cjr0ru49tfWt/u0rqOszrvK/dfpYml0zrtqyc+7uc6qMLXEuMXCys/UyLvOqigxLTEvbSleazxiciAvPg0KoaGhocTHw7TO0sPHsuXI62649tfWt/u0rqOszrvK/dfpYml0zrtqyc+7uc6qMLXEuMXCys/UyLvOqjxiciAvPg0KKDEtMS9tKV5rbiZhc3ltcDtlXigta24vbSk8YnIgLz4NCqGhoaG8tMSz0rvOu86qMbXEuMXCynDOqqO6MS0gZV4oLWtuL20po6zEx8O0ttTT2sv509BruPa5/s+juq/K/aGhoaG21NOma867trzOqjGjqLPlzbujqbXEuMXCymbOqqO6KDEtIGVeKC1rbi9tKSApXms8YnIgLz4NCqGhoaG21MnPyr3H87W8x/O8q9a1o6y1w2s9bG4yICZ0aW1lczsgbSAvbsqxyKG1w9fu0KHWtaOstMvKsXDUvM6qMS8yKG0vMiBiaXRzIDEsIG0vMiBiaXRzIDApPGJyIC8+DQqhoaGhZiA9ICgxLXApo95rICZhc3ltcDsgKD8po95rID0oPymj3ihsbiAyKW0vbiAmYXN5bXA7ICgwLjYxODUpo95tL248L3A+DQo8cD6hoaGhyOe5+20gPSA4biwgdGhlbjxiciAvPg0KoaGhoSBrID0gOChsbiAyKSA9IDUuNTQ1ICh1c2UgNiBoYXNoIGZ1bmN0aW9ucyk8YnIgLz4NCqGhoaEgZiAmYXN5bXA7ICgwLjYxODUpbS9uID0gKDAuNjE4NSk4ICZhc3ltcDsgMC4wMiAoMiUgZmFsc2UgcG9zaXRpdmVzKTxiciAvPg0KoaGhoSBDb21wYXJlIHRvIGEgaGFzaCB0YWJsZTogZiAmYXN5bXA7IDEgJm5kYXNoOyBlLW4vbSA9IDEtZS0xLzggJmFzeW1wOyAwLjExPC9wPg0KPHByZSBjbGFzcz0="brush:sql;"> add(T item) { for(int i = 0; i < k; i++) array[hi(item)] = 1; } contains(T item) { for(int i = 0; i < k; i++) if(!array[hi(item)]) return false; return true; }

  Bloom Filter通过允许少量的错误来节省大量的存储空间,但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。
  另外,一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

Counting Bloom Filter

   \

  Insertion : increment counter
  Deletion : decrement counter
  Overflow : keep bit 1 forever

  为了避免计数溢出,计数必须要有足够的位数。
  我们先计算第i个Counter被增加j次的概率,其中n为集合元素个数,k为哈希函数个数,m为Counter个数(对应着原来位数组的大小):

   \

  上面等式右端的表达式中,前一部分表示从nk次哈希中选择j次,中间部分表示j次哈希都选中了第i个Counter,后一部分表示其它nk – j次哈希都没有选中第i个Counter。因此,第i个Counter的值大于j的概率可以限定为:
  
   \

add(T item)
{
  for(int i = 0; i < k; i++)
   array[hi(item)]++;
}

contains(T item)
{
  for(int i = 0; i < k; i++)
  if(!array[hi(item)])
   return false;
  return true;
}

remove(T item)
{
  for(int i = 0; i < k; i++)
  array[hi(item)]--;
}

应用举例:
  1)HTTP缓存服务器、Web爬虫等
  主要工作是判断一条URL是否在现有的URL集合之中(可以认为这里的数据量级上亿)。
  对于HTTP缓存服务器,当本地局域网中的PC发起一条HTTP请求时,缓存服务器会先查看一下这个URL是否已经存在于缓存之中,如果存在的话就没有必要去原始的服务器拉取数据了(为了简单起见,我们假设数据没有发生变化),这样既能节省流量,还能加快访问速度,以提高用户体验。
  对于Web爬虫,要判断当前正在处理的网页是否已经处理过了,同样需要当前URL是否存在于已经处理过的URL列表之中。

  2)垃圾邮件过滤
  假设邮件服务器通过发送方的邮件域或者IP地址对垃圾邮件进行过滤,那么就需要判断当前的邮件域或者IP地址是否处于黑名单之中。如果邮件服务器的通信邮件数量非常大(也可以认为数据量级上亿),那么也可以使用Bloom Filter算法。

Tags:

相关文章

    文章评论

    最 近 更 新
    热 点 排 行
    Js与CSS工具
    代码转换工具
    
    <