第三百五十八節(jié)帖鸦，Python分布式爬蟲打造搜索引擎Scrapy精講—將bloomfilter(布隆過濾器)集成到scrapy-redis中，判斷URL是否重復(fù)
布隆過濾器(Bloom Filter)詳解
基本概念
如果想判斷一個(gè)元素是不是在一個(gè)集合里，一般想到的是將所有元素保存起來阿纤，然后通過比較確定。鏈表，樹等等數(shù)據(jù)結(jié)構(gòu)都是這種思路. 但是隨著集合中元素的增加喉恋，我們需要的存儲(chǔ)空間越來越大，檢索速度也越來越慢母廷。不過世界上還有一種叫作散列表（又叫哈希表轻黑，Hash table）的數(shù)據(jù)結(jié)構(gòu)。它可以通過一個(gè)Hash函數(shù)將一個(gè)元素映射成一個(gè)位陣列（Bit Array）中的一個(gè)點(diǎn)琴昆。這樣一來氓鄙，我們只要看看這個(gè)點(diǎn)是不是 1 就知道可以集合中有沒有它了。這就是布隆過濾器的基本思想椎咧。
Hash面臨的問題就是沖突玖详。假設(shè) Hash 函數(shù)是良好的，如果我們的位陣列長度為 m 個(gè)點(diǎn)勤讽，那么如果我們想將沖突率降低到例如 1%, 這個(gè)散列表就只能容納 m/100 個(gè)元素蟋座。顯然這就不叫空間有效了（Space-efficient）。解決方法也簡單脚牍，就是使用多個(gè) Hash向臀，如果它們有一個(gè)說元素不在集合中，那肯定就不在诸狭。如果它們都說在券膀，雖然也有一定可能性它們?cè)谡f謊君纫，不過直覺上判斷這種事情的概率是比較低的。
優(yōu)點(diǎn)
相比于其它的數(shù)據(jù)結(jié)構(gòu)芹彬，布隆過濾器在空間和時(shí)間方面都有巨大的優(yōu)勢(shì)蓄髓。布隆過濾器存儲(chǔ)空間和插入/查詢時(shí)間都是常數(shù)。另外, Hash 函數(shù)相互之間沒有關(guān)系舒帮，方便由硬件并行實(shí)現(xiàn)会喝。布隆過濾器不需要存儲(chǔ)元素本身，在某些對(duì)保密要求非常嚴(yán)格的場(chǎng)合有優(yōu)勢(shì)玩郊。
布隆過濾器可以表示全集肢执，其它任何數(shù)據(jù)結(jié)構(gòu)都不能；
k 和 m 相同译红，使用同一組 Hash 函數(shù)的兩個(gè)布隆過濾器的交并差運(yùn)算可以使用位操作進(jìn)行预茄。
缺點(diǎn)
但是布隆過濾器的缺點(diǎn)和優(yōu)點(diǎn)一樣明顯。誤算率（False Positive）是其中之一侦厚。隨著存入的元素?cái)?shù)量增加耻陕，誤算率隨之增加。但是如果元素?cái)?shù)量太少假夺，則使用散列表足矣淮蜈。
另外，一般情況下不能從布隆過濾器中刪除元素. 我們很容易想到把位列陣變成整數(shù)數(shù)組已卷，每插入一個(gè)元素相應(yīng)的計(jì)數(shù)器加1, 這樣刪除元素時(shí)將計(jì)數(shù)器減掉就可以了梧田。然而要保證安全的刪除元素并非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器里面. 這一點(diǎn)單憑這個(gè)過濾器是無法保證的侧蘸。另外計(jì)數(shù)器回繞也會(huì)造成問題裁眯。
python 基于redis實(shí)現(xiàn)的bloomfilter(布隆過濾器)，BloomFilter_imooc
BloomFilter_imooc下載
下載地址：https://github.com/liyaopinner/BloomFilter_imooc
依賴關(guān)系：
python 基于redis實(shí)現(xiàn)的bloomfilter
依賴mmh3
安裝依賴包：
pip install mmh3
1讳癌、安裝好BloomFilter_imooc所需要的依賴
2穿稳、將下載的BloomFilter_imooc包解壓后，將里面的py_bloomfilter.py文件復(fù)制到scrapy工程目錄
py_bloomfilter.py(布隆過濾器)源碼
import mmh3
import redis
import math
import time
class PyBloomFilter():
? ? #內(nèi)置100個(gè)隨機(jī)種子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ù)先估計(jì)要去重的數(shù)量
#error_rate表示錯(cuò)誤率
#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))? #需要的總bi位數(shù)????
????????self.k = math.ceil(math.log1p(2)*self.m/capacity)? ? #需要最少的hash次數(shù)
????????self.mem = math.ceil(self.m/8/1024/1024)? ? ? ? ?#需要的多少M(fèi)內(nèi)存
????????self.blocknum = math.ceil(self.mem/512)? ? ? ? ? ? ?#需要多少個(gè)512M的內(nèi)存塊,value的第一個(gè)字符必須是ascii碼晌坤，所有最多有256個(gè)內(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 = mmh3.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)? ??
將py_bloomfilter.py(布隆過濾器)集成到scrapy-redis中的dupefilter.py去重器中逢艘，使其抓取過的URL不添加到下載器，沒抓取過的URL添加到下載器
scrapy-redis中的dupefilter.py去重器修改
爬蟲文件
啟動(dòng)爬蟲scrapy crawl jobbole
cd 到redis安裝目錄執(zhí)行命令：redis-cli -h 127.0.0.1 -p 6379連接redis客戶端
連接redis客戶端后執(zhí)行命令：lpush jobbole:start_urls http://www.luyin.org向redis添加一個(gè)爬蟲起始url
開始爬取
redis狀態(tài)說明：
