BloomFilter算法是在1970年提出的算法,具有很好的空间和时间效率,内部是依赖一些列hash算法和数组的。被用来检测一个元素是不是集合中的一个成员,允许有一定的出错率:如果某个数据被判断不在集合中,那么该数据就一定不会在这个集合中;由于hash会有碰撞存,那么如果判断某数据在集合内,这会种判断可能出错。一句话,就是判断为"false"的就一定不会有错,而判断为"true",则有可能出错。可见 Bloom filter 是牺牲了正确率换取时间和空间,
居于这种特性,我们可以把BloomFilter当成大数据快速排除算法。
它是hash快速查表的改良快速算法。
BloomFilter的特点:数据的插入和查询时间都是常数,另外它查询元素却不保存元素本身,具有良好的安全性。
BloomFilter的缺点:当插入的元素越多,错判“在集合内”的概率就越大了,另外 Bloom filter 也不能删除一个元素,因为多个元素哈希的结果可能在 BloomFilter 结构中占用的是同一个位,如果删除了一个比特位,可能会影响多个元素的检测。
Bloom filter 采用的是哈希函数的方法,将一个元素映射到一个 m 长度的阵列上的一个点,当这个点是 1 时,那么这个元素在集合内,反之则不在集合内。这个方法的缺点就是当检测的元素很多的时候可能有冲突,解决方法就是使用 k 个哈希 函数对应 k 个点,如果所有点都是 1 的话,那么元素在集合内,如果有 0 的话,元素则不在集合内。
在实际的应用中为了,可以使用“白名单”的方式和该算法来减少出错。
BloomFilter算法思想是这样的:创建一个数组或BitMap,将之全部初始化为0,然后选择创建几个不同的hash函数,放入数据的时候,将加入地数据通过这几个hash函数得出数据在数组或BitMap中的下表,并以此将按其下标将对应的数组或BitMap中的数据改为1;判断数据是否包含在集合中的时候,还是通过这几个hash函数获得相应的几个hash值——即数组或BitMap的下表,然后循环判断下表对应的数据结构中的数据,如果其中有一个不为1,就可以判断数据不包含在聚合中,否则标识包含在聚合中。由上述过程我们可以看到,当判断为判断某数包含在集合时,可能有误判。
BloomFilter跟单哈希函数Bit-Map不同之处在于:Bloom Filter使用了N个哈希函数,每个字符串跟N个bit对应,从而降低了冲突的概率。
下面让我们看一下数据是如何加入到BloomFilter的结构中的:
Bloom Filter参数选择
1)、哈希函数选择
哈希函数的选择对性能的影响应该是很大的,一个好的哈希函数要能近似等概率的将字符串映射到各个Bit。选择k个不同的哈希函数比较麻烦,一种简单的方法是选择一个哈希函数,然后送入k个不同的参数。
2)、Bit数组大小选择
哈希函数个数k、位数组大小m、加入的字符串数量n的关系,当 k = ln(2)* m/n 时出错的概率是最小的。
- 大小: 47.7 KB
分享到:
相关推荐
C语言实现的Bloomfilter算法。
基于bloomfilter算法的c语言实验的url去重。使用的时候被去重的文件需要是txt格式的。
自己写的Java抓图程序 原理见 http://blog.csdn.net/binyao02123202/archive/2010/07/12/5728840.aspx 用了序列化 线程 和BloomFilter算法
主要介绍了PHP中实现Bloom Filter算法,本文直接给出实现代码,代码中给出详细注释,Bloom Filter算法介绍等内容,需要的朋友可以参考下
本程序主要是BloomFilter算法的简化实现 因为C#非安全代码无法直接分配内存块,使用了int型数组代替,暂时为了简单没有使用位运算,比位运算消耗内存多16倍。 算法原理: 其首先申请一块大内存,并把内存中...
相似项发现主题中的shingling、simhash、bloom filter算法java实现,测试通过,附带测试数据。
提出一种针对动态集合的矩阵型Bloom filter表示与查找法(matrix Bloom filter,MBF),它使用一个s×m位矩阵对数据集合进行哈希表示与查找,较同类算法SBF和DBF,能继承Bloom filter算法常数查找开销的基本精髓。
使用delphi编写的bloom filter 算法
Bloom filter是一个简明的空间效率极高的随机的数据结构。用Bloom filter 表示 cache 内容 ,可以高效地实现cache 协作。本文对BloomFilter及其改进型进行了综述性分析,探讨了它的实用性。
1、本期内容 1.1 版权申明 1.2 内容详情 1.2.1 垂直搜索的应用场景 1.2.2 垂直搜索的技术...2.3 BloomFilter–大规模数据处理利器 2.3.1 应用场景 2.3.2 专业术语 2.3.3 Bloom Filter 算法 2.3.4 Bloom Filter 参数
针对流与流之间传输的公平性问题,基于BLUE算法,结合Bloom filter,提出了一种改进的AQM算法EFBLUE。通过仿真实验对新算法从分组丢失率、吞吐量、延时等方面的性能进行了测试并与RED算法进行了性能对比。NS2仿真实验...
ScrapyRedisBloomFilterBlockCluster 基于 scrapy-redis + bloomfilter 算法去重,支持分配多个 Redis 内存块( Redis 1个 string 最大 512MB),并且支持 Redis 单机,Redis Sentinel 和 Redis-Cluster 集群,适用...
改进的Bloom filter主要将两个标准的Bloom filter组成二维并行Bloom filter,对RFID采集数据所包含的两个属性值tagID和readerID进行并行过滤。经实验可见,标准Bloom filter与哈希过滤(hash filter)相比具有明显的...
一种基于Bloomfilter的高速浮动关键词匹配算法,作者贾明志,适合学习存储时参考设计算法。
首先对大规模微博数据进行分析,基于 Bloom Filter算法对数据进行去重处理,针对微博的特有结构,对文本进行预处理,提出改进的LDA主题模型So- cial Network LDA(SNLDA),采用吉布斯采样法进行模型推导,挖掘出微博...