这几天一直看到bloom filter这个算法。网上的资料很不错了,先摘录下,最后自己给出一个具体的应用。
bloom filter的wiki
几个应用
问题 写道
A和B中各存放着一亿条不重复的URL,URL存放时无序的,且URL是没有特征的,A和B可以试任意数据结构,也可以是存在数据库中。
如何找出A中有而B中没有的URL。
问题 写道
给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢?
关于bloom filter
写道
Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。
写道
Bloom Filter。它是一种基于随机数(或Hash)的数据结构,它支持对成员使用较少空间来存储,却能得到较高效率的查询。换句话说:在Bloom Filter 可以用于检索一个元素是否在一个集合中。
原理
建立一个容量为500万的Bit Array结构(Bit Array的大小和keyword的数量决定了误判的几率),将集合中的每个keyword通过32个hash函数分别计算出32个数字,然后对这32个数字分别用500万取模,然后将Bit Array中对应的位置为1,我们将其称为特征值。简单的说就是将每个keyword对应到Bit Array中的32个位置上,见下图:
当需要快速查找某个keyword时,只要将其通过同样的32个hash函数运算,然后映射到Bit Array中的对应位,如果Bit Array中的对应位全部是1,那么说明该keyword匹配成功。
适用范围
可以用来实现数据字典,进行数据的判重,或者集合求交集
扩展
Bloom filter将集合中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是否全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个counter,从而支持了元素的删除操作。Spectral Bloom Filter(SBF)将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。
关于错误率
其中:k标示hash函数的个数,m表示bit array的长度(位数),n表示实际数据的个数。
具体例子
注意:如果要测试,比较长的数据,需要调节jvm参数
-server -Xms800m -Xmx800m -XX:MaxNewSize=256m
//待比较的数据长度---对应公式中的N
private static final Integer dataLength = 400;
//bloom filter的bitArray辅助对象长度,对应公式中M
private static final Integer bitArrayLength = 5000;
//辅助对象,
//将 查找目标hash后的值用bitArrayLengrh取模后的结果 的位置 置为 true
private boolean[] bitArray = new boolean[bitArrayLength];
//本地数据集,可以存储在内存中,文件,数据库中
//在系统初始化时,需要将每个值 进行bloom filter处理,初始化bitArray
//这样,bitArray就相当于成为了一个带有“信息摘要”的密码本
private Integer[] data = new Integer[dataLength];
//hash函数库
private HashFunction hashFunction = new HashFunction();
/**
* @param args
*/
public static void main(String[] args) {
BloomFilter bloomFilter = new BloomFilter();
bloomFilter.init();
Scanner in = new Scanner(System.in);
while(in.hasNext()) {
int n = in.nextInt();
long old = System.currentTimeMillis();
boolean exsist = bloomFilter.check(n);
long nl = System.currentTimeMillis();
if(exsist) {
System.out.println("exsist " + (nl - old));
} else {
System.out.println("not exsist " + (nl - old));
}
}
}
private void init() {
//初始化数据
//在这里只是简单的进行数字赋值,具体应用可以从数据源读取
for(int i =0,j=0; i<dataLength; i++,j+=2) {
data[i] = j;//赋值
//bloom filter 核心算法
APHash(data[i]);
RSHash(data[i]);
JSHash(data[i]);
PJWHash(data[i]);
ELFHash(data[i]);
BKDRHash(data[i]);
SDBMHash(data[i]);
DJBHash(data[i]);
DEKHash(data[i]);
BPHash(data[i]);
}
}
//1.得到data的hash值
//2.将hash值与bitArrayLength模运算
//3.将此为的bitArrayLength置为true
private void APHash(Integer data) {
int temp = (int)hashFunction.APHash(data.toString());
int l1 = (temp < 0 ? -temp : temp) % bitArrayLength;
bitArray[l1] = true;
}
private boolean check(Integer n) {
if(n > (dataLength-1) * 2 || n < 0)
return false;
//进行验证,是否所有位均为true,如果有任何一位不是true则表明查找数据不存在
//注意,bloom filter是会存在误差,具体的误差请看wiki上的资料
if(APHashE(n) && RSHashE(n) && JSHashE(n) && PJWHashE(n) && ELFHashE(n) && BKDRHashE(n)
&& SDBMHashE(n) && DJBHashE(n) && DEKHashE(n) && BPHashE(n)) {
return true;
}
return false;
}
总结
如果能够接受误差(具体的误差率可以通过N,M,K的值来计算),就可以用bloom filter来处理判断集合中是否存在某元素的问题,同时空间使用率很低
参考:
http://www.hellodba.net/2009/04/bloom_filter.html
http://blog.redfox66.com/post/mass-data-topic-2-bloom-filter.aspx
分享到:
相关推荐
bitmap_bloomfilter_t *bbf = create_bitmap_bloomfilter(10000); /* 创建位数组 */ long *url[10] = { ... }; /* URL数组 */ for (i = 0; i ; ++i) { fprintf(stdout, "%ld -> filtered(%d).\n", url[i], bloom...
在Go语言中,实现Bloom Filter可以利用其高效并发处理和内存管理的优势,使得这种数据结构在大数据场景下更加实用。本文将深入探讨Bloom Filter的基本原理、Go语言中的实现以及其在实际应用中的优缺点。 ### 一、...
总之,Bloom Filter是处理大数据时的一个高效工具,虽然存在误判风险,但在很多场景下,这种风险是可以接受的,因为它能显著降低存储和查询成本。在C#环境中,利用其丰富的库和工具,我们可以方便地实现和应用Bloom ...
布隆过滤器(Bloom Filter)是一种空间效率很高的概率型数据结构,它用于判断一个元素是否在一个集合中。它的优势在于空间和时间效率,尤其适用于大数据场景,但缺点是有一定的误判率,即可能把不属于集合的元素错误...
8. **源码解析**:在名为"Bloom-Filter-master"的压缩包中,应该包含C语言实现Bloom Filter的源代码。通过阅读和分析源码,我们可以更深入理解上述概念是如何在实际程序中实现的,例如如何定义位数组,如何定义和...
6. 研究背景和目的:文章在引言部分强调了研究的背景和目的,即面对海量数据快速匹配的严峻问题,提出了一种结合分布式技术和Bloom Filter的解决方案,以期提升大数据环境下的数据检索性能。 7. 中图分类号:文章给...
"一种新的基于Bloom filter数据结构的数据消冗算法" 本文提出了一种新的基于Bloom filter数据结构的数据消冗算法,该算法首先利用完全文件检测算法对数据进行检验匹配,通过的数据块再利用CDC分块检测算法进行...
在bloom-0.1.0这个版本中,开发者可能已经实现了基本的Bloom Filter操作,包括添加元素、查询元素存在性以及可能的优化算法。通常,Bloom Filter的主要优点在于其空间效率和查询速度,但不可避免的是存在一定的误判...
**正文** ...总的来说,多字段矩阵型Bloom Filter是一种适用于大数据和分布式系统的高效数据结构,它通过扩展传统的Bloom Filter来处理多维度数据,并允许根据需求进行空间优化,以适应各种查询场景。
在上述代码中,我们定义了一个`BloomFilter`类,构造函数接受哈希函数的数量和位数组的大小作为参数。`add`方法用于添加元素到Bloom Filter中,它通过循环使用哈希函数来计算多个位置并把它们设置为1。`check`方法...
例如,使用布隆过滤器(Bloom Filter)进行初步判断,这是一种空间效率极高的概率型数据结构,用于测试一个元素是否在一个集合中。虽然可能会有假阳性,但不会出现假阴性,这在大数据去重中非常有用。此外,分布式...
在描述中提到的"bloom filter in c language fot atmega micro",意味着这个实现是专门为ATmega系列微控制器设计的。ATmega是Arduino常用的一种微控制器,通常用于嵌入式系统开发。因此,这个项目可能是为了在资源...
在压缩包中的`BloomFilter_-_Object_Pascal`文件中,很可能包含了用Delphi编写的布隆过滤器的源代码示例。源代码可能会定义一个BloomFilter类,包含初始化、插入和查询等方法,同时实现了多个哈希函数。通过阅读和...
大数据处理算法目录中,主要介绍了三种大数据处理算法:Bitmap 算法、Bloom Filter 算法和分而治之/Hash 映射 + Hash 统计 + 堆/快速/归并排序。 大数据处理算法一:Bitmap 算法 Bitmap 算法是一种常用的大数据...
在大数据存储和管理中,Bloom Filter是一种非常重要的数据结构,尤其在节省存储空间和高效查询方面具有显著优势。Bloom Filter由Burton Howard Bloom在1970年提出,它是一个概率型的数据结构,用于判断一个元素是否...
- 方案2:引入Bloom Filter,一个概率型数据结构,能在内存受限的情况下快速判断元素是否存在,但存在一定的误判率。 2. **query频度排序**: - 方案1:通过哈希函数将query分散到新的文件中,然后使用内存中的...
为了有效应对这些挑战,研究者们提出了一系列的算法来处理大数据。本文对常用的大数据处理算法进行总结,包括Bloom Filter、Hashing和Bit-Map等。 Bloom Filter是一种空间效率很高的概率型数据结构,用于判断一个...
在研究和实践过程中,作者郑黎明、邹鹏、韩伟红、李爱平、贾焰对骨干网异常检测的理解和解决方案,包括了对Filter-ary-Sketch和Bloom Filter数据结构的深入应用,为大数据环境下网络安全问题提供了新的解决途径。...
这些算法通常包括Count-Min Sketch、Count-Sketch、Bloom Filter和Top-K Sketch等。例如,Count-Min Sketch用于估算数据流中的元素频次,Bloom Filter则用于快速判断一个元素是否可能存在于数据集中,而Top-K Sketch...
9. **布隆过滤器 (Bloom Filter)**:虽然文档中没有提及,但它是另一个经典算法,用于高效地判断一个元素是否可能存在于大数据集中,牺牲一定的准确性来节省空间。 10. **Dijkstra最短路径算法**:同样没有直接提及...