1. 引言
问题:有1000瓶药,但是其中有一瓶是有毒的,小白鼠吃了24小时后就会死掉,请问,在24小时找出有毒的药物,最少需要多少只小白鼠?
答案是:10只,一只小白鼠可以表示2种状态,2^10可以表示1024种状态
分析可参考:http://lzj0470.iteye.com/blog/657579
通过二进制向量组来扩展描述的状态,Bloom Filter(BF)算法也是利用这个思想,其本质是上是一个
很长的二进制向量和一系列随机映射函数2. 概述
问题:快速判断一个元素是否在一个集合中
解决方法:一般来说,我们会用HASH表来存储集合中的数据,好处是快速准确,缺点是存储效率低,在海量数据时一般服务器无法存储。
BF是针对哈希表存储效率低的问题,而衍生出来的一种算法。
其通过利用二进制数组来描述一个集合,来判断一个元素是否属于这个集合
优点是:快速查找,并具有非常高的存储效率
缺点是:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合
3. 算法描述
BF包含:
1)一个m位的二进位数组,每一位初始化时置为0
2)k个相互独立的hash函数
算法:
针对一个n个元素的集合,通过k个hash函数,将集合中的每个元素都映射到二进位数组中,映射到的位置置为1
例如:对任意一个元素x,第i个哈希函数映射的位置hi(x)就会被置为1
在判断某个元素P是否在这个集合时,通过对P应用k次hash函数,判断其对应所有的位置都是1,如果是则认为P是集合中的元素,否则不是。
4. 最优位数组m大小及hash函数个数
在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合。因此,如何根据输入元素个数n,确定位数组m的大小及hash函数个数是一个非常重要的问题。
经过一些复杂的证明(可参考相关文档),可以得到:
1)当hash函数个数k=(ln2)*(m/n)时错误率最小
2)在错误率不大于E的情况 下,m至少要等于n*lg(1/E)才能表示任意n个元素的集合,但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)的1.44倍
5. 应用
有10亿个url,如何判断一个新的url是否在这个url的集合中?
一个url平均长度为52,如果用Hash表解决的话,由于Hash表的存储效率一般只有50%,因此10个url大概需要100G内存,一般服务器无法存储。
使用BF,要求错误率小于万分之一。
此时,输入元素n=10亿,最大错误率E=0.0001
可计算出:m=nlg(1/E)*1.44=57.6亿,大概需要7.2亿(57.6亿/8)个字节,即720M内存。
Hash函数个数:k=(ln2)*(m/n) 大概4个Hash函数
6.总结
BF通过牺牲一定的错误率来保证时间和空间(鱼与熊掌,不可兼得),目前被广泛应用于海量数据处理及数据库系统中。
例如,在Big table和Cassandra中,都使用BF作为索引结构。
P.S 针对BF的错误识别问题,可以通过建立白名单的方式解决。
参考文献:
paper:Network Applications of Bloom Filters: A Survey
http://blog.csdn.net/jiaomeng/article/details/1495500
问题:有1000瓶药,但是其中有一瓶是有毒的,小白鼠吃了24小时后就会死掉,请问,在24小时找出有毒的药物,最少需要多少只小白鼠?
答案是:10只,一只小白鼠可以表示2种状态,2^10可以表示1024种状态
分析可参考:http://lzj0470.iteye.com/blog/657579
通过二进制向量组来扩展描述的状态,Bloom Filter(BF)算法也是利用这个思想,其本质是上是一个
很长的二进制向量和一系列随机映射函数2. 概述
问题:快速判断一个元素是否在一个集合中
解决方法:一般来说,我们会用HASH表来存储集合中的数据,好处是快速准确,缺点是存储效率低,在海量数据时一般服务器无法存储。
BF是针对哈希表存储效率低的问题,而衍生出来的一种算法。
其通过利用二进制数组来描述一个集合,来判断一个元素是否属于这个集合
优点是:快速查找,并具有非常高的存储效率
缺点是:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合
3. 算法描述
BF包含:
1)一个m位的二进位数组,每一位初始化时置为0
2)k个相互独立的hash函数
算法:
针对一个n个元素的集合,通过k个hash函数,将集合中的每个元素都映射到二进位数组中,映射到的位置置为1
例如:对任意一个元素x,第i个哈希函数映射的位置hi(x)就会被置为1
在判断某个元素P是否在这个集合时,通过对P应用k次hash函数,判断其对应所有的位置都是1,如果是则认为P是集合中的元素,否则不是。
4. 最优位数组m大小及hash函数个数
在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合。因此,如何根据输入元素个数n,确定位数组m的大小及hash函数个数是一个非常重要的问题。
经过一些复杂的证明(可参考相关文档),可以得到:
1)当hash函数个数k=(ln2)*(m/n)时错误率最小
2)在错误率不大于E的情况 下,m至少要等于n*lg(1/E)才能表示任意n个元素的集合,但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)的1.44倍
5. 应用
有10亿个url,如何判断一个新的url是否在这个url的集合中?
一个url平均长度为52,如果用Hash表解决的话,由于Hash表的存储效率一般只有50%,因此10个url大概需要100G内存,一般服务器无法存储。
使用BF,要求错误率小于万分之一。
此时,输入元素n=10亿,最大错误率E=0.0001
可计算出:m=nlg(1/E)*1.44=57.6亿,大概需要7.2亿(57.6亿/8)个字节,即720M内存。
Hash函数个数:k=(ln2)*(m/n) 大概4个Hash函数
6.总结
BF通过牺牲一定的错误率来保证时间和空间(鱼与熊掌,不可兼得),目前被广泛应用于海量数据处理及数据库系统中。
例如,在Big table和Cassandra中,都使用BF作为索引结构。
P.S 针对BF的错误识别问题,可以通过建立白名单的方式解决。
参考文献:
paper:Network Applications of Bloom Filters: A Survey
http://blog.csdn.net/jiaomeng/article/details/1495500
分享到:
相关推荐
C# 海量数据处理算法BloomFilter算法的实现和测试例子;C# 海量数据处理算法BloomFilter算法的实现和测试例子
基于bloomfilter算法的c语言实验的url去重。使用的时候被去重的文件需要是txt格式的。
C语言实现的Bloomfilter算法。
Bloom filter是一个简明的空间效率极高的随机的数据结构。用Bloom filter 表示 cache 内容 ,可以高效地实现cache 协作。本文对BloomFilter及其改进型进行了综述性分析,探讨了它的实用性。
主要介绍了PHP中实现Bloom Filter算法,本文直接给出实现代码,代码中给出详细注释,Bloom Filter算法介绍等内容,需要的朋友可以参考下
自己写的Java抓图程序 原理见 http://blog.csdn.net/binyao02123202/archive/2010/07/12/5728840.aspx 用了序列化 线程 和BloomFilter算法
相似项发现主题中的shingling、simhash、bloom filter算法java实现,测试通过,附带测试数据。
bloom filter(布隆过滤器)应用很广泛的高效算法,研究研究
提出一种针对动态集合的矩阵型Bloom filter表示与查找法(matrix Bloom filter,MBF),它使用一个s×m位矩阵对数据集合进行哈希表示与查找,较同类算法SBF和DBF,能继承Bloom filter算法常数查找开销的基本精髓。
本程序主要是BloomFilter算法的简化实现 因为C#非安全代码无法直接分配内存块,使用了int型数组代替,暂时为了简单没有使用位运算,比位运算消耗内存多16倍。 算法原理: 其首先申请一块大内存,并把内存中...
转载:基于Bloom-Filter算法的URL过滤器的实现,算法简介,基本思想,应用,具体实现(C代码)
针对流与流之间传输的公平性问题,基于BLUE算法,结合Bloom filter,提出了一种改进的AQM算法EFBLUE。通过仿真实验对新算法从分组丢失率、吞吐量、延时等方面的性能进行了测试并与RED算法进行了性能对比。NS2仿真实验...
改进的Bloom filter主要将两个标准的Bloom filter组成二维并行Bloom filter,对RFID采集数据所包含的两个属性值tagID和readerID进行并行过滤。经实验可见,标准Bloom filter与哈希过滤(hash filter)相比具有明显的...
一种基于Bloomfilter的高速浮动关键词匹配算法,作者贾明志,适合学习存储时参考设计算法。
一个 CuckooFilter 的 Go 库, BloomFilter 的替代物
Go中的Cuckoo Filter 实现,比 Bloom Filter 更好