Bloom Filter:是一个比特数组,表示具有一定误报率的集合。主要优势在于其大小(比特位个数)为常数且在初始化时被设置,增加更多的元素到一个Bloom Filter 中不会增加它的大小,仅增加误报的概率。一般包含两个方法:add(),contains()。
误报率: r = (1-exp(-kn/m))k ,k = ln(2) * (m/n) , r = 0.6185*(m/n)
——k,散列函数个数
——m,比特个数
——n,被添加的元素个数
比如,存储一千万条URL的集合(n = 10 000 000),每个URL分配8个比特(m/n = 8),将需要10M的Bloom Filter(m = 80 000 000),误报率约为2%。若用Set存储,需要1G的空间。
Bloom Filter的内在表现为一个m个比特位的数组。有k个独立的散列函数,每个散列函数的输入为一个对象,而输出为介于0到m-1之间的一个整数。使用这个输出的整数作为位数组的索引。当添加一个元素到Bloom Filter时,使用散列函数来生成位数组的k个索引。
上图(画的图真难看,不知道什么工具比较好?)是使用三个散列函数的Bloom Filter中添加了几个对象(x,y,z)的过程。无论以前的状态是什么,比特位都被设置为1,在位数组中的1的个数只能增加。对象(如x,y,z)被确定地散列到数组中的位上,而这些位被设置为1,通过散列并检查那些位置上的比特值,可以查看一个对象是否在这个集合中。
当有一个对象到来时,若要检查它是否已经被加入到Bloom Fiter中,则使用与在添加对象时相同的k个散列函数来生成一个位数组的索引。现在检查是否比特数组中所有的k个比特均为1,是则返回true,否则返回false。若已被添加,则一定返回true,不过,即使此对象从未被添加到这个集合中,与所查询相对应的k个比特也可能都为1,这是因为其他对象的增加会设置这些位,从而导致误报。
用java实现的一个Bloom Filter(Hadoop in Action一书中的实现)。
package cn.zhf.test;
import java.io.BufferedReader;
import java.io.DataInput;
import java.io.DataOutput;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
public class BloomFilter<E> {
private BitSet bs;
private int bitArraySize = 100000000;
private int numHashFunc = 6;
public BloomFilter(){
bs = new BitSet(bitArraySize);
}
public void add(E obj){
int[] indexes = getHashIndexes(obj);
for(int index : indexes)
bs.set(index);
}
public boolean contains(E obj){
int[] indexes = getHashIndexes(obj);
for(int index : indexes)
if(bs.get(index) == false)
return false;
return true;
}
public void union(BloomFilter<E> other){
bs.or(other.bs);
}
/*粗略实现,采用MD5散列作为java随机数生成器的种子并取k个随机数作为索引*/
public int[] getHashIndexes(E obj){
int[] indexes = new int[numHashFunc];
long seed = 0;
byte[] digest;
try {
MessageDigest md = MessageDigest.getInstance("MD5");
md.update(obj.toString().getBytes());
digest = md.digest();
for(int i=0;i<6;i++)
seed = seed^(((long)(digest[i] & 0xFF)) << (8*i));
} catch (NoSuchAlgorithmException e) {
e.printStackTrace();
}
Random gen = new Random(seed);
for(int i=0;i<numHashFunc;i++)
indexes[i] = gen.nextInt(bitArraySize);
return indexes;
}
public void write(DataOutput out) throws IOException{
int byteArraySize = (int)(bitArraySize / 8);
byte[] byteArray = new byte[byteArraySize];
for(int i=0;i<byteArraySize;i++){
byte nextElement = 0;
for(int j=0;j<8;j++){
if(bs.get(8*i+j))
nextElement |= 1<<j;
}
byteArray[i] = nextElement;
}
out.write(byteArray);
}
public void readFileds(DataInput in) throws IOException{
int byteArraySize = (int)(bitArraySize / 8);
byte[] byteArray = new byte[byteArraySize];
in.readFully(byteArray);
for(int i=0;i<byteArraySize;i++){
byte nextByte = byteArray[i];
for(int j=0;j<8;j++){
if(((int)nextByte & (1<<j)) != 0)
bs.set(8*i+j);
}
}
}
public Map<Integer,String> readFile(String filePath){
BufferedReader br;
Map<Integer,String> map = new HashMap<Integer,String>();
try {
br = new BufferedReader(new InputStreamReader(
new FileInputStream(filePath)));
int i = 0;
for (String line = br.readLine(); line != null; line = br.readLine()) {
map.put(i++, line);
}
br.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
return map;
}
public static void main(String[] args) {
BloomFilter<String> bf = new BloomFilter<String>();
Map<Integer,String> map = bf.readFile("C:\\Users\\zhf\\Desktop\\test.txt");
for(Map.Entry<Integer, String> m : map.entrySet())
bf.add(m.getValue());
boolean flag = bf.contains("15");
System.out.println(flag);
}
}
分享到:
相关推荐
介绍Bloom Filter(布隆过滤器)原理、实现及具体应用,包含9个不同PPT及PDF文档资料,对Bloom Filter感兴趣、想学习的同学可以下载查看下
Bloom Filter的原理与C++实现,并利用Bloom Filter实现简单的词典,进行字词查询
redis-bloomFilter是基于redis的bitset实现的bloomfilter.具体原理和实现思路可以参考 使用 redis-bloomFilter发布在JitPack,可以选择下载源码编译,或者通过jitpack源添加依赖。 使用Maven添加依赖 添加jitpack源 ...
本程序主要是BloomFilter算法的简化实现 因为C#非安全代码无法直接分配内存块,使用了int型数组代替,暂时为了简单没有使用位运算,比位运算消耗内存多16倍。 算法原理: 其首先申请一块大内存,并把内存中...
如何在庞大的数据中高效的检索自己需要的东西?本篇内容介绍了Python做出一个大数据搜索引擎的原理和方法,以及中间进行数据分析的...class Bloomfilter(object): A Bloom filter is a probabilistic data-structure
本质上布隆过滤器( BloomFilter )是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。 相比于传统的 Set、...
2.2 原理分析Bloom Filter使用一串位数组存储数据,并只支持对数据进行查询,无法读取 4.1 hash函数设计由于用于实现bloom filter的
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,...
搜索是大数据领域里常见的需求。Splunk和ELK分别是该领域在非开源和开源领域里的领导者。本文利用很少的Python代码实现了一个基本的数据搜索功能...class Bloomfilter(object): """ A Bloom filter is a probabilisti
针对双结构网络的特点及其URL去重面临的挑战,根据Bloom Filter的工作原理,提出一种基于可扩展的动态可分裂Bloom Filter的URL去重机制,并在原型系统中进行实现和部署。实验结果表明,该机制能够有效适用于大规模、高...
文章目录简介BloomFilterBloomFilter的简单优化改进BloomFilterspark 的布隆过滤器scala实现BF、CBF 简介 ...BloomFilter 使用范围:可以用来实现数据字典,进行数据的判重,或者集合求交 原理:位数
适用范围:可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下基本原理及要点:使用bit数组来表示某些元素是否存在,比如8位电话号码扩展:bloom filter可以看做是对bit-map的扩展问题实例:1)...
1.Bloom filter 适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集 基本原理及要点: 对于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现所有hash函数...
2.2.2. 布隆过滤器(BloomFilter) 基于布隆算法,对欲加入队列的原始统一资源定位符进行过滤,以防止已被抓 取过的URL再次入队,降低冗余开销同时避免无限循环。 2.2.3. 原始统一资源定位符(RawUrl) 提供原始形态的...
技术点56 通过MapReduce 对Bloom filter 进行semi-join 7.3 本章小结 8 结合R 和Hadoop 进行数据统计 8.1 比较R 和MapReduce 集成的几种方法 8.2 R 基础知识 8.3 R 和Streaming 8.3.1 Streaming 和...
of-friends(FoF) 技术点53 计算FoF 7.1.4 PageRank技术点54 通过Web 图计算PageRank7.2 Bloom filter 技术点55 在MapReduce 中并行创建Bloom filter 技术点56 通过MapReduce 对Bloom filter 进行semi-...
JobWorker上都存在消息队列节点,同时会有一个去重模块(bloom filter实现)。Cola还不够稳定,目前会处于持续改进的状态。且Cola还没有在较大规模的集群上测试,但是接下来我会把Cola应用到新项目中,并逐步完善。...