海量數據處理的算法海量數據處理 _數據處理

海量數據處理（海量數據處理的算法）
主要講述一下Bloom Filter算法
Bloom Filter（BF）是一種空間效率很高的隨機數據結構，它利用位數組很簡潔地表示一個集合，并能判斷一個元素是否屬于這個集合。它是一個判斷元素是否存在集合的快速的概率算法。Bloom Filter有可能會出現錯誤判斷，但不會漏掉判斷。也就是BloomFilter判斷元素不再集合，那肯定不在。如果判斷元素存在集合中，有一定的概率判斷錯誤。因此， BloomFilter不適合那些“零錯誤”的應用場合。
而在能容忍低錯誤率的應用場合下， BloomFilter比其他常見的算法（如hash ，折半查找）極大節省了空間。
BloomFilter的詳細介紹：海量數據處理之Bloom Filter詳解
【適用范圍】
【海量數據處理的算法海量數據處理】可以用來實現數據字典，進行數據的判重，或者集合求交集
【基本原理及要點】
原理要點：一是位數組，而是k個獨立hash函數。
1）位數組：
假設BloomFilter使用一個m比特的數組來保存信息，初始狀態時， Bloom Filter是一個包含m位的位數組，每一位都置為0 ，即BF整個數組的元素都設置為0 。

文章插圖

2）k個獨立hash函數
為了表達S={x1, x2,…,xn}這樣一個n個元素的集合， BloomFilter使用k個相互獨立的哈希函數（Hash Function），它們分別將集合中的每個元素映射到{1,…,m}的范圍中。
當我們往Bloom Filter中增加任意一個元素x時候，我們使用k個哈希函數得到k個哈希值，然后將數組中對應的比特位設置為1 。即第i個哈希函數映射的位置hashi(x)就會被置為1（1≤i≤k）。注意，如果一個位置多次被置為1 ，那么只有第一次會起作用，后面幾次將沒有任何效果。在下圖中， k=3 ，且有兩個哈希函數選中同一個位置（從左邊數第五位，即第二個“1“處）。

文章插圖

3）判斷元素是否存在集合
在判斷y是否屬于這個集合時，我們只需要對y使用k個哈希函數得到k個哈希值，如果所有hashi(y)的位置都是1（1≤i≤k），即k個位置都被設置為1了，那么我們就認為y是集合中的元素，否則就認為y不是集合中的元素。下圖中y1就不是集合中的元素（因為y1有一處指向了“0”位）。y2或者屬于這個集合，或者剛好是一個false positive 。

文章插圖

顯然這個判斷并不保證查找的結果是100%正確的。
BloomFilter的缺點：
1）Bloom Filter無法從Bloom Filter集合中刪除一個元素。因為該元素對應的位會牽動到其他的元素。所以一個簡單的改進就是 counting Bloom filter ，用一個counter數組代替位數組，就可以支持刪除了。此外， BloomFilter的hash函數選擇會影響算法的效果。
2）還有一個比較重要的問題，如何根據輸入元素個數n ，確定位數組m的大小及hash函數個數，即hash函數選擇會影響算法的效果。當hash函數個數k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大于E的情況下， m至少要等于n*lg(1/E) 才能表示任意n個元素的集合。但m還應該更大些，因為還要保證bit數組里至少一半為0 ，則m應該>=nlg(1/E)*lge ，大概就是nlg(1/E)1.44倍(lg表示以2為底的對數) 。
舉個例子我們假設錯誤率為0.01 ，則此時m應大概是n的13倍。這樣k大概是8個。
注意：
這里m與n的單位不同， m是bit為單位，而n則是以元素個數為單位(準確的說是不同元素的個數) 。通常單個元素的長度都是有很多bit的。所以使用bloom filter內存上通常都是節省的。
一般BF可以與一些key-value的數據庫一起使用，來加快查詢。由于BF所用的空間非常小，所有BF可以常駐內存。這樣子的話，對于大部分不存在的元素，我們只需要訪問內存中的BF就可以判斷出來了，只有一小部分，我們需要訪問在硬盤上的key-value數據庫。從而大大地提高了效率。
【擴展】
Bloom filter將集合中的元素映射到位數組中，用k（k為哈希函數個數）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）將位數組中的每一位擴展為一個counter ，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現次數關聯。SBF采用counter中的最小值來近似表示元素的出現頻率。
【問題實例】
給你A,B兩個文件，各存放50億條URL ，每條URL占用64字節，內存限制是4G ，讓你找出A,B文件共同的URL 。如果是三個乃至n個文件呢？
根據這個問題我們來計算下內存的占用， 4G=2^32大概是40億*8大概是340億bit ， n=50億，如果按出錯率0.01算需要的大概是650億個bit 。現在可用的是340億，相差并不多，這樣可能會使出錯率上升些。另外如果這些urlip是一一對應的，就可以轉換成ip ，則大大簡單了。
關于實現部分的代碼后續會分享，近期會繼續研究這部分算法，敬請期待，我的小伙伴們！！！