`
grzrt
  • 浏览: 188723 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

bloom filter 的Java 版

 
阅读更多

 属于转贴:http://www.cnblogs.com/hitwtx/archive/2011/08/24/2152180.html

一、 Bloom-Filter算法简介。
Bloom-Filter,即布隆过滤器,1970年由Bloom中提出。它可以用于检索一个元素是否在一个集合中,其优点是空间效率和查询时间都远远超过其他算法,其不足在于Bloom- Filter存在着误判。

二、 Bloom-Filter的基本思想。
Bloom-Filter算法的核心思想就是利用多个不同的Hash函数来解决“冲突”。 计算某元素x是否在一个集合中,首先能想到的方法就是将所有的已知元素保存起来构成一个集合R,然后用元素x跟这些R中的元素一一比较来判断是否存在于集合R中;我们可以采用链表等数据结构来实现。但是,随着集合R中元素的增加,其占用的内存将越来越大。试想,如果有几千万个不同网页需要下载,所需的内存将足以占用掉整个进程的内存地址空间。即使用MD5,UUID这些方法将URL转成固定的短小的字符串,内存占用也是相当巨大的.

日常生活中,包括在设计计算机软件时,我们经常要判断一个元素是否在一个集合中。比如在字处理软件中,需要检查一个英语单词是否拼写正确(也就是要判断它是否在已知的字典中);在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上;在网络爬虫里,一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中,遇到一个新元素时,将它和集合中的元素直接比较即可。

一般来讲,计算机中的集合是用哈希表(hash table)来存储的。它的好处是快速准确,缺点是费存储空间。当集合比较小时,这个问题不显著,但是当集合巨大时,哈希表存储效率低的问题就显现出来了。

三、 Bloom-Filter的应用。
Bloom-Filter一般用于在大数据量的集合中判定某元素是否存在。例如邮件服务器中的垃圾邮件过滤器。在搜索引擎领域,Bloom-Filter最常用于网络蜘蛛(Spider)的URL过滤,网络蜘蛛通常有一个 URL列表,保存着将要下载和已经下载的网页的URL,网络蜘蛛下载了一个网页,从网页中提取到新的URL后,需要判断该URL是否已经存在于列表中。此时,Bloom-Filter算法是最好的选择。
比如说,一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件(email)提供商,总是需要过滤来自发送垃圾邮件的人(spamer)的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址,全世界少说也有几十亿个发垃圾邮件的地址,将他们都存起来则需要大量的网络服务器。

布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。我们通过上面的例子来说明起工作原理。

假定我们存储一亿个电子邮件地址,我们先建立一个十六亿二进制(比特),即两亿字节的向量,然后将这十六亿个二进制位全部设置为零。对于每一个电子邮件地址 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 对应的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址,我们都能准确地发现。
布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。但是,它有一条不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中,因为有可能某个好的邮件地址正巧对应八个都被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率。在上面的例子中,误识概率在万分之一以下。
布隆过滤器的好处在于快速,省空间。但是有一定的误识别率。常见的补救办法是在建立一个小的白名单,存储那些可能别误判的邮件地址。

1. 使用Java 自带的

private BitSet bits = new BitSet(defaultSize);

 

 

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 bloomFilter(String key){
        this.key = key;
    }
    
    private int[] lrandom(){
        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(){
        if(exist()){
            System.out.println("已经包含("+key+")");
            return;
        }
        int keyCode[] = lrandom();
        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(){
        int keyCode[] = lrandom();
        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 static void main(String[] args) {
        // TODO Auto-generated method stub
        bloomFilter f = new bloomFilter("http://www.agrilink.cn/");
    
        System.out.println(f.defaultSize);
        f.add();
        System.out.println(f.exist());
        f.set0();
        System.out.println(f.exist());
    }

}

 

 

 2. 还有一个java 版的 ,也是 使用 bitset

 

import java.util.BitSet;
public class  SimpleBloomFilter {
     private static final  int  DEFAULT_SIZE  =2 << 24 ;
     private static final  int [] seeds =new  int []{5,7, 11 , 13 , 31 , 37 , 61};
     private  BitSet bits= new  BitSet(DEFAULT_SIZE);
     private  SimpleHash[]  func=new  SimpleHash[seeds.length];
     
   
     
     public  SimpleBloomFilter() {
         for( int  i= 0 ; i< seeds.length; i ++ ) {
            func[i]=new  SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }
     public void  add(String value) {
         for(SimpleHash f : func) {
            bits.set(f.hash(value),  true );
        }
    }
     public boolean  contains(String value) {
         if(value ==null ) {
             return false ;
        }
         boolean  ret  = true ;
         for(SimpleHash f : func) {
            ret=ret&& bits.get(f.hash(value));
        }
         return  ret;
    }
     
     //内部类,simpleHash
     public static class SimpleHash {
         private int  cap;
         private int  seed;
         public  SimpleHash( int cap, int seed) {
             this.cap= cap;
             this.seed =seed;
        }
         public int hash(String value) {
             int  result=0 ;
             int  len= value.length();
             for  (int i= 0 ; i< len; i ++ ) {
                result =seed* result + value.charAt(i);
            }
             return (cap - 1 ) & result;
        }
    }
     
     
     
     
     
     
     
     public static void  main(String[] args) {
         String value  = "stone2083@yahoo.cn" ;
         SimpleBloomFilter filter=new  SimpleBloomFilter();
         System.out.println(filter.contains(value));
         filter.add(value);
         System.out.println(filter.contains(value));
     }
     
     
     
     
}
 

 

 

分享到:
评论

相关推荐

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

    在Java中,我们可以使用Guava库中的`com.google.common.hash.BloomFilter`类来实现Bloom Filter。Guava提供了几个预定义的哈希函数组合,可以自动调整位数组的大小和哈希函数的数量以达到目标误判率。 ```java ...

    java-bloomfilter

    Java 中实现布隆过滤器,通常可以使用开源库Guava提供的`com.google.common.hash.BloomFilter`类。Guava的布隆过滤器提供了灵活的参数配置,包括期望元素数量(expectedInsertions)和错误率(fpp,False Positive ...

    Java-BloomFilter, 在Java中,一个独立的Bloom过滤器.zip

    Java-BloomFilter, 在Java中,一个独立的Bloom过滤器 java-bloomfilterJava bloomfilter是一个独立于Java的Bloom过滤器实现。 它旨在在不需要额外库开销的情况下包含在现有项目中。 第一个版本是由 Ian的博客条目...

    如何使用bloomfilter构建大型Java缓存系统Ja

    在Java中,可以使用开源库如Guava提供的BloomFilter类来实现。首先,需要创建一个BloomFilter实例,指定预期的元素数量和错误率。错误率通常是一个较小的浮点数,如0.01,表示1%的误判率。Guava的BloomFilter构造器...

    Go-Go中的CuckooFilter实现比BloomFilter更好

    在Go编程语言中,Bloom Filter和Cuckoo Filter是两种流行的数据结构,用于空间效率高的近似存在检查。本篇文章将深入探讨Cuckoo Filter如何在某些情况下优于Bloom Filter,以及Go语言中实现Cuckoo Filter的细节。 ...

    Bloom Filter of 2.5 Million common passwords

    This is the bloom filter of 2.5 Million ... BloomFilter bf=new BloomFilter(); BitSet bitSet=bf.readBit(fileName); bf.setBits(bitSet); System.out.println(bf.exist("password")); } it will says true.

    Bloom-Filter:Java中Bloom Filter数据结构的实现

    在Java中实现Bloom Filter,我们通常会用到位数组(Bit Array)和几个不同的哈希函数。位数组是一组二进制位,可以理解为一个很长的数字,其中每个位代表一个可能的元素。哈希函数则将输入映射到这个位数组的特定...

    java-bloomfilter:Java SE 8 的 BloomFilter 计数

    布隆过滤器实现 为 Java SE 8 计算 BloomFilter。用法 // capacity: 1000, error_rate: 0.001(= 0.1%)final BloomFilter&lt;String&gt; bf1 = new BloomFilter&lt;&gt;(1000, 0.01);bf.add("test");bf.contains("test"); // =...

    javabitset源码-redis-bloomfilter:基于Redis的BloomfilterforJava

    redis-bloomFilter是基于redis的bitset实现的bloomfilter.具体原理和实现思路可以参考 使用 redis-bloomFilter发布在JitPack,可以选择下载源码编译,或者通过jitpack源添加依赖。 使用Maven添加依赖 添加jitpack源 ...

    bloom-filter:Java中Bloom过滤器的实现

    在Java中实现布隆过滤器,可以使用Guava库提供的`com.google.common.hash.BloomFilter`类。Guava的BloomFilter提供了创建、添加元素和查询元素的方法,并且支持动态调整过滤器的大小以控制误判率。以下是一个简单的...

    java-bloomfilter:具有JSON(反)序列化和(zlib)压缩的Java Bloomfilter实现

    java-bloomfilter 具有JSON(反)序列化和(zlib)压缩的Java Bloomfilter实现 您可以在此处找到兼容的PYTHON实现: : 例子: BloomFilter bf1 = new BloomFilter(1000000, 0.001); bf1.add("Alabama"); bf1.add...

    bloom-filter:Java语言的Bloom Bloom筛选器

    var BloomFilter = require('bloom-filter'); var bf = new BloomFilter({ elements: [1, 2, 3], p: 0.001 // default value of false positive rate }); bf.has(1) // true 原料药 建设者 BloomFilter(opts) ...

    shingling、simhash、bloom filter

    在IT领域,尤其是在大数据分析和信息检索中,`shingling`、`simhash` 和 `bloom filter` 是三个非常重要的概念。这些技术主要用于处理大量数据,进行相似性检测和去重,从而提高效率和准确性。下面将详细介绍这三个...

    自己写的Java抓图程序(用了BloomFilter算法)

    自己写的Java抓图程序 原理见 http://blog.csdn.net/binyao02123202/archive/2010/07/12/5728840.aspx 用了序列化 线程 和BloomFilter算法

    布隆过滤器BloomFilters的一个简单Java库

    布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。在Java开发中,特别是在处理大数据、内存限制或需要快速查询是否存在某个元素的场景下,布隆过滤器是一个...

    介绍Bloom Filter(布隆过滤器)原理、实现及具体应用

    例如,Python中的`pybloom`库,Java中的`Guava`库都提供了Bloom Filter的实现。 通过学习提供的9个PPT和PDF文档,你可以深入了解Bloom Filter的工作机制、性能分析以及在不同场景下的应用实例,从而更好地理解和...

    布隆过滤器-BloomFilter

    例如,`BloomFilter.java`和`MyBloomFilter.java`可能是两个不同的实现版本。自定义实现通常包括以下几个关键部分: 1. **位数组(Bit Array)**:存储元素的位向量,所有操作都在这个数组上进行,大小通常是根据...

    BloomFilter .NET:BloomFilter .NET-Bloom Filter的.NET实现-开源

    Magnus Skjegstad从Java实现中移植的内容:https://github.com/MagnusS/Java-BloomFilter Bloom过滤器是一种数据结构,旨在快速且高效地告知您元素是否存在于集合中。 它是一个概率数据结构:虽然可以肯定地告诉您...

    Orestes-Bloomfilter:Java中的各种Bloom筛选器库,带有可选的Redis支持,计数和许多哈希选项

    布隆过滤器库| | | 版本1完全重写了几乎所有功能和许多新功能。 这是我们实施的一组... Orestes Bloom过滤器库中有4种类型的Bloom过滤器: 常规Bloom过滤器,常规内存Java Bloom过滤器( MemoryBloomFilter ) Counti

Global site tag (gtag.js) - Google Analytics