Bloom Filter演算法詳解
什么是布隆過濾器
布隆過濾器（Bloom Filter）是 1970 年由布隆提出的，它實際上是一個很長的二進制向量和一系列隨機映射函式 (下面詳細說)，實際上你也可以把它簡單理解為一個不怎么精確的set結構，當你使用它的contains方法判斷某個物件是否存在時，它可能會誤判，但是布隆過濾器也不是特別不精確，只要引數設定的合理，它的精確度可以控制的相對足夠精確，只會有小小的誤判概率，
當布隆過濾器說某個值存在時，這個值可能不存在；但是當它說不存在時，那么這個值一定不存在，打個比方，當它說不認識你時，那就是真的不認識，但是當它說認識你時，可能是因為你長得像他認識的另一個朋友（臉長得有些相似），所以誤判認識你，
布隆過濾器的使用場景
在程式的世界中，布隆過濾器是程式員的一把利器，利用它可以快速地解決專案中一些比較棘手的問題，
如網頁URL的去重、垃圾郵件識別、大集合中重復元素的判斷和快取穿透等問題，
布隆過濾器的典型應用有：
- 大資料判斷是否存在
如果你的服務器記憶體足夠大的話，那么使用HashMap可能是一個不錯的解決方案，理論上時間復雜度可以達到O(1)級別，但是當資料量起來之后還是只能考慮布隆過濾器， - 解決快取穿透
我們通常會把一些經常訪問的資料放在Redis中當作快取，例如產品詳情，通常一個請求過來之后，我們會先查詢快取，而不用直接讀取資料庫，這是提升性能最簡單，也是最普遍的做法，但是如果一直請求一個不存在的快取，那就會有大量的請求被直接打到資料庫上，造成快取穿透，布隆過濾器也可以用來解決此類問題， - 爬蟲|郵箱等系統的過濾
對爬蟲網址進行過濾，已經存在布隆中的網址，不再爬取，
對于垃圾郵件進行過濾，對每一個發送郵件的地址進行判斷是否在布隆的黑名單內，如果在就判斷為垃圾郵件， - 業務場景判斷
判斷用戶是否閱讀過某視頻或文章，比如抖音或頭條，當然會導致一定的誤判，但不會讓用戶看到重復的內容， - Web攔截器
如果是相同的請求則進行攔截，防止被重復攻擊，
用戶第一次請求，將請求引數放入布隆過濾器中，當第二次請求時，先判斷請求引數是否被布隆過濾器命中，可以提高快取命中率，Squid 網頁代理快取服務器在 cache digests 中就使用了布隆過濾器，Google Chrome瀏覽器使用了布隆過濾器加速安全瀏覽服務
為什么使用布隆過濾器
下面舉一個實體說明我們為什么要學習BloomFilter
假設我們要寫一個爬蟲程式，由于網路間的鏈接錯綜復雜，蜘蛛在網路間爬行很可能會形成“環”，爬蟲就會進入一個無限怪圈，找不到出路，程式出現崩潰，
所以為了避免形成“環”，就需要知道蜘蛛已經訪問過那些URL，也就是如何判重，
給一個URL，怎樣知道蜘蛛是否已經訪問過呢？按照我們的常識，就會有如下幾種方案：
1. 將訪問過的URL保存到資料庫，資料庫管理系統可以為你去重，
2. 用Set將訪問過的URL保存起來，那只需接近O(1)的代價就可以查到一個URL是否被訪問過了，
3. URL經過MD5或SHA-1等單向哈希后再保存到Set或資料庫
4. Bit-Map方法，建立一個BitSet，將每個URL經過一個哈希函式映射到某一位，
方法1~3都是將訪問過的URL完整保存，方法4則只標記URL的一個映射位，
以上方法在資料量較小的情況下都能完美解決問題，但是當資料量變得非常龐大時問題就來了，
方法1的缺點：資料量變得非常龐大后關系型資料庫查詢的效率會變得很低，而且每來一個URL就啟動一次資料庫查詢是不是太小題大做了？
方法2的缺點：太消耗記憶體，隨著URL的增多，占用的記憶體會越來越多，就算只有1億個URL，每個URL只算50個字符，至少需要5GB記憶體，還不包括Set資料結構中的記憶體浪費，
方法3的缺點：由于字串經過MD5處理后的資訊摘要長度只有128Bit，SHA-1處理后也只有160Bit，因此方法3比方法2節省了好幾倍的記憶體，
方法4的缺點：消耗記憶體是相對較少的，但缺點是單一哈希函式發生沖突的概率太高，
若要降低沖突發生的概率到1%，有種辦法就是就要將BitSet的長度設定為URL個數的100倍，
假設一億條URL，就得把BitSet長度設為100億，過于稀疏也是很費記憶體的
實質上,上面的演算法都忽略了一個重要的隱含條件：允許小概率的出錯，不一定要100%準確！
也就是說少量URL實際上沒有沒被網路爬蟲訪問，而將它們錯判為已訪問的代價是很小的——大不了少抓幾個網頁唄，
Bloom Filter演算法原理
下面引入本篇的主角——Bloom Filter，其實上面方法4的思想已經很接近Bloom Filter了，
方法四的致命缺點是沖突概率高，為了降低沖突的概念，Bloom Filter使用了多個哈希函式，而不是一個，
為什么可以降低呢？我們知道Hash函式有一定幾率出現沖突，概率假設為 p1，我們知道p1是一個很小的幾率，但是在資料量大之后沖突就會變多，也就是上面第四種方法的問題，
BoomFilter使用 多個Hash函式 分別沖突概率為 p2 p3 p4 p5 … pn ，我們知道不同 Hash函式處理同一個字串彼此獨立，所以沖突概率通過乘法公式得到為: p1p2p3p4p5p6…pn，是相當相當小的了，
Bloom Filter演算法如下：
預操作
創建一個 m 位 BitSet（C++自帶，Python為bitarray），先將所有位初始化為0，然后選擇 k 個不同的哈希函式，第 i 個哈希函式對字串 str 哈希的結果記為h（i, str），且h（i，str）的范圍是 0 到 m-1 ，
Add操作
下面是每個字串處理的程序，首先是將字串str“記錄”到BitSet中的程序：
對于字串str，分別計算h（1，str），h（2，str）…… h（k，str），然后將BitSet的第h（1，str）、h（2，str）…… h（k，str）位設為1，
很簡單吧？這樣就將字串str映射到BitSet中的k個二進制位了，
Check操作
根據上圖，我們對每個字串采用同樣的演算法，
下面是檢查字串str是否被BitSet記錄過的程序：
- 對于字串str，分別計算h（1，str），h（2，str）…… h（k，str），然后檢查BitSet的第h（1，str）、h（2，str）…… h（k，str）位是否為1，若其中任何一位不為1則可以判定str一定沒有被記錄過，若全部位都是1，則“認為”字串str存在，
- 若一個字串對應的Bit不全為1，則可以肯定該字串一定沒有被Bloom Filter記錄過，（這是顯然的，因為字串被記錄過，其對應的二進制位肯定全部被設為1了）
- 但是若一個字串對應的Bit全為1，實際上是不能100%的肯定該字串被Bloom Filter記錄過的，（因為有可能該字串的所有位都剛好是被其他字串所對應）這種將該字串劃分錯的情況，稱為wrong position，
Delete操作
字串加入了就被不能洗掉了，因為洗掉會影響到其他字串，實在需要洗掉字串的可以使用Counting bloomfilter(CBF)，這是一種基本Bloom Filter的變體，CBF將基本Bloom Filter每一個Bit改為一個計數器，這樣就可以實作洗掉字串的功能了，
Bloom Filter跟單哈希函式Bit-Map不同之處在于：Bloom Filter使用了k個哈希函式，每個字串跟k個bit對應，從而降低了沖突的概率，
Bloom Filter 優化
考慮到BoomFilter上面的指標，總結一下有以下幾個
m ： BitSet 位數
n ： 插入字串個數
k ：hash函式個數
當然，哈希函式也是影響的重要因素
從表格來看 m/n越大越準，k越大越準，
但是具體怎么設計呢？
哈希函式選擇
- 哈希函式的選擇對性能的影回應該是很大的，一個好的哈希函式要能近似等概率的將字串映射到各個Bit，
- 選擇k個不同的哈希函式比較麻煩，一種簡單的方法是選擇一個哈希函式，然后送入k個不同的引數，
引數設計
相信大家對于 Bloom Filter 的作業原理都有了一個基本的了解，現在我們來看看在Bloom Filter 中涉及到的一些引數指標：
- 欲插入Bloom Filter中的元素數目: n
- Bloom Filter誤判率: P(true)
- BitArray陣列的大小: m
- Hash Function的數目: k
欲插入Bloom Filter中的元素數目 n 是我們在實際應用中可以提前獲取或預估的；Bloom Filter的誤判率 P(true) 則是我們提前設定的可以接受的容錯率，所以在設計Bloom Filter程序中，最關鍵的引數就是BitArray陣列的大小 m 和 Hash Function的數目 k，下面將給出這兩個關鍵引數的設定依據、方法
誤判率P(true)
Hash Function的數目k
前文已經看到Hash Function數目k的增加可以減小誤判率P(true)，但是隨著Hash Function數目k的繼續增加，反而會使誤判率P(true)上升，即誤判率是一個關于Hash Function數目k的凸函式，所以當k在極值點時，此時誤判率即為最小值
BitArray陣列的大小 m
如何解決布隆過濾器不支持洗掉的問題
（1）Counting Bloom Filter
Counting Bloom Filter將標準 Bloom Filter位陣列的每一位擴展為一個小的計數器（counter），在插入元素時給對應的k（k為哈希函式個數）個Counter的值分別加1，洗掉元素時給對應的k個Counter的值分別減1，Counting Bloom Filter通過多占用幾倍的存盤空間的代價，給Bloom Filter增加了洗掉操作，
（2）布谷鳥過濾器
對于這種方式有興趣的讀者可以閱讀這篇文章：https://juejin.cn/post/6924636027948630029#heading-1
Python 代碼簡單實作
主體
from bitarray import bitarray # 產生BitSet
import mmh3 # 產生Hash函式
class BloomFilter(set):
def __init__(self, size, hash_count):
super(BloomFilter, self).__init__()
self.bit_array = bitarray(size)
self.bit_array.setall(0)
self.size = size
self.hash_count = hash_count
def __len__(self):
return self.size
def __iter__(self):
return iter(self.bit_array)
def add(self, item):
for seed in range(self.hash_count):
index = mmh3.hash(item, seed) % self.size
self.bit_array[index] = 1
return self
def __contains__(self, item):
out = True
for seed in range(self.hash_count):
index = mmh3.hash(item, seed) % self.size
if self.bit_array[index] == 0:
out = False
return out
測驗
def main():
bloom = BloomFilter(10000, 20)
animals = ['dog', 'cat', 'giraffe', 'fly', 'mosquito', 'horse', 'eagle',
'bird', 'bison', 'boar', 'butterfly', 'ant', 'anaconda', 'bear',
'chicken', 'dolphin', 'donkey', 'crow', 'crocodile']
# First insertion of animals into the bloom filter
for animal in animals:
bloom.add(animal)
# Membership existence for already inserted animals
# There should not be any false negatives
for animal in animals:
if animal in bloom:
print('{} is in bloom filter as expected'.format(animal))
else:
print('Something is terribly went wrong for {}'.format(animal))
print('FALSE NEGATIVE!')
# Membership existence for not inserted animals
# There could be false positives
other_animals = ['badger', 'cow', 'pig', 'sheep', 'bee', 'wolf', 'fox',
'whale', 'shark', 'fish', 'turkey', 'duck', 'dove',
'deer', 'elephant', 'frog', 'falcon', 'goat', 'gorilla',
'hawk' ]
for other_animal in other_animals:
if other_animal in bloom:
print('{} is not in the bloom, but a false positive'.format(other_animal))
else:
print('{} is not in the bloom filter as expected'.format(other_animal))
if __name__ == '__main__':
main()
結果
dog is in bloom filter as expected
cat is in bloom filter as expected
giraffe is in bloom filter as expected
fly is in bloom filter as expected
mosquito is in bloom filter as expected
horse is in bloom filter as expected
eagle is in bloom filter as expected
bird is in bloom filter as expected
bison is in bloom filter as expected
boar is in bloom filter as expected
butterfly is in bloom filter as expected
ant is in bloom filter as expected
anaconda is in bloom filter as expected
bear is in bloom filter as expected
chicken is in bloom filter as expected
dolphin is in bloom filter as expected
donkey is in bloom filter as expected
crow is in bloom filter as expected
crocodile is in bloom filter as expected
badger is not in the bloom filter as expected
cow is not in the bloom filter as expected
pig is not in the bloom filter as expected
sheep is not in the bloom, but a false positive
bee is not in the bloom filter as expected
wolf is not in the bloom filter as expected
fox is not in the bloom filter as expected
whale is not in the bloom filter as expected
shark is not in the bloom, but a false positive
fish is not in the bloom, but a false positive
turkey is not in the bloom filter as expected
duck is not in the bloom filter as expected
dove is not in the bloom filter as expected
deer is not in the bloom filter as expected
elephant is not in the bloom, but a false positive
frog is not in the bloom filter as expected
falcon is not in the bloom filter as expected
goat is not in the bloom filter as expected
gorilla is not in the bloom filter as expected
hawk is not in the bloom filter as expected
從輸出結果可以發現，存在不少誤報樣本，但是并不存在假陰性，
不同于這段布隆過濾器的實作代碼，其它語言的多個實作版本并不提供哈希函式的引數，這是因為在實際應用中誤報比例這個指標比哈希函式更重要，用戶可以根據誤報比例的需求來調整哈希函式的個數，通常來說，size和error_rate是布隆過濾器的真正誤報比例，如果你在初始化階段減小了error_rate，它們會調整哈希函式的數量，
參考資料
https://cloud.tencent.com/developer/article/1731494
https://blog.csdn.net/a745233700/article/details/113751718
https://juejin.cn/post/6924636027948630029#heading-1
https://www.wmyskxz.com/2020/03/11/redis-5-yi-ji-shu-ju-guo-lu-he-bu-long-guo-lu-qi/#%E4%B8%80%E3%80%81%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8%E7%AE%80%E4%BB%8B
https://segmentfault.com/a/1190000024566947
https://github.com/jaybaird/python-bloomfilter
https://blog.csdn.net/weixin_42081389/article/details/103137671
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/323005.html
標籤：其他