- 浏览: 347673 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
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 1229Lucene提供了丰富的API来 ... -
使用Lucene的Highlighter实现文件摘要的自动提取
2010-07-03 15:19 1413使用Lucene自带的Highlighter就可以实现对原始文 ... -
ICTCLAS 中科院分词系统 代码 注释 中文分词 词性标注
2010-04-16 15:45 1829中科院分词系统概述 这几天看完了中科院分词程序的代码,现在来 ... -
Lucene日期排序及组合查询
2009-11-19 14:31 4911public class SearchUtil { //索 ... -
Lucene中自定义排序的实现
2009-11-07 17:59 954使用Lucene来搜索内容,搜索结果的显示顺序当然是比较重要 ... -
在Lucene中应用poading进行分词
2009-11-07 17:52 12501、下载poading解牛 http://code.googl ... -
用Lucene实现摘要的高亮点
2009-11-07 17:46 1389注明:该类主要是符合本 ... -
Lucene日期索引搜索
2009-11-07 17:42 1433注意使用lucene的版本,调试本例的时候,作者使用的是luc ... -
Lucene 中文引擎,庖丁解牛的辞典参数配置方法
2009-11-07 16:34 2011随机文档指示可以在环境变量里配置。原文如下 庖丁中文分词需要一 ... -
Lucene 2.4更新索引的方法(Update Index)
2009-11-07 16:32 2070在Lucene里面没有update方法,我查了文档,我们只能删 ... -
庖丁解牛的Lucene 2.4的全文搜索代码
2009-11-07 16:30 1399package com.laozizhu.article.ut ... -
Lucene 搜索方式
2009-11-07 16:23 1154Lucene有多种搜索方式, ... -
转一篇lucene的使用的文章,写的比较全
2009-11-07 16:20 9841 lucene简介 1.1 什么是lucene Lucene ...
相关推荐
布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。在Java开发中,特别是在处理大数据、内存限制或需要快速查询是否存在某个元素的场景下,布隆过滤器是一个...
布隆过滤器(Bloom Filter)是一种空间效率极高...通过这个“bloom filter布隆过滤器学习资料大全”,你可以深入研究布隆过滤器的理论、算法实现以及在不同场景下的应用实例,提升对这一重要数据结构的理解和应用能力。
布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。它可能会误判,但不会漏判,即可能存在假阳性(False Positive),但绝不会有假阴性(False Negative)。...
要使用Redisson实现布隆过滤器,我们需要在SpringBoot应用中引入Redisson的依赖,配置Redis连接,并创建对应的BloomFilter实例。在代码中,我们可以调用`bf.add()`方法向过滤器添加元素,使用`bf.contains()`方法...
在Redis中,`BF`(Bloom Filter)命令集提供了对布隆过滤器的操作。例如,`BF.ADD`用于添加元素,`BF.MADD`可以一次添加多个元素,`BF.EXISTS`用来检查元素是否存在,`BF.SCAND`则允许批量查询元素。这些命令的设计...
要使用Python-cljcbloom,开发者需要安装库,然后导入并创建布隆过滤器实例,添加元素,最后进行查询。示例代码可能如下: ```python from cljc_bloom import BloomFilter bloom = BloomFilter(capacity=...
3. **负载均衡**:为了更有效地分配读请求,可以使用负载均衡器,如Nginx或LVS,根据策略将请求路由到合适的从节点。 4. **一致性问题**:虽然读写分离能提升性能,但可能导致短暂的数据不一致。为了解决这个问题,...
RedisBloom是一个专门为Redis设计的高效、可扩展的布隆过滤器模块,它在数据存储和检索中扮演着重要角色,特别是在需要处理大量潜在重复数据的场景中。2.0.3版本是RedisBloom的一个稳定版本,适用于CentOS 7和9操作...
在IT行业中,"bloom"通常与数据结构和算法中的布隆过滤器(Bloom Filter)有关,这是一种空间效率极高的概率型数据结构,用于测试一个元素是否在一个集合中。"盛开"可能指的是该过滤器在处理大量数据时的高效性能,...
布谷鸟过滤器(Cuckoo Filter)是一种空间效率极高的数据结构,常用于近似成员关系查询,类似于布隆过滤器(Bloom Filter)。它由Edward O. Fanaee-T和Gang Wang在2014年提出,其设计灵感来源于布谷鸟巢寄生行为,故...
hyperfilter的工作原理可以简单理解为一种布隆过滤器(Bloom Filter)的变体。布隆过滤器是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。尽管可能会有误判,但在处理海量数据时,其...
此外,Redis还支持事务(Transaction)、发布/订阅(Publish/Subscribe)、布隆过滤器(Bloom Filter)等功能,可以根据实际需求选择使用。 总结起来,Java调用Redis主要涉及以下知识点: 1. 引入Jedis库 2. 创建...
布隆过滤器可以视为位图的一个扩展,在其基础上增加了多个哈希函数,提高了处理海量数据的能力。位图数据结构的一个经典应用场景是海量日志数据的处理,比如找出某天访问某网站次数最多的IP地址。 具体应用实例包括...
由于无法使用哈希表来直接比较URL,可以考虑使用布隆过滤器(Bloom Filter)来减少存储需求。布隆过滤器是一种空间效率极高的概率型数据结构,用于测试一个元素是否在一个集合中。 1. **算法步骤**: - 使用布隆...
它在处理大规模数据集时能够提供显著的性能优势,比传统的布隆过滤器(Bloom Filter)和Java内置的BitSet类更为高效。RoaringBitmap的设计目标是减少内存占用并加快位操作的速度。 RoaringBitmap的核心思想是将一个...
书中介绍了Get、Put、Scan等基本操作,以及如何优化查询性能,例如使用过滤器(Filter)和布隆过滤器(Bloom Filter)。此外,还涉及到了HBase的分布式特性,如Region划分和RegionServer的角色,以及数据的分裂和...
4. 动态索引技术实例:例如,跳跃式B+树(Skip List)和布隆过滤器(Bloom Filter)等数据结构常被用于动态索引。跳跃式B+树允许快速跳过多个节点,提高查询速度;布隆过滤器则可以快速判断一个元素是否可能存在,...
JS可以处理复杂的几何形状碰撞,比如使用布隆过滤器(Bloom Filter)或自定义算法来检测两个球是否接触。同时,游戏的计分系统、球的发射角度计算以及背景动画的实现,都是JS编程的实例。 3. **开心消消乐**:这款...
2. **缓存穿透**:防止查询不存在的数据导致Redis频繁被查询,可以使用布隆过滤器(Bloom Filter)预先过滤掉不可能存在的key,降低无效请求。 3. **缓存击穿**:当热点数据过期,同时大量请求涌向数据库,造成数据库...