看見了海量數據去重，找到停留時間最長的ip等問題，有博友提到了Bloom Filter，我就查了查，不過首先想到的是大叔，下面就先看看大叔的風采。
一、布隆過濾器概念引入
（Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出的。它實際上是由一個很長的二進制向量和一系列隨機映射函數組成，布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率（假正例False positives，即Bloom Filter報告某一元素存在于某集合中，但是實際上該元素并不在集合中）和刪除困難，但是沒有識別錯誤的情形（即假反例False negatives，如果某個元素確實在該集合中，那么Bloom Filter 是不會報告該元素不存在于集合中的，所以不會漏報）。
下面從簡單的排序談到BitMap算法，再談到數據去重問題，談到大數據量處理利器：布隆過濾器。
對無重復的數據進行排序給定數據（2，4，1，12，9，7，6）如何對它排序？
方法1：基本的排序方法包括冒泡，快排等。
方法2：使用BitMap算法
方法1就不介紹了，方法2中所謂的BitMap是一個位數組，跟平時使用的數組的唯一差別在于操作的是位。首先是開辟2個字節大小的位數組，長度為12（該長度由上述數據中最大的數字12決定的),然后，讀取數據，2存放在位數組中下標為1的地方，值從0改為1，4存放在下標為3的地方，值從0改為1….最后，讀取該位數組，得到排好序的數據是：（1，2，4，6，7，9，12）。
比較方法1和方法2的差別：方法2中，排序需要的時間復雜度和空間復雜度很依賴與數據中最大的數字比如12，因此空間上講需要開2個字節大小的內存，時間上需要遍歷完整個數組。當數據類似（1，1000，10萬）只有3個數據的時候，顯然用方法2，時間復雜度和空間復雜度相當大，但是當數據比較密集時該方法就會顯示出來優勢。
對有重復的數據進行判重數據（2，4，1，12，2，9，7，6，1，4）如何找出重復出現的數字？
首先是開辟2個字節大小的位數組，長度為12（該長度由上述數據中最大的數字12決定的,當讀取完12后，當讀取2的時候，發現數組中的值是1，則判斷出2是重復出現的。
二、布隆過濾器原理
布隆過濾器需要的是一個位數組（這個和位圖有點類似）和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中。這個就是布隆過濾器的實現原理。
當然有讀者可能會問：即使array[g1],array[g2]……array[gk]都為1，能代表item一定在集合S中嗎？不一定，因為有這個可能：就是集合中的若干個元素通過映射之后得到的數值恰巧包括g1,g2,…..gk，那么這種情況下可能會造成誤判，但是這個概率很小，一般在萬分之一以下。
很顯然，布隆過濾器的誤判率和這k個映射函數的設計有關，到目前為止，有很多人設計出了很多高效實用的hash函數。尤其要注意的是，布隆過濾器是不允許刪除元素的(實際就是因為多個str可能都應設在同一點，而判斷str存在的話是所有映射點都存在，所以不能刪除)，因為若刪除一個元素，可能會發生漏判的情況。不過有一種布隆過濾器的變體Counter Bloom Filter，可以支持刪除元素，感興趣的讀者可以查閱相關文獻資料。
三、布隆過濾器False positives 概率推導
假設 Hash 函數以等概率條件選擇并設置 Bit Array 中的某一位，m 是該位數組的大小，k 是 Hash 函數的個數，那么位數組中某一特定的位在進行元素插入時的 Hash 操作中沒有被置位為1的概率是：
；那么在所有 k 次 Hash 操作后該位都沒有被置 “1” 的概率是：
；如果我們插入了 n 個元素，那么某一位仍然為 “0” 的概率是：
因而該位為 “1”的概率是：
；現在檢測某一元素是否在該集合中。標明某個元素是否在集合中所需的 k 個位置都按照如上的方法設置為 “1”，但是該方法可能會使算法錯誤的認為某一原本不在集合中的元素卻被檢測為在該集合中（False Positives），該概率由以下公式確定：
。
其實上述結果是在假定由每個 Hash 計算出需要設置的位（bit） 的位置是相互獨立為前提計算出來的，不難看出，隨著 m （位數組大小）的增加，假正例（False Positives）的概率會下降，同時隨著插入元素個數 n 的增加，False Positives的概率又會上升，對于給定的m，n，如何選擇Hash函數個數 k 由以下公式確定：
；此時False Positives的概率為：
；而對于給定的False Positives概率 p，如何選擇最優的位數組大小 m 呢，
；該式表明，位數組的大小最好與插入元素的個數成線性關系，對于給定的 m，n，k，假正例概率最大為：
。
四、布隆過濾器應用
布隆過濾器在很多場合能發揮很好的效果，比如：網頁URL的去重，垃圾郵件的判別，集合重復元素的判別，查詢加速（比如基于key-value的存儲系統）等，下面舉幾個例子：
有兩個URL集合A,B，每個集合中大約有1億個URL，每個URL占64字節，有1G的內存，如何找出兩個集合中重復的URL。很顯然，直接利用Hash表會超出內存限制的范圍。這里給出兩種思路：
第一種：如果不允許一定的錯誤率的話，只有用分治的思想去解決，將A,B兩個集合中的URL分別存到若干個文件中{f1,f2…fk}和{g1,g2….gk}中，然后取f1和g1的內容讀入內存，將f1的內容存儲到hash_map當中，然后再取g1中的url，若有相同的url，則寫入到文件中，然后直到g1的內容讀取完畢，再取g2…gk。然后再取f2的內容讀入內存。。。依次類推，知道找出所有的重復url。
第二種：如果允許一定錯誤率的話，則可以用布隆過濾器的思想。
在進行網頁爬蟲時，其中有一個很重要的過程是重復URL的判別，如果將所有的url存入到數據庫中，當數據庫中URL的數量很多時，在判重時會造成效率低下，此時常見的一種做法就是利用布隆過濾器，還有一種方法是利用berkeley db來存儲url，Berkeley db是一種基于key-value存儲的非關系數據庫引擎，能夠大大提高url判重的效率。
布隆過濾器主要運用在過濾惡意網址用的，將所有的惡意網址建立在一個布隆過濾器上，然后對用戶的訪問的網址進行檢測，如果在惡意網址中那么就通知用戶。這樣的話，我們還可以對一些常出現判斷錯誤的網址設定一個白名單，然后對出現判斷存在的網址再和白名單中的網址進行匹配，如果在白名單中，那么就放行。當然這個白名單不能太大，也不會太大，布隆過濾器錯誤的概率是很小的。
五、布隆過濾器簡單java實現
?
作者：張朋飛 出處：http://www.cnblogs.com/hxsyl/ 本文版權歸作者張朋飛所有，歡迎轉載和商用，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利. 分享到： 更多 分類: DataMining 好文要頂 關注我 收藏該文 
火星十一郎 關注 - 17 粉絲 - 495 +加關注 2 0 關注 | 頂部 | 評論 ? 上一篇：百度網頁搜索部? 下一篇：關于最大流的EdmondsKarp算法詳解 </div> <div class="postDesc">posted @ <span id="post-date">2014-12-21 11:06</span> <a >火星十一郎</a> 閱讀(<span id="post_view_count">2510</span>) 評論(<span id="post_comment_count">2</span>) <a href="https://i.cnblogs.com/EditPosts.aspx?postid=4176280" rel="nofollow">編輯</a> <a href="#" onclick="AddToWz(4176280);return false;">收藏</a></div></div><script type="text/Javascript">var allowComments=true,cb_blogId=111848,cb_entryId=4176280,cb_blogApp=currentBlogApp,cb_blogUserGuid='3372c2b7-076f-e111-aa3f-842b2b196315',cb_entryCreatedDate='2014/12/21 11:06:00';loadViewCount(cb_entryId);</script> 評論列表 #1樓 2014-12-21 11:33 kK_wen  |
|
|
|
新聞熱點
疑難解答
