Python怎么實(shí)現(xiàn)布隆過濾器

小編給大家分享一下Python怎么實(shí)現(xiàn)布隆過濾器，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

布隆過濾器

布隆過濾器是一種概率空間高效的數(shù)據(jù)結(jié)構(gòu)。它與hashmap非常相似，用于檢索一個(gè)元素是否在一個(gè)集合中。它在檢索元素是否存在時(shí)，能很好地取舍空間使用率與誤報(bào)比例。正是由于這個(gè)特性，它被稱作概率性數(shù)據(jù)結(jié)構(gòu)（probabilistic data structure）。

空間效率

我們來仔細(xì)地看看它的空間效率。如果你想在集合中存儲一系列的元素，有很多種不同的做法。你可以把數(shù)據(jù)存儲在hashmap，隨后在hashmap中檢索元素是否存在，hashmap的插入和查詢的效率都非常高。但是，由于hashmap直接存儲內(nèi)容，所以空間利用率并不高。

如果希望提高空間利用率，我們可以在元素插入集合之前做一次哈希變換。還有其它方法呢？我們可以用位數(shù)組來存儲元素的哈希值。還有嗎，還有嗎？我們也允許在位數(shù)組中存在哈希沖突。這正是布隆過濾器的工作原理，它們就是基于允許哈希沖突的位數(shù)組，可能會造成一些誤報(bào)。在布隆過濾器的設(shè)計(jì)階段就允許哈希沖突的存在，否則空間使用就不夠緊湊了。

當(dāng)使用列表或者集合時(shí)，空間效率都是重要且顯著的，那么布隆過濾器就應(yīng)當(dāng)被考慮。

布隆過濾器基礎(chǔ)

布隆過濾器是N位的位數(shù)組，其中N是位數(shù)組的大小。它還有另一個(gè)參數(shù)k，表示使用哈希函數(shù)的個(gè)數(shù)。這些哈希函數(shù)用來設(shè)置位數(shù)組的值。當(dāng)往過濾器中插入元素x時(shí)，h2(x), h3(x), ..., hk(x)所對應(yīng)索引位置的值被置“1”，索引值由各個(gè)哈希函數(shù)計(jì)算得到。注意，如果我們增加哈希函數(shù)的數(shù)量，誤報(bào)的概率會趨近于0.但是，插入和查找的時(shí)間開銷更大，布隆過濾器的容量也會減小。

為了用布隆過濾器檢驗(yàn)元素是否存在，我們需要校驗(yàn)是否所有的位置都被置“1”，與我們插入元素的過程非常相似。如果所有位置都被置“1”，那也就意味著該元素很有可能存在于布隆過濾器中。若有位置未被置“1”，那該元素一定不存在。

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

如果想實(shí)現(xiàn)一個(gè)簡單的布隆過濾器，我們可以這樣做：

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

輸出結(jié)果如下所示：

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誤報(bào) 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

從輸出結(jié)果可以發(fā)現(xiàn)，存在不少誤報(bào)樣本，但是并不存在假陰性。

不同于這段布隆過濾器的實(shí)現(xiàn)代碼，其它語言的多個(gè)實(shí)現(xiàn)版本并不提供哈希函數(shù)的參數(shù)。這是因?yàn)樵趯?shí)際應(yīng)用中誤報(bào)比例這個(gè)指標(biāo)比哈希函數(shù)更重要，用戶可以根據(jù)誤報(bào)比例的需求來調(diào)整哈希函數(shù)的個(gè)數(shù)。通常來說，size和error_rate是布隆過濾器的真正誤報(bào)比例。如果你在初始化階段減小了error_rate，它們會調(diào)整哈希函數(shù)的數(shù)量。

誤報(bào)

布隆過濾器能夠拍著胸脯說某個(gè)元素“肯定不存在”，但是對于一些元素它們會說“可能存在”。針對不同的應(yīng)用場景，這有可能會是一個(gè)巨大的缺陷，亦或是無關(guān)緊要的問題。如果在檢索元素是否存在時(shí)不介意引入誤報(bào)情況，那么你就應(yīng)當(dāng)考慮用布隆過濾器。

