99热在线精品一区二区三区_国产伦精品一区二区三区女破破_亚洲一区二区三区无码_精品国产欧美日韩另类一区

怎么在Python中利用Redis實現(xiàn)一個布隆過濾器？針對這個問題，這篇文章詳細介紹了相對應(yīng)的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

專注于為中小企業(yè)提供成都網(wǎng)站設(shè)計、成都網(wǎng)站制作服務(wù),電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)嵐山免費做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了千余家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實現(xiàn)規(guī)模擴充和轉(zhuǎn)變。

布隆過濾器是什么

　　布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數(shù)。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都比一般的算法要好的多，缺點是有一定的誤識別率和刪除困難。

布隆過濾器的基本思想

　　通過一種叫作散列表（又叫哈希表，Hash table）的數(shù)據(jù)結(jié)構(gòu)。它可以通過一個Hash函數(shù)將一個元素映射成一個位陣列（Bit array）中的一個點。這樣一來，我們只要看看這個點是不是1就可以知道集合中有沒有它了

布隆過濾器的優(yōu)缺點

優(yōu)點：

　　1.布隆過濾器的存儲空間和插入/查詢時間都是常數(shù)

　　2.Hash函數(shù)相互之間沒有關(guān)系，方便由硬件并行實現(xiàn)

　　3.布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優(yōu)勢

　　4.布隆過濾器可以表示全集，其它任何數(shù)據(jù)結(jié)構(gòu)都不能

缺點:

　　1.存在一定的誤算率，隨著存入的元素數(shù)量增加，誤算率隨之增加

　　　　（常見的補救辦法是建立一個小的白名單，存儲那些可能被誤判的元素。但是如果元素數(shù)量太少，則使用散列表足矣）

　　2.一般情況下不能從布隆過濾器中刪除元素

　　　　首先我們必須保證刪除的元素的確在布隆過濾器里面. 這一點單憑這個過濾器是無法保證的。另外計數(shù)器回繞也會造成問題。這就導(dǎo)致刪除元素需要很高的成本。

正文

簡單的python實現(xiàn)

pip install mmh4

對于安裝報錯，c++編譯錯誤問題：可以安裝    Microsoft Visual C++ Build Tools（）

 例子轉(zhuǎn)載（https://www.jb51.net/article/175929.htm）

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(10000, 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誤報 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)，存在不少誤報樣本，但是并不存在假陰性。

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

誤報

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

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

在使用布隆過濾器時，需要考慮誤報的潛在影響。

確定性

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

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

python 基于redis實現(xiàn)的bloomfilter(布隆過濾器)，BloomFilter_imooc

BloomFilter_imooc下載

下載地址：https://github.com/liyaopinner/BloomFilter_imooc

 py_bloomfilter.py(布隆過濾器)源碼:

import mmh4
import redis
import math
import time
class PyBloomFilter():
 #內(nèi)置100個隨機種子
 SEEDS = [543, 460, 171, 876, 796, 607, 650, 81, 837, 545, 591, 946, 846, 521, 913, 636, 878, 735, 414, 372,
  344, 324, 223, 180, 327, 891, 798, 933, 493, 293, 836, 10, 6, 544, 924, 849, 438, 41, 862, 648, 338,
  465, 562, 693, 979, 52, 763, 103, 387, 374, 349, 94, 384, 680, 574, 480, 307, 580, 71, 535, 300, 53,
  481, 519, 644, 219, 686, 236, 424, 326, 244, 212, 909, 202, 951, 56, 812, 901, 926, 250, 507, 739, 371,
  63, 584, 154, 7, 284, 617, 332, 472, 140, 605, 262, 355, 526, 647, 923, 199, 518]
 #capacity是預(yù)先估計要去重的數(shù)量
 #error_rate表示錯誤率
 #conn表示redis的連接客戶端
 #key表示在redis中的鍵的名字前綴
 def __init__(self, capacity=1000000000, error_rate=0.00000001, conn=None, key='BloomFilter'):
 self.m = math.ceil(capacity*math.log2(math.e)*math.log2(1/error_rate)) #需要的總bit位數(shù)
 self.k = math.ceil(math.log1p(2)*self.m/capacity)    #需要最少的hash次數(shù)
 self.mem = math.ceil(self.m/8/1024/1024)     #需要的多少M內(nèi)存
 self.blocknum = math.ceil(self.mem/512)     #需要多少個512M的內(nèi)存塊,value的第一個字符必須是ascii碼，所有最多有256個內(nèi)存塊
 self.seeds = self.SEEDS[0:self.k]
 self.key = key
 self.N = 2**31-1
 self.redis = conn
 # print(self.mem)
 # print(self.k)
 def add(self, value):
 name = self.key + "_" + str(ord(value[0])%self.blocknum)
 hashs = self.get_hashs(value)
 for hash in hashs:
  self.redis.setbit(name, hash, 1)
 def is_exist(self, value):
 name = self.key + "_" + str(ord(value[0])%self.blocknum)
 hashs = self.get_hashs(value)
 exist = True
 for hash in hashs:
  exist = exist & self.redis.getbit(name, hash)
 return exist
 def get_hashs(self, value):
 hashs = list()
 for seed in self.seeds:
  hash = mmh4.hash(value, seed)
  if hash >= 0:
  hashs.append(hash)
  else:
  hashs.append(self.N - hash)
 return hashs
pool = redis.ConnectionPool(host='127.0.0.1', port=6379, db=0)
conn = redis.StrictRedis(connection_pool=pool)
# 使用方法
# if __name__ == "__main__":
# bf = PyBloomFilter(conn=conn)  # 利用連接池連接Redis
# bf.add('www.jobbole.com')  # 向Redis默認的通道添加一個域名
# bf.add('www.luyin.org')   # 向Redis默認的通道添加一個域名
# print(bf.is_exist('www.zhihu.com')) # 打印此域名在通道里是否存在，存在返回1，不存在返回0
# print(bf.is_exist('www.luyin.org')) # 打印此域名在通道里是否存在，存在返回1，不存在返回0

關(guān)于怎么在Python中利用Redis實現(xiàn)一個布隆過濾器問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注創(chuàng)新互聯(lián)成都網(wǎng)站設(shè)計公司行業(yè)資訊頻道了解更多相關(guān)知識。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

本文標題：怎么在Python中利用Redis實現(xiàn)一個布隆過濾器-創(chuàng)新互聯(lián)
URL分享：http://www.ef60e0e.cn/article/dihecs.html