Python Counting Bloom Filter原理與實現詳細介紹

Posted on by

前言

標準的 Bloom Filter 是一種比較簡單的數據結構，隻支持插入和查找兩種操作。在所要表達的集合是靜態集合的時候，標準 Bloom Filter 可以很好地工作，但是如果要表達的集合經常變動，標準Bloom Filter的弊端就顯現出來瞭，因為它不支持刪除操作。這就引出來瞭本文要談的 Counting Bloom Filter，後文簡寫為 CBF。

原理

一、BF 為什麼不支持刪除

BF 為什麼不能刪除元素？我們可以舉一個例子來說明。

比如要刪除集合中的成員 dantezhao，那麼就會先用 k 個哈希函數對其計算，因為 dantezhao 已經是集合成員，那麼在位數組的對應位置一定是 1，我們如要要刪除這個成員 dantezhao，就需要把計算出來的所有位置上的 1 置為 0，即將 5 和 16 兩位置為 0 即可。

問題來瞭！現在，先假設 yyj 本身是屬於集合的元素，如果需要查詢 yyj 是否在集合中，通過哈希函數計算後，我們會去判斷第 16 和 第 26 位是否為 1， 這時候就得到瞭第 16 位為 0 的結果，即 yyj 不屬於集合。 顯然這裡是誤判的。

二、什麼是 Counting Bloom Filter

Counting Bloom Filter 的出現，解決瞭上述問題，它將標準 Bloom Filter 位數組的每一位擴展為一個小的計數器（Counter），在插入元素時給對應的 k （k 為哈希函數個數）個 Counter 的值分別加 1，刪除元素時給對應的 k 個 Counter 的值分別減 1。Counting Bloom Filter 通過多占用幾倍的存儲空間的代價， 給 Bloom Filter 增加瞭刪除操作。基本原理是不是很簡單？看下圖就能明白它和 Bloom Filter 的區別在哪。

三、Counter 大小的選擇

CBF 和 BF 的一個主要的不同就是 CBF 用一個 Counter 取代瞭 BF 中的一位，那麼 Counter 到底取多大才比較合適呢？這裡就要考慮到空間利用率的問題瞭，從使用的角度來看，當然是越大越好，因為 Counter 越大就能表示越多的信息。但是越大的 Counter 就意味著更多的資源占用，而且在很多時候會造成極大的空間浪費。

因此，我們在選擇 Counter 的時候，可以看 Counter 取值的范圍多小就可以滿足需求。

根據論文中描述，某一個 Counter 的值大於或等於 i 的概率可以通過如下公式描述，其中 n 為集合的大小，m 為 Counter 的數量，k 為 哈希函數的個數。

在之前的文章《Bloom Filter 的數學背景》中已經得出，k 的最佳取值為 k = m/n * ln2，將其帶入公式後可得。

如果每個 Counter 分配 4 位，那麼當 Counter 的值達到 16 時就會溢出。這個概率如下，這個值足夠小，因此對於大多數應用程序來說，4位就足夠瞭。

關於 CBF 中 Counter 大小的選擇，主要參考這篇論文：《Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol》，在論文的第 6、7 兩頁專門對其做瞭一番闡述。這裡不再推導細節，隻給出一個大概的說明，感興趣的童鞋可以參考原論文。

簡單的實現

還是實現一個簡單的程序來熟悉 CBF 的原理，這裡和 BF 的區別有兩個：

  • 一個是我們沒有用 bitarray 提供的位數組，而是使用瞭 bytearray 提供的一個 byte數組，因此每一個 Counter 的取值范圍在 0~255。
  • 另一個是多瞭一個 remove 方法來刪除集合中的元素。

代碼很簡單，隻是為瞭理解概念，實際中使用的庫會有很大差別。

import mmh3
class CountingBloomFilter:
    def __init__(self, size, hash_num):
        self.size = size
        self.hash_num = hash_num
        self.byte_array = bytearray(size)
    def add(self, s):
        for seed in range(self.hash_num):
            result = mmh3.hash(s, seed) % self.size
            if self.bit_array[result] < 256:
                self.bit_array[result] += 1
    def lookup(self, s):
        for seed in range(self.hash_num):
            result = mmh3.hash(s, seed) % self.size
            if self.bit_array[result] == 0:
                return "Nope"
        return "Probably"
    def remove(self, s):
        for seed in range(self.hash_num):
            result = mmh3.hash(s, seed) % self.size
            if self.bit_array[result] > 0:
                self.bit_array[result] -= 1
cbf = CountingBloomFilter(500000, 7)
cbf.add("dantezhao")
cbf.add("yyj")
cbf.remove("dantezhao")
print (cbf.lookup("dantezhao"))
print (cbf.lookup("yyj"))

總結

CBF 雖說解決瞭 BF 的不能刪除元素的問題，但是自身仍有不少的缺陷有待完善，比如 Counter 的引入就會帶來很大的資源浪費，CBF 的 FP 還有很大可以降低的空間， 因此在實際的使用場景中會有很多 CBF 的升級版。

比如 SBF（Spectral Bloom Filter）在 CBF 的基礎上提出瞭元素出現頻率查詢的概念，將CBF的應用擴展到瞭 multi-set 的領域；dlCBF（d-Left Counting Bloom Filter）利用 d-left hashing 的方法存儲 fingerprint，解決哈希表的負載平衡問題；ACBF（Accurate Counting Bloom Filter）通過 offset indexing 的方式將 Counter 數組劃分成多個層級，來降低誤判率。這些內容，有機會再分享。

到此這篇關於Python Counting Bloom Filter原理與實現詳細介紹的文章就介紹到這瞭,更多相關Python Counting Bloom Filter內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：