大數據算法——布隆過濾器

本文始發于個人公眾號:TechFlow,原創不易,求個關注


今天的文章和大家一起來學習大數據領域一個經常用到的算法——布隆過濾器。如果看過《數學之美》的同學對它應該并不陌生,它經常用在集合的判斷上,在海量數據的場景當中用來快速地判斷某個元素在不在一個龐大的集合當中。它的原理不難,但是設計非常巧妙,老實講在看《數學之美》之前,我也沒有聽說過這個數據結構,所以這篇文章也是我自己學習的筆記。


原理


在我之前的理解當中,如果想要判斷某個元素在不在集合當中,經典的結構應該是平衡樹和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組合之前沒有出現過,但是對應的位置都在其他元素中出現過了,這樣就出現誤差了。所以我們可以知道,布隆過濾器對于不存在的判斷是準確的,但是對于存在的判斷是有可能有錯誤的。


代碼


布隆過濾器的原理很簡單,明白了之后,我們很容易寫出代碼:

# 插入元素
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

錯誤率計算


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

這個概率的計算也不難:由于數組長度是\(m\),所以插入一個bit它被置為1的概率是\(\frac{1}{m}\),插入一個元素需要插入k個hash值,所以插入一個元素,某一位沒有被置為1的概率是\((1-\frac{1}{m})^k\)。插入n個元素之后,某一位依舊為0的概率是\((1-\frac{1}{m})^{nk}\),它變成1的概率是\(1-(1-\frac{1}{m})^{nk}\)

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

\[\displaystyle\left[1-(1-\frac{1}{m})^{nk}\right]^k \approx (1-e^{-\frac{kn}{m}})^k \]

這里用到了一個極限:

\[\displaystyle\lim_{x \to -\infty}(1-\frac{1}{x})^{-x}=e \]

我們來求一下沖突率最低時k的取值,為了方便計算,我們令\(b=e^{\frac{n}{m}}\),代入:

\[f(k) = (1-b^{-k})^k \\ \ln f(k) = k\ln(1-b^{-k}) \]

兩邊求導:

\[\begin{aligned} \frac{1}{f(k)}f'(k)&= ln(1-b^{-k}) + \frac{kb^{-k}\ln b}{1-b^{-k}} \end{aligned} \]

我們令導數等于0,來求它的極值:

\[\begin{aligned} \ln(1-b^{-k})(1-b^{-k})&=-kb^{-k}\ln b\\ \ln(1-b^{-k})(1-b^{-k})&=b^{-k}\ln b^{-k}\\ 1-b^{-k} &=b^{-k}\\ b^{-k} &= \frac{1}{2} \end{aligned} \]

我們將\(b^{-k}=\frac{1}{2}\)代入,可以求出最值時的\(k=\ln2\cdot\frac{m}{n} \approx 0.7\frac{m}{n}\)

同理,我們也可以預設定集合元素n和錯判率p,來求解對應的n,同樣利用上面的公式推算,可以得到\(m=-\frac{n\ln p}{(\ln2)^2}\)

如果我們允許一定的容錯,并且能夠大概估計會出現的元素的個數,那么完全可以使用布隆過濾器來代替傳統的容器判重的方法。這樣不僅效率極高,而且對于存儲的要求非常小。


靈魂拷問


原理也明白了,代碼也看懂了,這個時候我們來思考一個問題:布隆過濾器可以刪除元素嗎?

很遺憾,布隆過濾器是不支持刪除的。

因為布隆過濾器的每一個bit并不是獨占的,很有可能多個元素共享了某一位。如果我們直接刪除這一位的話,會影響其他的元素。

還是用上面的例子舉例:我們刪除線性代數,線性代數對應的位置是1,3,5,雖然我們并沒有刪除高等數學,但是由于我們移除了高等數學也用到的位置1,如果我們再去判斷高等數學是否存在就會得到錯誤的結果,雖然我們并沒有刪除它。

當然,在一些必須要有刪除功能的場景下,也是有辦法的。方法也很簡單,就是修改數據結構,將原本每一位一個bit改成一個int,當我們插入元素的時候,不再是將bit設置為true,而是讓對應的位置自增,而刪除的時候則是對應的位減一。這樣,我們刪除單個結果就不會影響其他元素了。

這種方法并不是完美的,由于布隆過濾器存在誤判的情況,很有可能我們會刪除原本就不存在的值,這同樣會對其他元素產生影響。

布隆過濾器是一個優缺點都非常明顯的數據結構,優點非常出色:速度足夠快,內存消耗小,代碼實現簡單。但是缺點也很明顯:不支持刪除元素,會有誤判的情況。這樣特點鮮明的數據結構真的非常吸引人。

今天的文章就是這些,如果覺得有所收獲,請順手點個關注吧,你們的舉手之勞對我來說很重要。

posted @ 2020-02-15 09:22  TechFlow2019  閱讀(7237)  評論(21編輯  收藏
最新chease0ldman老人|无码亚洲人妻下载|大香蕉在线看好吊妞视频这里有精品www|亚洲色情综合网