Python?Counting?Bloom?Filter怎么實(shí)現(xiàn)

這篇“Python Counting Bloom Filter怎么實(shí)現(xiàn)”文章的知識(shí)點(diǎn)大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細(xì)，步驟清晰，具有一定的借鑒價(jià)值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來(lái)看看這篇“Python Counting Bloom Filter怎么實(shí)現(xiàn)”文章吧。

前言

標(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ù)。

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位就足夠了。

簡(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 mmh4
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 = mmh4.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 = mmh4.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 = mmh4.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"))

以上就是關(guān)于“Python Counting Bloom Filter怎么實(shí)現(xiàn)”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對(duì)大家有幫助，若想了解更多相關(guān)的知識(shí)內(nèi)容，請(qǐng)關(guān)注億速云行業(yè)資訊頻道。