溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下Python怎么實現布隆過濾器，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
布隆過濾器
布隆過濾器是一種概率空間高效的數據結構。它與hashmap非常相似，用于檢索一個元素是否在一個集合中。它在檢索元素是否存在時，能很好地取舍空間使用率與誤報比例。正是由于這個特性，它被稱作概率性數據結構（probabilistic data structure）。
空間效率
我們來仔細地看看它的空間效率。如果你想在集合中存儲一系列的元素，有很多種不同的做法。你可以把數據存儲在hashmap，隨后在hashmap中檢索元素是否存在，hashmap的插入和查詢的效率都非常高。但是，由于hashmap直接存儲內容，所以空間利用率并不高。
如果希望提高空間利用率，我們可以在元素插入集合之前做一次哈希變換。還有其它方法呢？我們可以用位數組來存儲元素的哈希值。還有嗎，還有嗎？我們也允許在位數組中存在哈希沖突。這正是布隆過濾器的工作原理，它們就是基于允許哈希沖突的位數組，可能會造成一些誤報。在布隆過濾器的設計階段就允許哈希沖突的存在，否則空間使用就不夠緊湊了。
當使用列表或者集合時，空間效率都是重要且顯著的，那么布隆過濾器就應當被考慮。
布隆過濾器基礎
布隆過濾器是N位的位數組，其中N是位數組的大小。它還有另一個參數k，表示使用哈希函數的個數。這些哈希函數用來設置位數組的值。當往過濾器中插入元素x時，h2(x), h3(x), ..., hk(x)所對應索引位置的值被置“1”，索引值由各個哈希函數計算得到。注意，如果我們增加哈希函數的數量，誤報的概率會趨近于0.但是，插入和查找的時間開銷更大，布隆過濾器的容量也會減小。
為了用布隆過濾器檢驗元素是否存在，我們需要校驗是否所有的位置都被置“1”，與我們插入元素的過程非常相似。如果所有位置都被置“1”，那也就意味著該元素很有可能存在于布隆過濾器中。若有位置未被置“1”，那該元素一定不存在。
簡單的python實現
如果想實現一個簡單的布隆過濾器，我們可以這樣做：
from bitarray import bitarray
# 3rd party
import mmh4
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 = mmh4.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 = mmh4.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
從輸出結果可以發現，存在不少誤報樣本，但是并不存在假陰性。
不同于這段布隆過濾器的實現代碼，其它語言的多個實現版本并不提供哈希函數的參數。這是因為在實際應用中誤報比例這個指標比哈希函數更重要，用戶可以根據誤報比例的需求來調整哈希函數的個數。通常來說，size和error_rate是布隆過濾器的真正誤報比例。如果你在初始化階段減小了error_rate，它們會調整哈希函數的數量。
誤報
布隆過濾器能夠拍著胸脯說某個元素“肯定不存在”，但是對于一些元素它們會說“可能存在”。針對不同的應用場景，這有可能會是一個巨大的缺陷，亦或是無關緊要的問題。如果在檢索元素是否存在時不介意引入誤報情況，那么你就應當考慮用布隆過濾器。
另外，如果隨意地減小了誤報比率，哈希函數的數量相應地就要增加，在插入和查詢時的延時也會相應地增加。本節的另一個要點是，如果哈希函數是相互獨立的，并且輸入元素在空間中均勻的分布，那么理論上真實誤報率就不會超過理論值。否則，由于哈希函數的相關性和更頻繁的哈希沖突，布隆過濾器的真實誤報比例會高于理論值。
在使用布隆過濾器時，需要考慮誤報的潛在影響。
確定性
當你使用相同大小和數量的哈希函數時，某個元素通過布隆過濾器得到的是正反饋還是負反饋的結果是確定的。對于某個元素x，如果它現在可能存在，那五分鐘之后、一小時之后、一天之后、甚至一周之后的狀態都是可能存在。當我得知這一特性時有一點點驚訝。因為布隆過濾器是概率性的，那其結果顯然應該存在某種隨機因素，難道不是嗎？確實不是。它的概率性體現在我們無法判斷究竟哪些元素的狀態是可能存在。
換句話說，過濾器一旦做出可能存在的結論后，結論不會發生變化。
缺點
布隆過濾器并不十全十美。
布隆過濾器的容量
布隆過濾器需要事先知道將要插入的元素個數。如果你并不知道或者很難估計元素的個數，情況就不太好。你也可以隨機指定一個很大的容量，但這樣就會浪費許多存儲空間，存儲空間卻是我們試圖優化的首要任務，也是選擇使用布隆過濾器的原因之一。一種解決方案是創建一個能夠動態適應數據量的布隆過濾器，但是在某些應用場景下這個方案無效。有一種可擴展布隆過濾器，它能夠調整容量來適應不同數量的元素。它能彌補一部分短板。
布隆過濾器的構造和檢索
在使用布隆過濾器時，我們不僅要接受少量的誤報率，還要接受速度方面的額外時間開銷。相比于hashmap，對元素做哈希映射和構建布隆過濾器時必然存在一些額外的時間開銷。
無法返回元素本身
布隆過濾器并不會保存插入元素的內容，只能檢索某個元素是否存在，因為存在哈希函數和哈希沖突我們無法得到完整的元素列表。這是它相對于其它數據結構的最顯著優勢，空間的使用率也造成了這塊短板。
刪除某個元素
想從布隆過濾器中刪除某個元素可不是一件容易的事情，你無法撤回某次插入操作，因為不同項目的哈希結果可以被索引在同一位置。如果想撤消插入，你只能記錄每個索引位置被置位的次數，或是重新創建一次。兩種方法都有額外的開銷。基于不同的應用場景，若要刪除一些元素，我們更傾向于重建布隆過濾器。
在不同語言中的實現
在產品中，你肯定不想自己去實現布隆過濾器。有兩個原因，其中之一是選擇好的哈希函數和實現方法能有效改善錯誤率的分布。其次，它需要通過實戰測試，錯誤率和容量大小都要經得起實戰檢驗。各種語言都有開源實現的版本，以我自己的經驗，下面的Node.js和Python版本實現非常好用：
NodePython
還有更快版本的pybloomfilter（插入和檢索速度都比上面的python庫快10倍），但它需要運行在PyPy環境下，并不支持Python3。
以上是“Python怎么實現布隆過濾器”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
