Java版本的BloomFilter (布隆过滤器)

哈哈...我终于写了个BloomFilter

这个是干嘛用的???


恩...一般比较常见的应用是字符串去重..也就是...恩..就是采集网址去重.防止重复采集

下面是我自己写的个例子

BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("D:\\Users\\caiqing\\workspace\\CQ\\library\\dictionary-utf8.TXT"),"UTF-8")) ;
		String str = null ;
		System.out.println("begin");
		long start = System.currentTimeMillis() ;
		while((str=br.readLine())!=null){
			if(bf.containsAndAdd(str)){
				System.out.println("containsAndAdd:"+str);
			}
		}
		
		br.close() ;
		
		br = new BufferedReader(new InputStreamReader(new FileInputStream("D:\\Users\\caiqing\\workspace\\CQ\\library\\dictionary-utf8.TXT"),"UTF-8")) ;
			System.out.println("begin-find");
			start = System.currentTimeMillis() ;
			while((str=br.readLine())!=null){
				if(!bf.contains(str)){
					System.out.println("contains:"+str);
				}
			}
			
		System.out.println(System.currentTimeMillis()-start);
		br.close() ;

对分词词典79962个词进行插入.和查重..准确率100%.算上IO时间耗时79毫秒...

源码我放到下面了大家可以下载..还有..要的人给个评论吧..我的博客好冷清啊


今天回来用我的过滤器做了个测试哎...效果不是很理想啊..在千万级数据还行.再大就不好办啦



重新抄袭了一些经典的算法...(哎中科院老师的算法有毛病有三个Hash算法都是白给的.也许是我从c转到java没写对吧..)  现在效率1亿..64m内存大约失误率是0.0013  12m的失误个数是44..另外我吧能加的hash都加上了.这里只测试了5个..哈哈
我很满意非常满意....请大家敬请下载吧

10000000
32m:0
64m:0
128m:0

100000000
64m:146546
128m:44
256m:0

评论

10 楼 assasszt 2015-04-15  

请问 能不能加入写入文件功能，不然的话 是每次 执行 都是一个新的 吗？上一次执行 加入的 是不是就  不再里面了呢？

9 楼 lhj_6270 2014-12-23  

楼主不错。果然不是一般人。再接再厉弄个软件出来。

8 楼 tuoxinzhou 2013-12-31  

不错哦。加油

7 楼 tuoxinzhou 2013-11-26  

加油，不知道现在还有没有继续新的东东啊，最近在研究这个，很高兴看到你的博客。

6 楼 bzq19881115 2013-11-21  

最近需要学习学习！

5 楼 rick_liao 2012-10-18  

学习了，谢谢

4 楼 happyITLife 2012-06-06  

为什么不给个完整的呢?

3 楼 ericlyf 2011-09-20  

不错不错，学习了

2 楼 flootball 2011-09-20  

很少研究这个，先顶哈。

1 楼 xingcxb 2011-09-15  

     记得当年去外企面试的时候搞了个类似的陷阱，跳进去出不来....