专栏首页算法工程师之路数学之美:布隆过滤器

数学之美:布隆过滤器

算法题目

如果一个黑名单网站包含100亿个黑名单网页,每个网页最多占64B,设计一个系统,判断当前的URL是否在这个黑名单当中,要求额外空间不超过30GB,允许误差率为万分之一。

解题思路:布隆过滤器

基础介绍

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量(位图)和一系列随机映射函数(哈希函数)。 布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。

实际工程的应用

实际上,布隆过滤器广泛应用于网页黑名单系统、垃圾邮件过滤系统、爬虫网址判重系统等,有人会想,我直接将网页URL存入数据库进行查找不就好了,或者建立一个哈希表进行查找不就OK了。

当数据量小的时候,这么思考是对的,但如果整个网页黑名单系统包含100亿个网页URL,在数据库查找是很费时的,并且如果每个URL空间为64B,那么需要内存为640GB,一般的服务器很难达到这个需求。

那么,在这种内存不够且检索速度慢的情况下,不妨考虑下布隆过滤器,但业务上要可以忍受判断失误率。

布隆过滤器结构图

位图(bitmap)

布隆过滤器其中重要的实现就是位图的实现,也就是位数组,并且在这个数组中每一个位置只占有1个bit,而每个bit只有0和1两种状态。如上图bitarray所示!bitarray也叫bitmap,大小也就是布隆过滤器的大小。

假设一种有k个哈希函数,且每个哈希函数的输出范围都大于m,接着将输出值对k取余(%m),就会得到k个[0, m-1]的值,由于每个哈希函数之间相互独立,因此这k个数也相互独立,最后将这k个数对应到bitarray上并标记为1(涂黑)。

等判断时,将输入对象经过这k个哈希函数计算得到k个值,然后判断对应bitarray的k个位置是否都为1(是否标黑),如果有一个不为黑,那么这个输入对象则不在这个集合中,也就不是黑名单了!如果都是黑,那说明在集合中,但有可能会误,由于当输入对象过多,而集合也就是bitarray过小,则会出现大部分为黑的情况,那样就容易发生误判!因此使用布隆过滤器是需要容忍错误率的,即使很低很低!

布隆过滤器重要参数计算

通过上面的描述,我们可以知道,如果输入量过大,而bitarray空间的大小又很小,那么误判率就会上升。那么bitarray空间大小怎么确定呢?不要慌,已经有人通过数据推倒出公式了!!!哈哈,直接用~

假设输入对象个数为n,bitarray大小(也就是布隆过滤器大小)为m,所容忍的误判率p和哈希函数的个数k。计算公式如下:(小数向上取整

计算公式

注意:由于我们计算的m和k可能是小数,那么需要经过向上取整,此时需要重新计算误判率p!

假设一个网页黑名单有URL为100亿,每个样本为64B,失误率为0.01%,经过上述公式计算后,需要布隆过滤器大小为25GB,这远远小于使用哈希表的640GB的空间。

并且由于是通过hash进行查找的,所以基本都可以在O(1)的时间完成!

布隆过滤器的测试

测试用例来自GitHub的CPP版的布隆过滤器! GitHub地址:https://github.com/ArashPartow/bloom

测试数据展示 我们关心的主要是Queries列和FPQ列,可以看出,输入对象为1万多个时也会出现错误的访问,当然概率极低的,那么如果我们一直增加Queries的次数,其误判率是怎么样的!

测试数据展示 我们可以看到作者一共测试到了1715万次输入,而平均的误判率为0.00023738,充分说明了布隆过滤器的有效性。如果想要了解底层的话,可以去看看源码学习学习!

本文分享自微信公众号 - 算法工程师之路(Zleopard7319538)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PrestaShop 网站漏洞修复如何修复

    PrestaShop网站的漏洞越来越多,该网站系统是很多外贸网站在使用的一个开源系统,从之前的1.0初始版本到现在的1.7版本,经历了多次的升级,系统使用的人也...

    网站安全专家
  • 网站被百度停止推广并提示网站存在安全风险,不宜推广的处理方案

    春节刚过完,上班的第一天,公司网站被百度停止推广了,百度推广提示:您的url被百度杀毒提示存在网址安全风险,故物料不宜推广;若有异议,请进入百度杀毒申诉通道申诉...

    网站安全专家
  • 压力测试工具siege的用法

    Siege是linux下的一个web系统的压力测试工具,支持多链接,支持get和post请求,可以对web系统进行多并发下持续请求的压力测试。

    卡二条的技术圈子
  • PHP工程师学Python数据类型

    继上篇文章比较了PHP与Python语法之后,这周又学习了Python数据类型,准备从通过这篇文章给自己进行一些总结,也给其他读者一些参考。

    汤青松
  • 网站漏洞检测工具对discuzX3.2 X3.4网站漏洞修复

    2018年12月9日,国内某安全组织,对discuz X3.2 X3.4版本的漏洞进行了公开,这次漏洞影响范围较大,具体漏洞是discuz 的用户前段SQL注入...

    网站安全专家
  • Webpack系列——Webpack + xxx配合使用

    在webpack中使用Babel通过使用babel-loader即可,babel中的配置可以通过options选项进行配置。 安装:

    用户1515472
  • javascript跨域无需修改服务器端

    由于img标签可以跨域,因此在onload和onerror事件中可以请求跨域,只能get请求,无法访问服务器的响应文本,只能用于单向通信。

    战神伽罗
  • 动手实现一个JSONP

    JSONP的原理就不细说了,就是利用script可以跨域的特点来实现跨域,首先我们考虑一个最简单的jsonp,就是简简单单创建script标签, 添加url的...

    用户1515472
  • Rails路由

    在创建资源路由时,会同时创建多个可以在控制器中使用的辅助方法,如上面的资源路由会创建以下方法:

    用户1515472
  • 爬爬更健康

    爬取淘宝商品的信息,数据主要用于分析市场趋势,从而制定一系列营销方案。实现功能如下:

    公众号---志学Python

扫码关注云+社区

领取腾讯云代金券