【引言】
在日常生活中,包括在设计计算机软件时,我们经常要判断一个元素是否在一个集合中。比如在字处理软件中,需要检查一个英语单词是否拼写正确(也就是要判断 它是否在已知的字典中);在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上;在网络爬虫里,一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中,遇到一个新 元素时,将它和集合中的元素直接比较即可。一般来讲,计算机中的集合是用哈希表(hash table)来存储的。它的好处是快速准确,缺点是费存储空间。当集合比较小时,这个问题不显著,但是当集合巨大时,哈希表存储效率低的问题就显现出来
了。比如说,一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件(email)提供商,总是需要过滤来自发送垃圾邮件的人(spamer)的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址,全世界少说也有几十亿个发垃圾邮件的地址,将他们都存起来则需要大量的网络服务器。如果用哈希表,每存储一亿 个 email 地址, 就需要 1.6GB 的内存(用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹(详见:数学之美之信息指纹),
然后将这些信息指纹存入哈希表,由于哈希表的存储效率一般只有 50%,因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB, 即十六亿字节的内存)。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机,一般服务器是无法存储的。
今天我们就介绍一个一种称作布隆过滤器的数学工具,它只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。
(数学之美)
【简介】
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。
布隆过滤器可以用于检索一个元素是否在一个集合中。
它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。
【工作原理】
我们通过上面的电子邮件的例子来说明工作原理。
假定存储以一亿个电子邮件地址,先建立一个16亿二进制(比特),即两亿字节的向量,然后将这16亿个二进制位全部清零。
对于每一个电子邮件的地址X,用8个不同的随机数产生器(F1,F2.........F8)产生8个信息指纹(f1,f2,......f8)。
在用一个随机数产生器G把这8个信息指纹映射到1-16亿中的8个自然数g1,g2.....g8。现在把这9个位置全部设置为1。对这一亿个电子邮件都这样处理之后,一个针对这些
电子邮件地址布隆过滤器就建成了。
现在,让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址Y是否是在黑名单中。用相同的8个随机数(F1,F2,....F8)产生器对这个地址产生
8个信息指纹(s1,s2,.....s8),然后将这8个信息指纹对应到布隆过滤器的8个二进制位,分别是t1,t2,....t8。
如果Y在黑名单中,显然,t1,t2,...t8对应8个二进制位一定为1。这样如果再遇到黑名单中的电子邮件地址都能准确的发现。
说白了就是原理很简单,用位数组和k个不同的HASH函数。将HASH函数对应的值的位数组置1,查找时如果发现所有HASH函数对应位都是1说明存在。
【集合表示和元素查询】
下面我们具体来看布隆过滤器是如何用位数组表示集合的。初始状态时,布隆过滤器是一个包含m位的位数组,每一位都置为0。
为了表达S={x1, x2,…,xn}这样一个n个元素的集合,布隆过滤器使用k个相互独立的哈希函数(Hash ),它们分别将集合中的每个元素映射到{1,…,m}的范围中。
对任意一个元素x,第i个哈希函数映射的位置h(i,x)就会被置为1(1≤i≤k,代表第i个哈希函数)。
注意,如果一个位置多次被置为1,那么只有第一次会起作用,后面几次将没有任何效果。
在下图中,k=3,且有两个哈希函数选中同一个位置(从左边数第五位)。
在判断y是否属于这个集合时,我们对y应用k次哈希函数,如果所有h(i,y)的位置都是1(1≤i≤k),那么我们就认为y是集合中的元素,否则就认为y不是集合中的元素。
下图中y1就不是集合中的元素。y2或者属于这个集合,或者刚好是一个false positive。
【误识别问题】
(引用于数学之美)
从这个公式可以看出:
k = ln2 * m / n时 p 最小
何根据输入元素个数n,确定位数组m的大小及hash函数个数。
当hash函数个数k = ln2 * m / n时错误率最小。
在错误率p不大于E的情况 下:
推出:
在错误率不大于E的情况 下,m至少要等于才能表示任意n个元素的集合。
但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应 该大于等于 大概就是nlg(1/E)1.44倍。
布隆过滤器背后的数学原理在于两个完全随机的数学冲突峰概率很小,因此,可以在很小的无识别率的条件下,用很小的空间存储大量的信息。
【适用范围】
可以用来实现数据字典,进行数据的判重,或者集合求交集
分享到:
相关推荐
下面是一个简单的布隆过滤器的C/C++实现,以及使用例程。使用sdbmhash字符串hash方法来进行hash。
LevelDB 学习笔记1:布隆过滤器.doc
使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,
做成dll可以在很多场合使用,如自己写爬虫,要判断一个url是否已经访问过,判断一个单词是否在某个字典内,当集合很大的时候,用布隆过滤器很有优势,不过使用前,请了解它的优缺点(缺点是有一定的误判率)
布隆过滤器,大家学过数据结构的应该都清楚,一般的字典树要实现嵌入和查找都内存的消耗非常大,布隆过滤器有BloomFilter,string, BKDRHash, APHash, DJBHash> bf五个参数你要查找的元素个数,查找元素类型,三个...
PDD – 基于高级布隆过滤器算法用于高效得删除数据流中的近似重复数据
比如在字处理软件中,需要检查一个英语单词是否拼写正确(也就是要判断它是否在已知的字典中);在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上;在网络爬虫里,一个网址是否被访问过等等。最直接的方法就是将集合中...
自制布隆过滤器,采用八种不同哈希函数来获取随机数,错误率低
布隆过滤器JavaScript实现 用法 要在您的项目中使用BloomJS,只需从dist目录中导入bloom.min.js文件即可! 构造函数: var bloom = new Bloom(k, m, n, hashFunction) k :散列数量,默认为Math.max(Math.round(m ...
布隆过滤器在网页去重中的应用 , 海量数据处理中的一个绝好应用
基于布隆过滤器和聚簇技术的大规模WSN服务发现算法,薛寒寒,王柏,针对大规模WSN节点资源受限,难以快速、准确、节能的进行服务发现问题,提出一种基于布隆过滤器BF(bloom filter)和聚簇技术的大规模W
一个简单的golang布隆过滤器
布隆过滤器C源码
布隆过滤器的python库,通过python setup.py install安装
布隆过滤器是空间高效的概率 数据结构,通过设想伯顿霍华德布卢姆于1970年,是用于测试一个是否元件是一个的成员组。可能会出现假阳性匹配,但否定否定匹配-换句话说,查询返回“可能在集合中”或“绝对不在集合中”...
基于布隆过滤器的字符串模糊匹配算法的FPGA实现.pdf
基于Redis的布隆过滤器,内含scrapy示例程序,github地址:https://github.com/kongtianyi/BloomFilterRedis
Bloomfilter布隆过滤器技术分享PPT。 介绍了布隆过滤器的使用方法与适用场景等。 适合用于技术分享。
布隆过滤器 源码 java版 /** * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published by * the Free Software ...
自动清空过滤器内部信息的使用比率,传null则表示不会自动清理,当过滤器使用率达到100%时,则无论传入什么数据,都会认为在数据已经存在了当希望过滤器使用率达到80%时自动清空重新使用,则传入0.8