在爬蟲的過程中如何使用Redis的Bloomfilter去重

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

前言：

「去重」是日常工作中會常用到的技能，在爬蟲領域更是常用，而且規模一般都比較大。去重需要考慮兩個點：去重的資料量、去重速度。為了保持較快的去重速度，一般選擇在記憶體中去重。

• 資料量不大時，可以直接放在記憶體裡面去重，例如python可以使用set()去重。

• 當去重資料需要持久化時可以使用redis的set資料結構。

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

• 當資料量達到億（甚至十億、百億）數量級時，記憶體有限，必須用「位」來去重，才能滿足需求。 Bloomfilter就是將去重物件對應到幾個記憶體“位元”，透過幾個位元的 0/1值來判斷一個物件是否已經存在。

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

程式碼：

# encoding=utf-8import redisfrom hashlib import md5class 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__ == &#39;__main__&#39;:""" 第一次运行时会显示 not exists!，之后再运行会显示 exists! """
    bf = BloomFilter()    if bf.isContains(&#39;http://www.baidu.com&#39;):   # 判断字符串是否存在
        print &#39;exists!&#39;
    else:        print &#39;not exists!&#39;
        bf.insert(&#39;http://www.baidu.com&#39;)

#說明：

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

2. 要提醒的是Bloomfilter演算法會有漏失機率，即不存在的字串有一定機率被誤判為已經存在。這個機率的大小與seeds的數量、申請的記憶體大小、去重物件的數量有關。下面有一張表，m表示記憶體大小（多少個位元），n表示去重物件的數量，k表示seed的個數。例如我代碼中申請了256M，也就是1

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

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

總結：

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

以上是在爬蟲的過程中如何使用Redis的Bloomfilter去重的詳細內容。更多資訊請關注PHP中文網其他相關文章！