另外，如果隨意地減小了誤報(bào)比率，哈希函數(shù)的數(shù)量相應(yīng)地就要增加，在插入和查詢時(shí)的延時(shí)也會相應(yīng)地增加。本節(jié)的另一個(gè)要點(diǎn)是，如果哈希函數(shù)是相互獨(dú)立的，并且輸入元素在空間中均勻的分布，那么理論上真實(shí)誤報(bào)率就不會超過理論值。否則，由于哈希函數(shù)的相關(guān)性和更頻繁的哈希沖突，布隆過濾器的真實(shí)誤報(bào)比例會高于理論值。

在使用布隆過濾器時(shí)，需要考慮誤報(bào)的潛在影響。

確定性

當(dāng)你使用相同大小和數(shù)量的哈希函數(shù)時(shí)，某個(gè)元素通過布隆過濾器得到的是正反饋還是負(fù)反饋的結(jié)果是確定的。對于某個(gè)元素x，如果它現(xiàn)在可能存在，那五分鐘之后、一小時(shí)之后、一天之后、甚至一周之后的狀態(tài)都是可能存在。當(dāng)我得知這一特性時(shí)有一點(diǎn)點(diǎn)驚訝。因?yàn)椴悸∵^濾器是概率性的，那其結(jié)果顯然應(yīng)該存在某種隨機(jī)因素，難道不是嗎？確實(shí)不是。它的概率性體現(xiàn)在我們無法判斷究竟哪些元素的狀態(tài)是可能存在。

換句話說，過濾器一旦做出可能存在的結(jié)論后，結(jié)論不會發(fā)生變化。

缺點(diǎn)

布隆過濾器并不十全十美。

布隆過濾器的容量

布隆過濾器需要事先知道將要插入的元素個(gè)數(shù)。如果你并不知道或者很難估計(jì)元素的個(gè)數(shù)，情況就不太好。你也可以隨機(jī)指定一個(gè)很大的容量，但這樣就會浪費(fèi)許多存儲空間，存儲空間卻是我們試圖優(yōu)化的首要任務(wù)，也是選擇使用布隆過濾器的原因之一。一種解決方案是創(chuàng)建一個(gè)能夠動態(tài)適應(yīng)數(shù)據(jù)量的布隆過濾器，但是在某些應(yīng)用場景下這個(gè)方案無效。有一種可擴(kuò)展布隆過濾器，它能夠調(diào)整容量來適應(yīng)不同數(shù)量的元素。它能彌補(bǔ)一部分短板。

布隆過濾器的構(gòu)造和檢索

在使用布隆過濾器時(shí)，我們不僅要接受少量的誤報(bào)率，還要接受速度方面的額外時(shí)間開銷。相比于hashmap，對元素做哈希映射和構(gòu)建布隆過濾器時(shí)必然存在一些額外的時(shí)間開銷。

無法返回元素本身

布隆過濾器并不會保存插入元素的內(nèi)容，只能檢索某個(gè)元素是否存在，因?yàn)榇嬖诠：瘮?shù)和哈希沖突我們無法得到完整的元素列表。這是它相對于其它數(shù)據(jù)結(jié)構(gòu)的最顯著優(yōu)勢，空間的使用率也造成了這塊短板。

刪除某個(gè)元素

想從布隆過濾器中刪除某個(gè)元素可不是一件容易的事情，你無法撤回某次插入操作，因?yàn)椴煌?xiàng)目的哈希結(jié)果可以被索引在同一位置。如果想撤消插入，你只能記錄每個(gè)索引位置被置位的次數(shù)，或是重新創(chuàng)建一次。兩種方法都有額外的開銷?；诓煌膽?yīng)用場景，若要刪除一些元素，我們更傾向于重建布隆過濾器。

在不同語言中的實(shí)現(xiàn)

在產(chǎn)品中，你肯定不想自己去實(shí)現(xiàn)布隆過濾器。有兩個(gè)原因，其中之一是選擇好的哈希函數(shù)和實(shí)現(xiàn)方法能有效改善錯(cuò)誤率的分布。其次，它需要通過實(shí)戰(zhàn)測試，錯(cuò)誤率和容量大小都要經(jīng)得起實(shí)戰(zhàn)檢驗(yàn)。各種語言都有開源實(shí)現(xiàn)的版本，以我自己的經(jīng)驗(yàn)，下面的Node.js和Python版本實(shí)現(xiàn)非常好用：

NodePython

還有更快版本的pybloomfilter（插入和檢索速度都比上面的python庫快10倍），但它需要運(yùn)行在PyPy環(huán)境下，并不支持Python3。

以上是“Python怎么實(shí)現(xiàn)布隆過濾器”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道！