03.07 大數據算法——布隆過濾器技术頭條網

原理

在我之前的理解當中，如果想要判斷某個元素在不在集合當中，經典的結構應該是平衡樹和hash table。但是無論是哪一種方法，都逃不開一點，都需要存儲原值。

比如在爬蟲場景當中，我們需要記錄下之前爬過的網站。我們要將之前的網址全部都存儲在容器裡，然後在遇到新網站的時候去判斷是否已經爬過了。在這個問題當中，我們並不關心之前爬過的網站有哪些，我們只關心現在的網站有沒有在之前出現過。也就是說之前出現過什麼不重要，現在的有沒有出現過才重要。

我們利用平衡樹或者是Trie或者是AC自動機等數據結構和算法可以實現高效的查找，但是都離不開存儲下所有的字符串。想象一下，一個網址大概上百個字符，大約0.1KB，如果是一億個網址，就需要10GB了，如果是一百億一千億呢？顯然這麼大的規模就很麻煩了，今天要介紹的布隆過濾器就可以解決這個問題，而且不需要存儲下原值，這是一個非常巧妙的做法，讓我們一起來看下它的原理。

布隆過濾器本身的結構非常簡單，就是一個一維的bool型的數組，也就是說每一位只有0或者1，是一個bit，這個數組的長度是m。對於每個新增的項，我們使用K種不同的hash算法對它計算hash值。所以我們可以得到K個hash值，我們用hash值對m取模，假設是x。剛開始的時候數組內全部都是0，我們把所有x對應的位置標記為1。

舉個例子，假設我們一開始m是10，K是3。我們遇到第一個插入的值是”線性代數“，我們對它hash之後得到1，3，5，那麼我們將對應的位置標記成1.

然後我們又遇到了一個值是”高等數學“，hash之後得到1，8，9，我們還是將對應位置賦值成1，會發現1這個位置對應的值已經是1了，我們忽略就好。

如果這個時候我們想要判斷”概率統計”有沒有出現過，怎麼辦？很簡單，我們對“概率統計”再計算hash值。假設得到1，4，5，我們去遍歷一下對應的位置，發現4這個位置是0，說明之前沒有添加過“概率統計”，顯然“概率統計”沒有出現過。

但是如果“概率統計”hash之後的結果是1，3，8呢？我們判斷它出現過就錯了，答案很簡單，因為雖然1，3，8這個hash組合之前沒有出現過，但是對應的位置都在其他元素中出現過了，這樣就出現誤差了。所以我們可以知道，布隆過濾器對於不存在的判斷是準確的，但是對於存在的判斷是有可能有錯誤的。

代碼

布隆過濾器的原理很簡單，明白了之後，我們很容易寫出代碼：

<code># 插入元素
def BloomFilter(filter, value, hash_functions):
    m = len(filter)
    for func in hash_functions:
        idx = func(value) % m
        filter[idx] = True
    return filter
     

# 判斷元素
def MemberInFilter(filter, value, hash_functions):
    m = len(filter)
    for func in hash_functions:
        idx = func(value) % m
        if not filter[idx]:
            return False
    return True/<code>

錯誤率計算

之前的例子當中應該展示得很明白了，布隆過濾器雖然好用，但是會存在bad case，也就是判斷錯誤的情況。那麼，這種錯誤判斷髮生的概率有多大呢？

這個概率的計算也不難：由於數組長度是mm，所以插入一個bit它被置為1的概率是1m1m，插入一個元素需要插入k個hash值，所以插入一個元素，某一位沒有被置為1的概率是(1−1m)k(1−1m)k。插入n個元素之後，某一位依舊為0的概率是(1−1m)nk(1−1m)nk，它變成1的概率是1−(1−1m)nk1−(1−1m)nk。

如果在某次判斷當中，有一個沒有出現過的元素被認為已經在集合當中了，那麼也就是說它hash得到的位置均已經在之前被置為1了，這個時間發生的概率為：