布隆過濾器總結（二）原理和例子

布隆過濾器用于字元串去重複，比如網絡爬蟲抓取時URL去重、郵件提供商反垃圾黑名單Email位址去重。等等。用哈希表也可以用于元素去重，但是占用空間比較大，而且空間使用率隻有50%。

　　布隆過濾器隻占哈希表的1/8或1/4的空間複雜度，就能解決同樣的問題，但是有一定的誤判，而且不能删除已有元素。元素越多，誤報率越大，但是不會漏報。對于還需要删除的布隆過濾器，還有Counter Bloom Filter，這個是布隆過濾器的變體，可以删除元素。

布隆過濾器的原理

布隆過濾器需要的是一個位數組(和位圖類似)和K個映射函數(和Hash表類似)，在初始狀态時，對于長度為m的位數組array，它的所有位被置0。

　　

對于有n個元素的集合S={S1,S2...Sn},通過k個映射函數{f1,f2,......fk}，将集合S中的每個元素Sj(1<=j<=n)映射為K個值{g1,g2...gk}，然後再将位數組array中相對應的array[g1],array[g2]......array[gk]置為1：

　　

　　如果要查找某個元素item是否在S中，則通過映射函數{f1,f2,...fk}得到k個值{g1,g2...gk}，然後再判斷array[g1],array[g2]...array[gk]是否都為1，若全為1，則item在S中，否則item不在S中。這個就是布隆過濾器的實作原理。

前面說到過，布隆過濾器會造成一定的誤判，因為集合中的若幹個元素通過映射之後得到的數值恰巧包括g1,g2,...gk，在這種情況下可能會造成誤判，但是機率很小。

　　總結一下，感覺布隆過濾器的實作原理并不是太複雜，但是映射函數這個東西說的還是比較虛無。對于布隆過濾器的數學證明，數學公式之類的，我還是覺得我研究不了那麼深入了。畢竟現階段水準還不到有時間去研究這麼底層的，甚至于底層到和數學打交道的東西，就現階段來說，隻要知道有這樣一個東西可用，會用，我就很滿足了。

　　本來此處留白是準備自己寫個簡易版的布隆過濾器的，但是實在不懂，看來資料結構還遠遠有待補充。

　　另外附上一個第三方布隆過濾器控件，位址如下：http://bloomfilter.codeplex.com/

　　DEMO:

class Program
    {
        static void Main(string[] args)
        {
            //聲明一個布隆過濾器的初始容量包含10000個項目
            int capacity = 10000;
            float errorRate = 0.0001F;
            //初始化一個布隆過濾器
            Filter<string> urlSeen = new Filter<string>(capacity, errorRate, null);
            //添加資料進入布隆過濾器
            urlSeen.Add("www.baidu.com");
            urlSeen.Add("www.google.com");
            urlSeen.Add("www.qq.com");
            Console.WriteLine("請輸入網址：");
            string str = Console.ReadLine();
            //測試布隆過濾器是否記得這個url
            if (urlSeen.Contains(str))
            {
                Console.WriteLine("此url已經有了！");
            }
            else
            {
                Console.WriteLine("此url尚未被收錄！");
            }

            Console.ReadKey();
        }
    }