布隆過濾器的概述及Python實現(xiàn)方法
布隆過濾器
布隆過濾器是一種概率空間高效的數(shù)據(jù)結構。它與hashmap非常相似，用于檢索一個元素是否在一個集合中。它在檢索元素是否存在時，能很好地取舍空間使用率與誤報比例。正是由于這個特性，它被稱作概率性數(shù)據(jù)結構（probabilistic data structure）。
空間效率
我們來仔細地看看它的空間效率。如果你想在集合中存儲一系列的元素，有很多種不同的做法。你可以把數(shù)據(jù)存儲在hashmap，隨后在hashmap中檢索元素是否存在，hashmap的插入和查詢的效率都非常高。但是，由于hashmap直接存儲內容，所以空間利用率并不高。
如果希望提高空間利用率，我們可以在元素插入集合之前做一次哈希變換。還有其它方法呢？我們可以用位數(shù)組來存儲元素的哈希值。還有嗎，還有嗎？我們也允許在位數(shù)組中存在哈希沖突。這正是布隆過濾器的工作原理，它們就是基于允許哈希沖突的位數(shù)組，可能會造成一些誤報。在布隆過濾器的設計階段就允許哈希沖突的存在，否則空間使用就不夠緊湊了。
當使用列表或者集合時，空間效率都是重要且顯著的，那么布隆過濾器就應當被考慮。
布隆過濾器基礎
布隆過濾器是N位的位數(shù)組，其中N是位數(shù)組的大小。它還有另一個參數(shù)k，表示使用哈希函數(shù)的個數(shù)。這些哈希函數(shù)用來設置位數(shù)組的值。當往過濾器中插入元素x時，h1(x), h2(x), ..., hk(x)所對應索引位置的值被置“1”，索引值由各個哈希函數(shù)計算得到。注意，如果我們增加哈希函數(shù)的數(shù)量，誤報的概率會趨近于0.但是，插入和查找的時間開銷更大，布隆過濾器的容量也會減小。
為了用布隆過濾器檢驗元素是否存在，我們需要校驗是否所有的位置都被置“1”，與我們插入元素的過程非常相似。如果所有位置都被置“1”，那也就意味著該元素很有可能存在于布隆過濾器中。若有位置未被置“1”，那該元素一定不存在。
簡單的python實現(xiàn)
如果想實現(xiàn)一個簡單的布隆過濾器，我們可以這樣做：
from bitarray import bitarray
# 3rd party
import mmh3
class BloomFilter(set):
def __init__(self, size, hash_count):
super(BloomFilter, self).__init__()
self.bit_array = bitarray(size)
self.bit_array.setall(0)
self.size = size
self.hash_count = hash_count
def __len__(self):
return self.size
def __iter__(self):
return iter(self.bit_array)
def add(self, item):
for ii in range(self.hash_count):
index = mmh3.hash(item, ii) % self.size
self.bit_array[index] = 1
return self
def __contains__(self, item):
out = True
for ii in range(self.hash_count):
index = mmh3.hash(item, ii) % self.size
if self.bit_array[index] == 0:
out = False
return out
def main():
bloom = BloomFilter(100, 10)
animals = ['dog', 'cat', 'giraffe', 'fly', 'mosquito', 'horse', 'eagle',
'bird', 'bison', 'boar', 'butterfly', 'ant', 'anaconda', 'bear',
'chicken', 'dolphin', 'donkey', 'crow', 'crocodile']
# First insertion of animals into the bloom filter
for animal in animals:
bloom.add(animal)
# Membership existence for already inserted animals
# There should not be any false negatives
for animal in animals:
if animal in bloom:
print('{} is in bloom filter as expected'.format(animal))
else:
print('Something is terribly went wrong for {}'.format(animal))
print('FALSE NEGATIVE!')
# Membership existence for not inserted animals
# There could be false positives
other_animals = ['badger', 'cow', 'pig', 'sheep', 'bee', 'wolf', 'fox',
'whale', 'shark', 'fish', 'turkey', 'duck', 'dove',
'deer', 'elephant', 'frog', 'falcon', 'goat', 'gorilla',
'hawk' ]
for other_animal in other_animals:
if other_animal in bloom:
print('{} is not in the bloom, but a false positive'.format(other_animal))
else:
print('{} is not in the bloom filter as expected'.format(other_animal))
if __name__ == '__main__':
main()
輸出結果如下所示：
dog is in bloom filter as expected cat is in bloom filter as expected giraffe is in bloom filter as expected fly is in bloom filter as expected mosquito is in bloom filter as expected horse is in bloom filter as expected eagle is in bloom filter as expected bird is in bloom filter as expected bison is in bloom filter as expected boar is in bloom filter as expected butterfly is in bloom filter as expected ant is in bloom filter as expected anaconda is in bloom filter as expected bear is in bloom filter as expected chicken is in bloom filter as expected dolphin is in bloom filter as expected donkey is in bloom filter as expected crow is in bloom filter as expected crocodile is in bloom filter as expected badger is not in the bloom filter as expected cow is not in the bloom filter as expected pig is not in the bloom filter as expected sheep is not in the bloom, but a false positive bee is not in the bloom filter as expected wolf is not in the bloom filter as expected fox is not in the bloom filter as expected whale is not in the bloom filter as expected shark is not in the bloom, but a false positive fish is not in the bloom, but a false positive turkey is not in the bloom filter as expected duck is not in the bloom filter as expected dove is not in the bloom誤報 filter as expected deer is not in the bloom filter as expected elephant is not in the bloom, but a false positive frog is not in the bloom filter as expected falcon is not in the bloom filter as expected goat is not in the bloom filter as expected gorilla is not in the bloom filter as expected hawk is not in the bloom filter as expected
從輸出結果可以發(fā)現(xiàn)，存在不少誤報樣本，但是并不存在假陰性。
不同于這段布隆過濾器的實現(xiàn)代碼，其它語言的多個實現(xiàn)版本并不提供哈希函數(shù)的參數(shù)。這是因為在實際應用中誤報比例這個指標比哈希函數(shù)更重要，用戶可以根據(jù)誤報比例的需求來調整哈希函數(shù)的個數(shù)。通常來說，size和error_rate是布隆過濾器的真正誤報比例。如果你在初始化階段減小了error_rate，它們會調整哈希函數(shù)的數(shù)量。
誤報
布隆過濾器能夠拍著胸脯說某個元素“肯定不存在”，但是對于一些元素它們會說“可能存在”。針對不同的應用場景，這有可能會是一個巨大的缺陷，亦或是無關緊要的問題。如果在檢索元素是否存在時不介意引入誤報情況，那么你就應當考慮用布隆過濾器。
另外，如果隨意地減小了誤報比率，哈希函數(shù)的數(shù)量相應地就要增加，在插入和查詢時的延時也會相應地增加。本節(jié)的另一個要點是，如果哈希函數(shù)是相互獨立的，并且輸入元素在空間中均勻的分布，那么理論上真實誤報率就不會超過理論值。否則，由于哈希函數(shù)的相關性和更頻繁的哈希沖突，布隆過濾器的真實誤報比例會高于理論值。
在使用布隆過濾器時，需要考慮誤報的潛在影響。
確定性
當你使用相同大小和數(shù)量的哈希函數(shù)時，某個元素通過布隆過濾器得到的是正反饋還是負反饋的結果是確定的。對于某個元素x，如果它現(xiàn)在可能存在，那五分鐘之后、一小時之后、一天之后、甚至一周之后的狀態(tài)都是可能存在。當我得知這一特性時有一點點驚訝。因為布隆過濾器是概率性的，那其結果顯然應該存在某種隨機因素，難道不是嗎？確實不是。它的概率性體現(xiàn)在我們無法判斷究竟哪些元素的狀態(tài)是可能存在。
換句話說，過濾器一旦做出可能存在的結論后，結論不會發(fā)生變化。
缺點
布隆過濾器并不十全十美。
布隆過濾器的容量
布隆過濾器需要事先知道將要插入的元素個數(shù)。如果你并不知道或者很難估計元素的個數(shù)，情況就不太好。你也可以隨機指定一個很大的容量，但這樣就會浪費許多存儲空間，存儲空間卻是我們試圖優(yōu)化的首要任務，也是選擇使用布隆過濾器的原因之一。一種解決方案是創(chuàng)建一個能夠動態(tài)適應數(shù)據(jù)量的布隆過濾器，但是在某些應用場景下這個方案無效。有一種可擴展布隆過濾器，它能夠調整容量來適應不同數(shù)量的元素。它能彌補一部分短板。
布隆過濾器的構造和檢索
在使用布隆過濾器時，我們不僅要接受少量的誤報率，還要接受速度方面的額外時間開銷。相比于hashmap，對元素做哈希映射和構建布隆過濾器時必然存在一些額外的時間開銷。
無法返回元素本身
布隆過濾器并不會保存插入元素的內容，只能檢索某個元素是否存在，因為存在哈希函數(shù)和哈希沖突我們無法得到完整的元素列表。這是它相對于其它數(shù)據(jù)結構的最顯著優(yōu)勢，空間的使用率也造成了這塊短板。
刪除某個元素
想從布隆過濾器中刪除某個元素可不是一件容易的事情，你無法撤回某次插入操作，因為不同項目的哈希結果可以被索引在同一位置。如果想撤消插入，你只能記錄每個索引位置被置位的次數(shù)，或是重新創(chuàng)建一次。兩種方法都有額外的開銷?；诓煌膽脠鼍埃粢獎h除一些元素，我們更傾向于重建布隆過濾器。
在不同語言中的實現(xiàn)
在產品中，你肯定不想自己去實現(xiàn)布隆過濾器。有兩個原因，其中之一是選擇好的哈希函數(shù)和實現(xiàn)方法能有效改善錯誤率的分布。其次，它需要通過實戰(zhàn)測試，錯誤率和容量大小都要經得起實戰(zhàn)檢驗。各種語言都有開源實現(xiàn)的版本，以我自己的經驗，下面的Node.js和Python版本實現(xiàn)非常好用：
還有更快版本的pybloomfilter（插入和檢索速度都比上面的python庫快10倍），但它需要運行在PyPy環(huán)境下，并不支持Python3。
總結
以上所述是小編給大家介紹的布隆過濾器的概述及Python實現(xiàn)方法，希望對大家有所幫助，如果大家有任何疑問歡迎給我留言，小編會及時回復大家的！
相關文章
這篇文章主要介紹了Django 簡單實現(xiàn)分頁與搜索功能的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-11-11
今天小編就為大家分享一篇python將秒數(shù)轉化為時間格式的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-09-09
利用Pycharm + Django搭建一個簡單Python Web項目的步驟
這篇文章主要介紹了利用Pycharm + Django搭建一個簡單Python Web項目的步驟，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-10-10
這篇文章主要介紹了Python中的迭代器與生成器高級用法解析,生成器在Python中是迭代器的一種,這里我們會講到生成表達式、鏈式生成器等深層次內容,需要的朋友可以參考下2016-06-06
這篇文章主要為大家詳細介紹了python學生信息管理系統(tǒng)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-03-03
這篇文章主要介紹了使用python解析xml成對應的html示例,需要的朋友可以參考下2014-04-04
實際開發(fā)中我們可能會遇到一類問題，如何將Pandas DataFrame轉換為字典，本文就來介紹一下，感興趣的可以了解一下2021-05-05
win10系統(tǒng)下python3安裝及pip換源和使用教程
這篇文章主要介紹了win10系統(tǒng)下python3安裝及pip換源和使用教程,本文給大家介紹的非常詳細，具有一定的參考借鑒價值，需要的朋友可以參考下2020-01-01
這篇文章主要介紹了關于pytorch求導總結(torch.autograd)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-06-06
僅用50行Python代碼實現(xiàn)一個簡單的代理服務器
這篇文章主要介紹了僅用50行Python代碼實現(xiàn)一個簡單的代理服務器,利用最簡單的client->proxy->forward原理在socket模塊下編寫,需要的朋友可以參考下2015-04-04