布隆过滤器-原理介绍[通俗易懂]

布隆过滤器-原理介绍[通俗易懂]一、布隆过滤器概念引入     (BloomFilter)是由布隆(BurtonHowardBloom)在1970年提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成,布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率(假正例Falsepositives,即BloomFilter报告某一元素存在

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

一、布隆过滤器概念引入

      (Bloom Filter)是由布隆(Burton Howard Bloom)在1970年提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成,布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率(假正例False positives,即Bloom Filter报告某一元素存在于某集合中,但是实际上该元素并不在集合中)和删除困难,但是没有识别错误的情形(即假反例False negatives,如果某个元素确实在该集合中,那么Bloom Filter 是不会报告该元素不存在于集合中的,所以不会漏报)。

      下面从简单的排序谈到BitMap算法,再谈到数据去重问题,谈到大数据量处理利器:布隆过滤器。

  • 对无重复的数据进行排序

      给定数据(2,4,1,12,9,7,6)如何对它排序?

     方法1:基本的排序方法包括冒泡,快排等。

     方法2:使用BitMap算法

     方法1就不介绍了,方法2中所谓的BitMap是一个位数组,跟平时使用的数组的唯一差别在于操作的是位。首先是开辟2个字节大小的位数组,长度为12(该长度由上述数据中最大的数字12决定的),然后,读取数据,2存放在位数组中下标为1的地方,值从0改为1,4存放在下标为3的地方,值从0改为1….最后,读取该位数组,得到排好序的数据是:(1,2,4,6,7,9,12)。

      比较方法1和方法2的差别:方法2中,排序需要的时间复杂度和空间复杂度很依赖与数据中最大的数字比如12,因此空间上讲需要开2个字节大小的内存,时间上需要遍历完整个数组。当数据类似(1,1000,10万)只有3个数据的时候,显然用方法2,时间复杂度和空间复杂度相当大,但是当数据比较密集时该方法就会显示出来优势。

  • 对有重复的数据进行判重

   数据(2,4,1,12,2,9,7,6,1,4)如何找出重复出现的数字?

   首先是开辟2个字节大小的位数组,长度为12(该长度由上述数据中最大的数字12决定的,当读取完12后,当读取2的时候,发现数组中的值是1,则判断出2是重复出现的。

二、布隆过滤器原理

      布隆过滤器需要的是一个位数组(这个和位图有点类似)和k个映射函数(和Hash表类似),在初始状态时,对于长度为m的位数组array,它的所有位都被置为0。对于有n个元素的集合S={s1,s2……sn},通过k个映射函数{f1,f2,……fk},将集合S中的每个元素sj(1<=j<=n)映射为k个值{g1,g2……gk},然后再将位数组array中相对应的array[g1],array[g2]……array[gk]置为1;如果要查找某个元素item是否在S中,则通过映射函数{f1,f2…..fk}得到k个值{g1,g2…..gk},然后再判断array[g1],array[g2]……array[gk]是否都为1,若全为1,则item在S中,否则item不在S中。这个就是布隆过滤器的实现原理。

      当然有读者可能会问:即使array[g1],array[g2]……array[gk]都为1,能代表item一定在集合S中吗?不一定,因为有这个可能:就是集合中的若干个元素通过映射之后得到的数值恰巧包括g1,g2,…..gk,那么这种情况下可能会造成误判,但是这个概率很小,一般在万分之一以下。

      很显然,布隆过滤器的误判率和这k个映射函数的设计有关,到目前为止,有很多人设计出了很多高效实用的hash函数。尤其要注意的是,布隆过滤器是不允许删除元素的(实际就是因为多个str可能都应设在同一点,而判断str存在的话是所有映射点都存在,所以不能删除),因为若删除一个元素,可能会发生漏判的情况。不过有一种布隆过滤器的变体Counter Bloom Filter,可以支持删除元素,感兴趣的读者可以查阅相关文献资料。

三、布隆过滤器False positives 概率推导

      假设 Hash 函数以等概率条件选择并设置 Bit Array 中的某一位,m 是该位数组的大小,k 是 Hash 函数的个数,那么位数组中某一特定的位在进行元素插入时的 Hash 操作中没有被置位为1的概率是:布隆过滤器-原理介绍[通俗易懂]那么在所有 k 次 Hash 操作后该位都没有被置 “1” 的概率是:布隆过滤器-原理介绍[通俗易懂]如果我们插入了 n 个元素,那么某一位仍然为 “0” 的概率是:布隆过滤器-原理介绍[通俗易懂]因而该位为 “1”的概率是:布隆过滤器-原理介绍[通俗易懂]现在检测某一元素是否在该集合中。标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 “1”,但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中(False Positives),该概率由以下公式确定:布隆过滤器-原理介绍[通俗易懂]

      其实上述结果是在假定由每个 Hash 计算出需要设置的位(bit) 的位置是相互独立为前提计算出来的,不难看出,随着 m (位数组大小)的增加,假正例(False Positives)的概率会下降,同时随着插入元素个数 n 的增加,False Positives的概率又会上升,对于给定的m,n,如何选择Hash函数个数 k 由以下公式确定:布隆过滤器-原理介绍[通俗易懂]此时False Positives的概率为:布隆过滤器-原理介绍[通俗易懂]而对于给定的False Positives概率 p,如何选择最优的位数组大小 m 呢,布隆过滤器-原理介绍[通俗易懂]该式表明,位数组的大小最好与插入元素的个数成线性关系,对于给定的 m,n,k,假正例概率最大为:布隆过滤器-原理介绍[通俗易懂]

四、布隆过滤器应用

      布隆过滤器在很多场合能发挥很好的效果,比如:网页URL的去重,垃圾邮件的判别,集合重复元素的判别,查询加速(比如基于key-value的存储系统)等,下面举几个例子:

  • 有两个URL集合A,B,每个集合中大约有1亿个URL,每个URL占64字节,有1G的内存,如何找出两个集合中重复的URL。

很显然,直接利用Hash表会超出内存限制的范围。这里给出两种思路:

      第一种:如果不允许一定的错误率的话,只有用分治的思想去解决,将A,B两个集合中的URL分别存到若干个文件中{f1,f2…fk}和{g1,g2….gk}中,然后取f1和g1的内容读入内存,将f1的内容存储到hash_map当中,然后再取g1中的url,若有相同的url,则写入到文件中,然后直到g1的内容读取完毕,再取g2…gk。然后再取f2的内容读入内存。。。依次类推,知道找出所有的重复url。

      第二种:如果允许一定错误率的话,则可以用布隆过滤器的思想。

  • 在进行网页爬虫时,其中有一个很重要的过程是重复URL的判别,如果将所有的url存入到数据库中,当数据库中URL的数

量很多时,在判重时会造成效率低下,此时常见的一种做法就是利用布隆过滤器,还有一种方法是利用berkeley db来存储url,Berkeley db是一种基于key-value存储的非关系数据库引擎,能够大大提高url判重的效率。

      布隆过滤器主要运用在过滤恶意网址用的,将所有的恶意网址建立在一个布隆过滤器上,然后对用户的访问的网址进行检测,如果在恶意网址中那么就通知用户。这样的话,我们还可以对一些常出现判断错误的网址设定一个白名单,然后对出现判断存在的网址再和白名单中的网址进行匹配,如果在白名单中,那么就放行。当然这个白名单不能太大,也不会太大,布隆过滤器错误的概率是很小的。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/188917.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • 无穷小分析理论_无穷小是一个过程

    无穷小分析理论_无穷小是一个过程一般读者对无穷小微积分只是略知一二,其实这是不够的。现将有关文章引用如下,供读者参考。袁萌 12月23日非标准分析概念又可称为实无穷小分析)(英语:Non-standardanalysis)是一个数学分支,它用严格定义的无穷小的数(infinitesimalnumber)的概念来构建数学分析大厦。1历史2动机2.1历史上的原因2.2教学上的原因2.3技术上的原因3无穷小分析的各种建立

    2022年8月11日
    5
  • 004-protostuff踩坑-java bean新增字段反序列化失败问题

    004-protostuff踩坑-java bean新增字段反序列化失败问题protostuff避免更改java对象字段,比如新增一个,导致redis等缓存的数据反序列化失败问题??问题重现:我们有个方法通过attrKey查询List,同时方法中有缓存,会优先查询缓存,没有读库,然后写缓存返回。方法伪代码如下:publicvoidsetId(StringattrKey){//从缓存查询List<ConfAttr>attrValues=cacheClient.get(attrKey);

    2022年5月7日
    173
  • intentservice使用(Intention)

    IntentService,更好用的Service说起IntentService就需要先了解一下Service。Service是长期运行在后台的应用程序组件。Service不是一个单独的进程,它和应用程序在同一个进程中,Service也不是一个线程,它和线程没有任何关系,所以它不能直接处理耗时操作。如果直接把耗时操作放在Service的onStartCommand()中,…

    2022年4月18日
    35
  • Linux命令—tail 加过滤功能

    Linux命令—tail 加过滤功能tail-n 行数-f 文件夹路径以及名字,用于查看log 后面可以追加 |grep +名字 用于过滤ps aux|grep 文件 查看执行情况 tail-n40-f/home/logs/info.log|grepkeyword …

    2022年5月23日
    196
  • 输入法个性化怎么设置_手机输入键盘怎么个性化设置

    输入法个性化怎么设置_手机输入键盘怎么个性化设置个性化设置技巧(补充输入法)子墨居士前言本次的内容大部分为推送。本打算自己推荐几款比较好用的桌面整理软件,然而最近事情越来越多,这部分的内容分享已经有很多不错的文章。就允许我偷一次懒呗(…

    2025年6月29日
    2
  • How AHI Fintech and DataVisor are Securing Data through AI and Big Data

    How AHI Fintech and DataVisor are Securing Data through AI and Big Data

    2022年4月2日
    48

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号