`

算法系列-大数据系列-Bloom Filter

阅读更多

这几天一直看到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

分享到:
评论

相关推荐

    转载 : 基于Bloom-Filter算法的URL过滤器的实现.txt

    bitmap_bloomfilter_t *bbf = create_bitmap_bloomfilter(10000); /* 创建位数组 */ long *url[10] = { ... }; /* URL数组 */ for (i = 0; i ; ++i) { fprintf(stdout, "%ld -&gt; filtered(%d).\n", url[i], bloom...

    Go-bloom-Bloomfilters在Go中的实现

    在Go语言中,实现Bloom Filter可以利用其高效并发处理和内存管理的优势,使得这种数据结构在大数据场景下更加实用。本文将深入探讨Bloom Filter的基本原理、Go语言中的实现以及其在实际应用中的优缺点。 ### 一、...

    BloomFilter算法

    总之,Bloom Filter是处理大数据时的一个高效工具,虽然存在误判风险,但在很多场景下,这种风险是可以接受的,因为它能显著降低存储和查询成本。在C#环境中,利用其丰富的库和工具,我们可以方便地实现和应用Bloom ...

    大数据算法导论第四周

    布隆过滤器(Bloom Filter)是一种空间效率很高的概率型数据结构,它用于判断一个元素是否在一个集合中。它的优势在于空间和时间效率,尤其适用于大数据场景,但缺点是有一定的误判率,即可能把不属于集合的元素错误...

    C语言实现的Bloomfilter算法。.zip

    8. **源码解析**:在名为"Bloom-Filter-master"的压缩包中,应该包含C语言实现Bloom Filter的源代码。通过阅读和分析源码,我们可以更深入理解上述概念是如何在实际程序中实现的,例如如何定义位数组,如何定义和...

    基于Bloom Filter的海量数据分布式快速匹配算法研究.pdf

    6. 研究背景和目的:文章在引言部分强调了研究的背景和目的,即面对海量数据快速匹配的严峻问题,提出了一种结合分布式技术和Bloom Filter的解决方案,以期提升大数据环境下的数据检索性能。 7. 中图分类号:文章给...

    一种新的基于Bloom filter数据结构的数据消冗算法.pdf

    "一种新的基于Bloom filter数据结构的数据消冗算法" 本文提出了一种新的基于Bloom filter数据结构的数据消冗算法,该算法首先利用完全文件检测算法对数据进行检验匹配,通过的数据块再利用CDC分块检测算法进行...

    Python库 | bloom-0.1.0.tar.gz

    在bloom-0.1.0这个版本中,开发者可能已经实现了基本的Bloom Filter操作,包括添加元素、查询元素存在性以及可能的优化算法。通常,Bloom Filter的主要优点在于其空间效率和查询速度,但不可避免的是存在一定的误判...

    多字段矩阵型bloomfilter(支持砍维度)

    **正文** ...总的来说,多字段矩阵型Bloom Filter是一种适用于大数据和分布式系统的高效数据结构,它通过扩展传统的Bloom Filter来处理多维度数据,并允许根据需求进行空间优化,以适应各种查询场景。

    PHP中实现Bloom Filter算法

    在上述代码中,我们定义了一个`BloomFilter`类,构造函数接受哈希函数的数量和位数组的大小作为参数。`add`方法用于添加元素到Bloom Filter中,它通过循环使用哈希函数来计算多个位置并把它们设置为1。`check`方法...

    行业文档-设计装置-消息队列大数据去重处理方法.zip

    例如,使用布隆过滤器(Bloom Filter)进行初步判断,这是一种空间效率极高的概率型数据结构,用于测试一个元素是否在一个集合中。虽然可能会有假阳性,但不会出现假阴性,这在大数据去重中非常有用。此外,分布式...

    Bloom_filter_(C).zip_Flooding_atmega_bloom_bloom filter

    在描述中提到的"bloom filter in c language fot atmega micro",意味着这个实现是专门为ATmega系列微控制器设计的。ATmega是Arduino常用的一种微控制器,通常用于嵌入式系统开发。因此,这个项目可能是为了在资源...

    bloom filter

    在压缩包中的`BloomFilter_-_Object_Pascal`文件中,很可能包含了用Delphi编写的布隆过滤器的源代码示例。源代码可能会定义一个BloomFilter类,包含初始化、插入和查询等方法,同时实现了多个哈希函数。通过阅读和...

    大数据处理算法.pdf

    大数据处理算法目录中,主要介绍了三种大数据处理算法:Bitmap 算法、Bloom Filter 算法和分而治之/Hash 映射 + Hash 统计 + 堆/快速/归并排序。 大数据处理算法一:Bitmap 算法 Bitmap 算法是一种常用的大数据...

    大数据存储系统与管理1

    在大数据存储和管理中,Bloom Filter是一种非常重要的数据结构,尤其在节省存储空间和高效查询方面具有显著优势。Bloom Filter由Burton Howard Bloom在1970年提出,它是一个概率型的数据结构,用于判断一个元素是否...

    常见算法面试题--海量数据专题.doc

    - 方案2:引入Bloom Filter,一个概率型数据结构,能在内存受限的情况下快速判断元素是否存在,但存在一定的误判率。 2. **query频度排序**: - 方案1:通过哈希函数将query分散到新的文件中,然后使用内存中的...

    常用大数据量、海量数据处理方法__算法总结.pdf

    为了有效应对这些挑战,研究者们提出了一系列的算法来处理大数据。本文对常用的大数据处理算法进行总结,包括Bloom Filter、Hashing和Bit-Map等。 Bloom Filter是一种空间效率很高的概率型数据结构,用于判断一个...

    基于Filter-ary-Sketch数据结构的骨干网异常检测研究.pdf

    在研究和实践过程中,作者郑黎明、邹鹏、韩伟红、李爱平、贾焰对骨干网异常检测的理解和解决方案,包括了对Filter-ary-Sketch和Bloom Filter数据结构的深入应用,为大数据环境下网络安全问题提供了新的解决途径。...

    Sketch算法所用数据

    这些算法通常包括Count-Min Sketch、Count-Sketch、Bloom Filter和Top-K Sketch等。例如,Count-Min Sketch用于估算数据流中的元素频次,Bloom Filter则用于快速判断一个元素是否可能存在于数据集中,而Top-K Sketch...

    当今世界最为经典的十大算法-投票进行时.pdf

    9. **布隆过滤器 (Bloom Filter)**:虽然文档中没有提及,但它是另一个经典算法,用于高效地判断一个元素是否可能存在于大数据集中,牺牲一定的准确性来节省空间。 10. **Dijkstra最短路径算法**:同样没有直接提及...

Global site tag (gtag.js) - Google Analytics