Bloom Filter

Bloom Filter 是一種可以儲存「某一個元素是否存在」的集合, 我們可以用這種資料結構快速查詢像是「某隻小雞是否在這間雞舍」或「某位學生是不是在這間實驗室」 這一類的資訊。

這種資料結構有三個非常重要的特性:

  • 不存在漏報(False Negative):有一定會說
  • 但卻可能誤報(False Positive):但說了不一定會對
  • 確定某元素是否在集合的代價和元素數目無關:不管對不對,反正很快

這個結構有趣的地方在於它並不準確,它可能會誤報,也許它會說:「這隻小雞在這間雞舍!」, 但實際上這隻小雞並不在這間雞舍。不過反過來說,若它說:「這隻小雞『不在』這間雞舍!」, 那小雞就絕對不會出現在這間雞舍中。

雖然這種資料結構可能不準確,但查詢速度卻非常快,所以很適合用來當作事前的篩選。 舉例而言,若我想找「某隻小雞在那一間雞舍的資訊」,就可以透過 Bloom Filter 對每一間雞舍做篩選, 篩去 Bloom Filter 說「這隻小雞不在這間雞舍」的雞舍,再對剩下的雞舍做詳細的調查, 這樣就會比漫無目的找還要快上許多。

一般而言,一個搜尋演算法,若搜尋的速度要很快,資料結構所佔的空間就會相對比較大, 但若要求佔的空間要小,速度可能就快不起來。基本上,好的演算法就是取得空間和速度的平衡點, 讓速度足夠快,而且空間也不會用太多。

但 Bloom filter 卻很神奇的既速度快,而且所佔的空間也很小,不過代價是用準確率換取的空間大小。 空間越大,準確率越高,空間越小,準確率就越低。

「那麼這個方法到底是怎麼做到這一點的呢?」

這個方法是由一個叫 Bloom 的人提出的(顯而易見吧?), 它實際上是一個很長的 bit-vector,和很多個 Hash 函式組成。 演算法的最初的概念也很簡單,想要找某元素存不存在? 那就準備一個 bit-vector,再使用 Hash 函式為每個元素找對應的位置。 如果該元素存在,即設為 1,如果不存在,就設為 0。 那麼以後想查詢某元素存不存在,只要看 Hash 函式編碼後對應的位置內容是不是 1 即可。

很簡單吧?不過若要使用 Hash 函式的話,就會有一個很重要但很基本問題一定要考慮, 那就是 Key 和 Key 之間可能會有「碰撞」的問題,而一旦發生「碰撞」,就有可能誤報, 明明不存在,卻回報存在。

這個問題最直觀的解決辦法就是增加 bit-vector 的大小,但是增加大小就會佔用更多的空間, 這樣就會違反 Bloom filter 要佔很小空間的初衷了。

所以 Bloom 實際上採用的是另一種解法,那就是使用多個 Hash 函式。

「一個 Hash 函式發生碰撞很容易,但若使用多個不同的 Hash 函式, 要每一個 Hash 函式對應的位置都剛好同時碰撞就很不容易了吧?」

若使用多個 Hash 函式對應到 bit-vector 上,因為要每一個對應到的都是 1 才會符合, 只要有其中一個 Hash 函式對應到的位置內容不為 1,就一定不會存在,所以相對於原本的方法, 「誤報」的可能性自然會比較低。不過這並不代表不會發生碰撞,所以仍然有「誤報」的可能。

這個方法的好處是可以在不增加 bit-vector 的大小而且保持搜尋速度的情況下, 有效的減少了誤報的機會。

由於 Bloom Filter 其實就是使用 Hash 函式,所以搜尋的速度很快, 而且所佔的空間也很小(Hash 方法的特性)。不過這個方法雖然好,但還是有一些缺點, 其中最重要的就是不支援刪除,由於採用多個 Hash 函式的原因, 所以我們不敢隨便把一個 Hash 函式對應的位置從 1 改成 0, 因為這有可能會影響別的 Hash 函式。

很多地方都可以用到 Bloom Filter ,比如說 IP Iookup。使用的概念主要都是 「為了增加搜尋的速度,於是在搜尋的過程中另外添加一個篩選器,先過濾掉不可能的結果, 再做搜尋,這樣就可以增加搜尋的速度。」,如下圖:

另外還有很多不同的運用和延伸,這之後再研究吧。

發表迴響