本篇文章給大家帶來的內容是關于如何使用Redis的Bloomfilter去重，既用上了Bloomfilter的海量去重能力，又用上了Redis的可持久化能力，有一定的參考價值，有需要的朋友可以參考一下，希望對你有所幫助。

“去重”是日常工作中會經常用到的一項技能，在爬蟲領域更是常用，并且規模一般都比較大。去重需要考慮兩個點：去重的數據量、去重速度。為了保持較快的去重速度，一般選擇在內存中進行去重。

數據量不大時，可以直接放在內存里面進行去重，例如python可以使用set()進行去重。

當去重數據需要持久化時可以使用redis的set數據結構。

當數據量再大一點時，可以用不同的加密算法先將長字符串壓縮成 16/32/40 個字符，再使用上面兩種方法去重；

當數據量達到億（甚至十億、百億）數量級時，內存有限，必須用“位”來去重，才能夠滿足需求。Bloomfilter就是將去重對象映射到幾個內存“位”，通過幾個位的 0/1值來判斷一個對象是否已經存在。

然而Bloomfilter運行在一臺機器的內存上，不方便持久化（機器down掉就什么都沒啦），也不方便分布式爬蟲的統一去重。如果可以在Redis上申請內存進行Bloomfilter，以上兩個問題就都能解決了。

# encoding=utf-8import redisfrom hashlib import md5html' target='_blank'>class SimpleHash(object): def __init__(self, cap, seed): self.cap = cap self.seed = seed def hash(self, value): ret = 0 for i in range(len(value)): ret += self.seed * ret + ord(value[i]) return (self.cap - 1) retclass BloomFilter(object): def __init__(self, host= localhost , port=6379, db=0, blockNum=1, key= bloomfilter ): :param host: the host of Redis :param port: the port of Redis :param db: witch db in Redis :param blockNum: one blockNum for about 90,000,000; if you have more strings for filtering, increase it. :param key: the key s name in Redis self.server = redis.Redis(host=host, port=port, db=db) self.bit_size = 1 31 # Redis的String類型最大容量為512M，現使用256M self.seeds = [5, 7, 11, 13, 31, 37, 61] self.key = key self.blockNum = blockNum self.hashfunc = [] for seed in self.seeds: self.hashfunc.append(SimpleHash(self.bit_size, seed)) def isContains(self, str_input): if not str_input: return False m5 = md5() m5.update(str_input) str_input = m5.hexdigest() ret = True name = self.key + str(int(str_input[0:2], 16) % self.blockNum) for f in self.hashfunc: loc = f.hash(str_input) ret = ret self.server.getbit(name, loc) return ret def insert(self, str_input): m5 = md5() m5.update(str_input) str_input = m5.hexdigest() name = self.key + str(int(str_input[0:2], 16) % self.blockNum) for f in self.hashfunc: loc = f.hash(str_input) self.server.setbit(name, loc, 1)if __name__ == __main__ : 第一次運行時會顯示 not exists!，之后再運行會顯示 exists!  bf = BloomFilter() if bf.isContains( http://www.baidu.com ): # 判斷字符串是否存在 print exists!  else: print not exists!  bf.insert( http://www.baidu.com )

Bloomfilter算法如何使用位去重，這個百度上有很多解釋。簡單點說就是有幾個seeds，現在申請一段內存空間，一個seed可以和字符串哈希映射到這段內存上的一個位，幾個位都為1即表示該字符串已經存在。插入的時候也是，將映射出的幾個位都置為1。

需要提醒一下的是Bloomfilter算法會有漏失概率，即不存在的字符串有一定概率被誤判為已經存在。這個概率的大小與seeds的數量、申請的內存大小、去重對象的數量有關。下面有一張表，m表示內存大?。ǘ嗌賯€位），n表示去重對象的數量，k表示seed的個數。例如我代碼中申請了256M，即1 31（m=2^31，約21.5億），seed設置了7個?？磌=7那一列，當漏失率為8.56e-05時，m/n值為23。所以n = 21.5/23 = 0.93(億），表示漏失概率為8.56e-05時，256M內存可滿足0.93億條字符串的去重。同理當漏失率為0.000112時，256M內存可滿足0.98億條字符串的去重。

基于Redis的Bloomfilter去重，其實就是利用了Redis的String數據結構，但Redis一個String最大只能512M，所以如果去重的數據量大，需要申請多個去重塊（代碼中blockNum即表示去重塊的數量）。

代碼中使用了MD5加密壓縮，將字符串壓縮到了32個字符（也可用hashlib.sha1()壓縮成40個字符）。它有兩個作用，一是Bloomfilter對一個很長的字符串哈希映射的時候會出錯，經常誤判為已存在，壓縮后就不再有這個問題；二是壓縮后的字符為 0~f 共16中可能，我截取了前兩個字符，再根據blockNum將字符串指定到不同的去重塊進行去重。

基于Redis的Bloomfilter去重，既用上了Bloomfilter的海量去重能力，又用上了Redis的可持久化能力，基于Redis也方便分布式機器的去重。在使用的過程中，要預算好待去重的數據量，則根據上面的表，適當地調整seed的數量和blockNum數量（seed越少肯定去重速度越快，但漏失率越大）。

以上就是在爬蟲的過程中如何使用Redis的Bloomfilter去重的詳細內容，PHP教程

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。