温州网站建设(首选国鼎网络),广告公司企业简介怎么写,什么是静态网站,上海提供虚拟注册地址的园区一、概念
Bloom Filter的中文翻译叫做布隆过滤器#xff0c;是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法#xff0c;缺点是有一定的误…一、概念
Bloom Filter的中文翻译叫做布隆过滤器是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法缺点是有一定的误识别率和删除困难。如文章标题所述本文只是做简单介绍属于科普文章。
二、应用场景
在正式介绍Bloom Filter算法之前先来看看什么时候需要用到Bloom Filter算法。
1. HTTP缓存服务器、Web爬虫等 主要工作是判断一条URL是否在现有的URL集合之中可以认为这里的数据量级上亿。 对于HTTP缓存服务器当本地局域网中的PC发起一条HTTP请求时缓存服务器会先查看一下这个URL是否已经存在于缓存之中如果存在的话就没有必要去原始的服务器拉取数据了为了简单起见我们假设数据没有发生变化这样既能节省流量还能加快访问速度以提高用户体验。对于Web爬虫要判断当前正在处理的网页是否已经处理过了同样需要当前URL是否存在于已经处理过的URL列表之中。2. 垃圾邮件过滤 假设邮件服务器通过发送方的邮件域或者IP地址对垃圾邮件进行过滤那么就需要判断当前的邮件域或者IP地址是否处于黑名单之中。如果邮件服务器的通信邮件数量非常大也可以认为数据量级上亿那么也可以使用Bloom Filter算法。 几个专业术语 这里有必要介绍一下False Positive和False Negative的概念更形象的描述可以阅读第4条参考。 False Positive中文可以理解为“假阳性”形象的一点说就是“误报”后面将会说道Bloom Filter存在误报的情况现实生活中也有误报比如说去体检的时候医生告诉你XXX检测是阳性而实际上是阴性也就是说误报了是假阳性杀毒软件误报也是同样的概念。False Negative中文可以理解为“假阴性”形象的一点说是“漏报”。医生告诉你XXX检测为阴性实际上你是阳性你是有病的Sorry, it’s just a joke那就是漏报了。同样杀毒软件也存在漏报的情况。三、Bloom Filter算法
初始状态下Bloom Filter是一个m位的位数组且数组被0所填充。同时我们需要定义k个不同的hash函数每一个hash函数都随机的将每一个输入元素映射到位数组中的一个位上。那么对于一个确定的输入我们会得到k个索引。
插入元素经过k个hash函数的映射我们会得到k个索引我们把位数组中这k个位置全部置1不管其中的位之前是0还是1
查询元素输入元素经过k个hash函数的映射会得到k个索引如果位数组中这k个索引任意一处是0那么就说明这个元素不在集合之中如果元素处于集合之中那么当插入元素的时候这k个位都是1。但如果这k个索引处的位都是1被查询的元素就一定在集合之中吗答案是不一定也就是说出现了False Positive的情况但Bloom Filter不会出现False Negative的情况) 在上图中当插入x、y、z这三个元素之后再来查询w会发现w不在集合之中而如果w经过三个hash函数计算得出的结果所得索引处的位全是1那么Bloom Filter就会告诉你w在集合之中实际上这里是误报w并不在集合之中。 False Positive Rate
Bloom Filter的误报率到底有多大下面在数学上进行一番推敲。假设HASH函数输出的索引值落在m位的数组上的每一位上都是等可能的。那么对于一个给定的HASH函数在进行某一个运算的时候一个特定的位没有被设置为1的概率是 那么对于所有的k个HASH函数都没有把这个位设置为1的概率是 如果我们已经插入了n个元素那么对于一个给定的位这个位仍然是0的概率是 那么如果插入n个元素之后这个位是1的概率是 如果对一个特定的元素存在误报那么这个元素的经过HASH函数所得到的k个索引全部都是1概率也就是 根据常数e的定义可以近似的表示为 关于误报
有时候误报对实际操作并不会带来太大的影响比如对于HTTP缓存服务器如果一条URL被误以为存在与缓存服务器之中那么当取数据的时候自然会无法取到最终还是要从原始服务器当中获取之后再把记录插入缓存服务器几乎没有什么不可以接受的。 对于安全软件有着“另可错报不可误报”的说法如果你把一个正常软件误判为病毒对使用者来说不会有什么影响如果用户相信是病毒那么就是删除这个文件罢了如果用户执意要执行那么后果也只能由用户来承担如果你把一个病毒漏判了那么对用户造成的后果是不可设想的……更有甚者误报在某种程度上能让部分用户觉得你很专业……
参考资料
1. Bloom Filter 算法简介 (增加 Counting Bloom Filter 内容
