前言

標(biāo)準(zhǔn)的 Bloom Filter 是一種比較簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，只支持插入和查找兩種操作。在所要表達(dá)的集合是靜態(tài)集合的時(shí)候，標(biāo)準(zhǔn) Bloom Filter 可以很好地工作，但是如果要表達(dá)的集合經(jīng)常變動(dòng)，標(biāo)準(zhǔn)Bloom Filter的弊端就顯現(xiàn)出來(lái)了，因?yàn)樗恢С謩h除操作。這就引出來(lái)了本文要談的 Counting Bloom Filter，后文簡(jiǎn)寫(xiě)為 CBF。

原理

一、BF 為什么不支持刪除

BF 為什么不能刪除元素？我們可以舉一個(gè)例子來(lái)說(shuō)明。

比如要?jiǎng)h除集合中的成員 dantezhao，那么就會(huì)先用 k 個(gè)哈希函數(shù)對(duì)其計(jì)算，因?yàn)?dantezhao 已經(jīng)是集合成員，那么在位數(shù)組的對(duì)應(yīng)位置一定是 1，我們?nèi)缫獎(jiǎng)h除這個(gè)成員 dantezhao，就需要把計(jì)算出來(lái)的所有位置上的 1 置為 0，即將 5 和 16 兩位置為 0 即可。

問(wèn)題來(lái)了！現(xiàn)在，先假設(shè) yyj 本身是屬于集合的元素，如果需要查詢(xún) yyj 是否在集合中，通過(guò)哈希函數(shù)計(jì)算后，我們會(huì)去判斷第 16 和 第 26 位是否為 1， 這時(shí)候就得到了第 16 位為 0 的結(jié)果，即 yyj 不屬于集合。 顯然這里是誤判的。

二、什么是 Counting Bloom Filter

Counting Bloom Filter 的出現(xiàn)，解決了上述問(wèn)題，它將標(biāo)準(zhǔn) Bloom Filter 位數(shù)組的每一位擴(kuò)展為一個(gè)小的計(jì)數(shù)器（Counter），在插入元素時(shí)給對(duì)應(yīng)的 k （k 為哈希函數(shù)個(gè)數(shù)）個(gè) Counter 的值分別加 1，刪除元素時(shí)給對(duì)應(yīng)的 k 個(gè) Counter 的值分別減 1。Counting Bloom Filter 通過(guò)多占用幾倍的存儲(chǔ)空間的代價(jià)， 給 Bloom Filter 增加了刪除操作?；驹硎遣皇呛芎?jiǎn)單？看下圖就能明白它和 Bloom Filter 的區(qū)別在哪。

三、Counter 大小的選擇

CBF 和 BF 的一個(gè)主要的不同就是 CBF 用一個(gè) Counter 取代了 BF 中的一位，那么 Counter 到底取多大才比較合適呢？這里就要考慮到空間利用率的問(wèn)題了，從使用的角度來(lái)看，當(dāng)然是越大越好，因?yàn)?Counter 越大就能表示越多的信息。但是越大的 Counter 就意味著更多的資源占用，而且在很多時(shí)候會(huì)造成極大的空間浪費(fèi)。

因此，我們?cè)谶x擇 Counter 的時(shí)候，可以看 Counter 取值的范圍多小就可以滿(mǎn)足需求。

根據(jù)論文中描述，某一個(gè) Counter 的值大于或等于 i 的概率可以通過(guò)如下公式描述，其中 n 為集合的大小，m 為 Counter 的數(shù)量，k 為 哈希函數(shù)的個(gè)數(shù)。

在之前的文章《Bloom Filter 的數(shù)學(xué)背景》中已經(jīng)得出，k 的最佳取值為 k = m/n * ln2，將其帶入公式后可得。

如果每個(gè) Counter 分配 4 位，那么當(dāng) Counter 的值達(dá)到 16 時(shí)就會(huì)溢出。這個(gè)概率如下，這個(gè)值足夠小，因此對(duì)于大多數(shù)應(yīng)用程序來(lái)說(shuō)，4位就足夠了。

關(guān)于 CBF 中 Counter 大小的選擇，主要參考這篇論文：《Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol》，在論文的第 6、7 兩頁(yè)專(zhuān)門(mén)對(duì)其做了一番闡述。這里不再推導(dǎo)細(xì)節(jié)，只給出一個(gè)大概的說(shuō)明，感興趣的童鞋可以參考原論文。

簡(jiǎn)單的實(shí)現(xiàn)

還是實(shí)現(xiàn)一個(gè)簡(jiǎn)單的程序來(lái)熟悉 CBF 的原理，這里和 BF 的區(qū)別有兩個(gè)：

• 一個(gè)是我們沒(méi)有用 bitarray 提供的位數(shù)組，而是使用了 bytearray 提供的一個(gè) byte數(shù)組，因此每一個(gè) Counter 的取值范圍在 0~255。
• 另一個(gè)是多了一個(gè) remove 方法來(lái)刪除集合中的元素。

代碼很簡(jiǎn)單，只是為了理解概念，實(shí)際中使用的庫(kù)會(huì)有很大差別。

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"))

總結(jié)

CBF 雖說(shuō)解決了 BF 的不能刪除元素的問(wèn)題，但是自身仍有不少的缺陷有待完善，比如 Counter 的引入就會(huì)帶來(lái)很大的資源浪費(fèi)，CBF 的 FP 還有很大可以降低的空間， 因此在實(shí)際的使用場(chǎng)景中會(huì)有很多 CBF 的升級(jí)版。

比如 SBF（Spectral Bloom Filter）在 CBF 的基礎(chǔ)上提出了元素出現(xiàn)頻率查詢(xún)的概念，將CBF的應(yīng)用擴(kuò)展到了 multi-set 的領(lǐng)域；dlCBF（d-Left Counting Bloom Filter）利用 d-left hashing 的方法存儲(chǔ) fingerprint，解決哈希表的負(fù)載平衡問(wèn)題；ACBF（Accurate Counting Bloom Filter）通過(guò) offset indexing 的方式將 Counter 數(shù)組劃分成多個(gè)層級(jí)，來(lái)降低誤判率。這些內(nèi)容，有機(jī)會(huì)再分享。

到此這篇關(guān)于Python Counting Bloom Filter原理與實(shí)現(xiàn)詳細(xì)介紹的文章就介紹到這了,更多相關(guān)Python Counting Bloom Filter內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論