no-image

布隆過濾器(Bloom Filter)

                                    

布隆過濾器(Bloom Filter)

一、什麼是布隆過濾器

以前有過這種需求,抽象來說就是:兩個集合S1和S2,相交,求如下ABC三部分分別有哪些元素?

輸入圖片說明

做法是:構造兩個map,遍歷。資料量小還可以,資料量大的話,就不可以了。直到看到“布隆過濾器”這個概念

1.1 定義

Bloom Filter是1970年由Bloom提出的。它實際上是一個很長的二進位制向量和一系列隨機對映函式(Hash函式)。布隆過濾器可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的演算法,缺點是有一定的誤識別率和刪除困難。Bloom Filter廣泛的應用於各種需要查詢的場合中,如Orocle的資料庫,Google的BitTable也用了此技術。

1.2 特點

  1. 不存在漏報(False Negative),即某個元素在某個集合中,肯定能報出來。
  2. 可能存在誤報(False Positive),即某個元素不在某個集合中,可能也被爆出來。
  3. 確定某個元素是否在某個集合中的代價和總的元素數目無關。

二、實現

2.1 java實現

import java.util.BitSet;

public class BloomFilter {

	// 位陣列bits,長度為m,初值置為0
	// hash函式f,長度為k
	// 集合S,長度為n

  	// 布隆過濾器的位元長度 2^25
	private static final int DEFAULT_SIZE = 2 << 24;
    // 這裡要選取質數,能很好的降低錯誤率
	private static final int[] seeds = { 3, 5, 7, 11, 13, 31, 37, 61 };
	
  	// 位陣列
	private static BitSet bits = new BitSet(DEFAULT_SIZE); 
    // hash函式
	private static SimpleHash[] func = new SimpleHash[seeds.length]; 

	public static void addValue(String value) {
		// 將字串value雜湊為8個或多個整數,然後在這些整數的bit上變為1
      	for (SimpleHash f : func) {
			bits.set(f.hash(value), true);
        }
	}

	public static void add(String value) {
		if (value != null) {
			addValue(value);
		}
	}

	public static boolean contains(String value) {
		if (value == null) {
			return false;
		}
		boolean ret = true;
		for (SimpleHash f : func) { 
          	 // 這裡其實沒必要全部跑完,只要一次ret==false那麼就不包含這個字串
			ret = ret && bits.get(f.hash(value));
			if (!ret) {
				return ret;
			}
		}
		return ret;
	}

	public static void main(String[] args) {
		System.out.println(DEFAULT_SIZE);
		String value = "www..net";
		// 初始化hash函式
		for (int i = 0; i < seeds.length; i  ) {
			func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
		}
		add(value);
		System.out.println(contains(value));
	}
}

class SimpleHash {// 這玩意相當於C  中的結構體
	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;
	}
}

2.2 c 實現

/*http://www.cnblogs.com/dolphin0520/archive/2012/11/10/2755089.html*/
/*布隆過濾器簡易版本 2012.11.10*/

#include<iostream>
#include<bitset>
#include<string>
#define MAX 2<<24
using namespace std;

bitset<MAX> bloomSet;           //簡化了由n和p生成m的過程 

int seeds[7]={3, 7, 11, 13, 31, 37, 61};     //使用7個hash函式 



int getHashValue(string str,int n)           //計算Hash值 
{
    int result=0;
    int i;
    for(i=0;i<str.size();i  )
    {
        result=seeds[n]*result (int)str[i];
        if(result > 2<<24)
            result%=2<<24;
    }
    return result;
}


bool isInBloomSet(string str)                //判斷是否在布隆過濾器中 
{
    int i;
    for(i=0;i<7;i  )
    {
        int hash=getHashValue(str,i);
        if(bloomSet[hash]==0)
            return false;
    }
    return true;
}

void addToBloomSet(string str)               //新增元素到布隆過濾器 
{
    int i;
    for(i=0;i<7;i  )
    {
        int hash=getHashValue(str,i);
        bloomSet.set(hash,1);
    }
}


void initBloomSet()                         //初始化布隆過濾器 
{
    addToBloomSet("http://www.baidu.com");
    addToBloomSet("http://www.cnblogs.com");
    addToBloomSet("http://www.google.com");
}


int main(int argc, char *argv[])
{
    
    int n;
    initBloomSet();
    while(scanf("%d",&n)==1)
    {
        string str;
        while(n--)
        {
            cin>>str;
            if(isInBloomSet(str))
                cout<<"yes"<<endl;
            else
                cout<<"no"<<endl;
        }
        
    }
    return 0;
}

三、應用場景

如何生成數千萬不重複的固定長度的字串?

一個實現

四、參考

網上大部分文章都是從下面這幾篇文章中摘抄的。

  1. 數學之美系列二十一 - 布隆過濾器(Bloom Filter)
  2. 布隆過濾器-維基百科
  3. 布隆過濾器
  4. 布隆過濾器(Bloom Filter)的Java實現方法
  5. Hash和Bloom Filter

關聯文章