- 浏览: 337656 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
pacoson:
感谢楼主。请受小生一拜。
ANT预编译JSP -
zhuhongming123:
一楼的同学Lucene4.* 以上的 已经改成了Numeric ...
Lucene日期排序及组合查询 -
ywjk520:
RangeQuery在哪个包里?
Lucene日期排序及组合查询 -
willwen:
有个疑问,楼主,为何初始化bits 从txt读取已有的网址是直 ...
布隆过滤器(Bloom Filter)之java实例 -
yu_226528:
还不如没有呢
jFreeChart 在jsp页上实现简单的折线图、柱状图
在日常生活中,包括在设计计算机软件时,我们经常要判断一个元素是否在一个集合中。比如在字处理软件中,需要检查一个英语单词是否拼写正确(也就是要判断它是否在已知的字典中);在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上;在网络爬虫里,一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中,遇到一个新元素时,将它和集合中的元素直接比较即可。一般来讲,计算机中的集合是用哈希表(hash table)来存储的。它的好处是快速准确,缺点是费存储空间。当集合比较小时,这个问题不显著,但是当集合巨大时,哈希表存储效率低的问题就显现出来了。比如说,一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件(email)提供商,总是需要过滤来自发送垃圾邮件的人(spamer)的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址,全世界少说也有几十亿个发垃圾邮件的地址,将他们都存起来则需要大量的网络服务器。如果用哈希表,每存储一亿个 email 地址, 就需要 1.6GB 的内存(用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹 googlechinablog.com/2006/08/blog-post.html,然后将这些信息指纹存入哈希表,由于哈希表的存储效率一般只有 50%,因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB, 即十六亿字节的内存)。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机,一般服务器是无法存储的。
今天,我们介绍一种称作布隆过滤器的数学工具,它只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。
布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。我们通过上面的例子来说明起工作原理。
假定我们存储一亿个电子邮件地址,我们先建立一个十六亿二进制(比特),即两亿字节的向量,然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X,我们用八个不同的随机数产生器(F1,F2, ...,F8) 产生八个信息指纹(f1, f2, ..., f8)。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, ...,g8。现在我们把这八个位置的二进制全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。(见下图)
现在,让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中。我们用相同的八个随机数产生器(F1, F2, ..., F8)对这个地址产生八个信息指纹 s1,s2,...,s8,然后将这八个指纹对应到布隆过滤器的八个二进制位,分别是 t1,t2,...,t8。如果 Y 在黑名单中,显然,t1,t2,..,t8 对应的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址,我们都能准确地发现。
布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。但是,它有一条不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中,因为有可能某个好的邮件地址正巧对应个八个都被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率。在上面的例子中,误识概率在万分之一以下。
布隆过滤器的好处在于快速,省空间。但是有一定的误识别率。常见的补救办法是在建立一个小的白名单,存储那些可能别误判的邮件地址。
package com.huigao.util; import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.util.BitSet; public class BloomFilter { private int defaultSize = 5000 << 10000; private int basic = defaultSize -1; private String key = null; private BitSet bits = new BitSet(defaultSize); public BitSet getBits() { return bits; } public void setBits(BitSet bits) { this.bits = bits; } public BloomFilter(){ } public BloomFilter(String key){ this.key = key; } private int[] lrandom(String key){ int[] randomsum = new int[8]; int random1 = hashCode(key,1); int random2 = hashCode(key,2); int random3 = hashCode(key,3); int random4 = hashCode(key,4); int random5 = hashCode(key,5); int random6 = hashCode(key,6); int random7 = hashCode(key,7); int random8 = hashCode(key,8); randomsum[0] = random1; randomsum[1] = random2; randomsum[2] = random3; randomsum[3] = random4; randomsum[4] = random5; randomsum[5] = random6; randomsum[6] = random7; randomsum[7] = random8; return randomsum; } /* private int[] sameLrandom(){ int[] randomsum = new int[8]; int random1 = hashCode(key,1); int random2 = hashCode(key,1); int random3 = hashCode(key,1); int random4 = hashCode(key,1); int random5 = hashCode(key,1); int random6 = hashCode(key,1); int random7 = hashCode(key,1); int random8 = hashCode(key,1); randomsum[0] = random1; randomsum[1] = random2; randomsum[2] = random3; randomsum[3] = random4; randomsum[4] = random5; randomsum[5] = random6; randomsum[6] = random7; randomsum[7] = random8; return randomsum; } */ private void add(String key){ if(exist( key)){ System.out.println("已经包含("+key+")"); return; } int keyCode[] = lrandom(key); bits.set(keyCode[0]); bits.set(keyCode[1]); bits.set(keyCode[2]); bits.set(keyCode[3]); bits.set(keyCode[4]); bits.set(keyCode[5]); bits.set(keyCode[6]); bits.set(keyCode[7]); } private boolean exist(String key){ int keyCode[] = lrandom(key); if(bits.get(keyCode[0])&& bits.get(keyCode[1]) &&bits.get(keyCode[2]) &&bits.get(keyCode[3]) &&bits.get(keyCode[4]) &&bits.get(keyCode[5]) &&bits.get(keyCode[6]) &&bits.get(keyCode[7])){ return true; } return false; } // private boolean set0(){ // if(exist()){ // int keyCode[] = lrandom(); // bits.clear(keyCode[0]); // bits.clear(keyCode[1]); // bits.clear(keyCode[2]); // bits.clear(keyCode[3]); // bits.clear(keyCode[4]); // bits.clear(keyCode[5]); // bits.clear(keyCode[6]); // bits.clear(keyCode[7]); // return true; // } // return false; // } private int hashCode(String key,int Q){ int h = 0; int off = 0; char val[] = key.toCharArray(); int len = key.length(); for (int i = 0; i < len; i++) { h = (30 + Q) * h + val[off++]; } return changeInteger(h); } private int changeInteger(int h) { return basic & h; } public void saveBit(String filename){ try { File file=new File(filename); ObjectOutputStream oos=new ObjectOutputStream(new FileOutputStream(file,false)); oos.writeObject(bits); oos.flush(); oos.close(); } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } } public BitSet readBit(String filename){ BitSet bits=new BitSet(defaultSize); File file=new File(filename); if(!file.exists()){ return bits; } try { ObjectInputStream ois=new ObjectInputStream(new FileInputStream(file)); bits=(BitSet)ois.readObject(); ois.close(); } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } catch (ClassNotFoundException e) { e.printStackTrace(); } return bits; } public static void main(String[] args) { String fileName="c:\\test\\BloomFilter.txt"; String url="http://www.agrssdddd.com/"; BloomFilter bf=new BloomFilter(); BitSet bitSet=bf.readBit(fileName); bf.setBits(bitSet); bf.add(url); System.out.println(bf.exist(url)); bf.saveBit(fileName); /* BloomFilter f = new BloomFilter("http://www.agrilink.cn/"); f.add(); System.out.println(f.exist()); */ // f.set0(); // System.out.println(f.exist()); } }
评论
bf.setBits(bitSet);
为何不需要对txt文件中的网址逐个调用add方法,即为何不需要逐个调用lrandom方法,谢谢!
String mk;
if(j < 10)
mk = "0" + j;
else
mk = String.valueOf(j);
System.out.println(mk + "->" + (5000 << j));
}
结果:
01->10000
02->20000
03->40000
04->80000
05->160000
06->320000
07->640000
08->1280000
09->2560000
10->5120000
11->10240000
12->20480000
13->40960000
14->81920000
15->163840000
16->327680000
17->655360000
18->1310720000
19->-1673527296
20->947912704
21->1895825408
22->-503316480
23->-1006632960
24->-2013265920
25->268435456
26->536870912
27->1073741824
28->-2147483648
29->0
30->0
31->0
32->5000
33->10000
34->20000
35->40000
36->80000
37->160000
38->320000
39->640000
40->1280000
41->2560000
42->5120000
43->10240000
44->20480000
45->40960000
46->81920000
47->163840000
48->327680000
49->655360000
50->1310720000
51->-1673527296
52->947912704
53->1895825408
54->-503316480
55->-1006632960
56->-2013265920
57->268435456
58->536870912
59->1073741824
这行写得太潇洒了……
这个的确是够潇洒的。。[
这行写得太潇洒了……
发表评论
-
Lucene查询语法详解
2010-07-16 10:55 1187Lucene提供了丰富的API来 ... -
使用Lucene的Highlighter实现文件摘要的自动提取
2010-07-03 15:19 1382使用Lucene自带的Highlighter就可以实现对原始文 ... -
ICTCLAS 中科院分词系统 代码 注释 中文分词 词性标注
2010-04-16 15:45 1745中科院分词系统概述 这几天看完了中科院分词程序的代码,现在来 ... -
Lucene日期排序及组合查询
2009-11-19 14:31 4757public class SearchUtil { //索 ... -
Lucene中自定义排序的实现
2009-11-07 17:59 911使用Lucene来搜索内容,搜索结果的显示顺序当然是比较重要 ... -
在Lucene中应用poading进行分词
2009-11-07 17:52 12141、下载poading解牛 http://code.googl ... -
用Lucene实现摘要的高亮点
2009-11-07 17:46 1342注明:该类主要是符合本 ... -
Lucene日期索引搜索
2009-11-07 17:42 1401注意使用lucene的版本,调试本例的时候,作者使用的是luc ... -
Lucene 中文引擎,庖丁解牛的辞典参数配置方法
2009-11-07 16:34 1964随机文档指示可以在环境变量里配置。原文如下 庖丁中文分词需要一 ... -
Lucene 2.4更新索引的方法(Update Index)
2009-11-07 16:32 2016在Lucene里面没有update方法,我查了文档,我们只能删 ... -
庖丁解牛的Lucene 2.4的全文搜索代码
2009-11-07 16:30 1362package com.laozizhu.article.ut ... -
Lucene 搜索方式
2009-11-07 16:23 1110Lucene有多种搜索方式, ... -
转一篇lucene的使用的文章,写的比较全
2009-11-07 16:20 9171 lucene简介 1.1 什么是lucene Lucene ...
相关推荐
布隆过滤器Bloom Filters的一个简单Java库
自制布隆过滤器,采用八种不同哈希函数来获取随机数,错误率低
布隆过滤器是一种数据结构,主要用于判断一个元素是否可能在一个集合中存在。它可以在插入和查询数据时快速地判断一个元素是否可能在这个集合中,比如在缓存中查询一个元素是否存在。 它的原理是使用多个哈希函数对...
使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,
Bloomfilter布隆过滤器技术分享PPT。 介绍了布隆过滤器的使用方法与适用场景等。 适合用于技术分享。
布隆去重工具类,感兴趣的了解一下。
布隆过滤器C源码
布隆过滤器,大家学过数据结构的应该都清楚,一般的字典树要实现嵌入和查找都内存的消耗非常大,布隆过滤器有BloomFilter,string, BKDRHash, APHash, DJBHash> bf五个参数你要查找的元素个数,查找元素类型,三个...
下面小编就为大家带来一篇布隆过滤器(Bloom Filter)的Java实现方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
C++实现的布隆过滤器,其中使用到的bitset也是自己简单实现的一个BitContainer。可以处理千万条到亿条记录的存在性判断。做成dll可以在很多场合使用,如自己写爬虫,要判断一个url是否已经访问过,判断一个单词是否...
硬核 - Redis 布隆(Bloom Filter)过滤器原理与实战.doc
bloom filter布隆过滤器学习资料大全,收集了很多相关的论文,并总结了各种布隆过滤器的变种
布隆过滤器的一个Go实现,参考bloomfilter.js
布隆过滤器 源码 java版 /** * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published by * the Free Software ...
介绍Bloom Filter(布隆过滤器)原理、实现及具体应用,包含9个不同PPT及PDF文档资料,对Bloom Filter感兴趣、想学习的同学可以下载查看下
bloom filter 布隆过滤器,这是源码,简单易学易用
主要介绍了布隆过滤器(bloom filter)介绍以及php和redis实现布隆过滤器实现方法,非常不错,具有一定的参考借鉴价值,需要的朋友可以参考下
布隆过滤器在网页去重中的应用 , 海量数据处理中的一个绝好应用
布隆过滤器的简单实现,从谷歌的levelDB摘取过来,做了源码的注释很好理解
Java 实现的高性能布隆过滤器!.zip,Advanced Bloom Filter Based Algorithms for Efficient Approximate Data De-Duplication in Streams