Scrapy 爬虫的去重策略：使用 Bloom Filter 进行 URL 去重

2023-04-17 00:00:00 scrapy 爬虫策略

Bloom Filter 是一种空间效率非常高的随机数据结构，它利用位数组实现。 Bloom Filter 可以用于判断一个元素是否在一个集合中。使用 Bloom Filter 进行 URL 去重的原理是将抓取到的 URL 对应的哈希值存入 Bloom Filter 中，当再次遇到哈希值相同的 URL 时，直接判定为重复的 URL。

具体实现可以使用 Python 的第三方库 pybloomfiltermmap，代码示例如下：

import hashlib
from pybloomfilter import BloomFilter

class FilterURLs(object):

    def __init__(self, capacity):
        self.capacity = capacity
        self.filter = BloomFilter(capacity, error_rate=0.001)

    def is_visited(self, url):
        md5 = hashlib.md5()
        md5.update(url.encode('utf-8'))
        md5_digest = md5.hexdigest()
        if md5_digest in self.filter:
            return True
        else:
            self.filter.add(md5_digest)
            return False

if __name__ == '__main__':
    filter_urls = FilterURLs(1000000)
    urls = ['http://pidancode.com', 'https://pidancode.com', 'http://www.pidancode.com', 'http://www.pidancode.com/page1', 'http://pidancode.com']
    for url in urls:
        if filter_urls.is_visited(url):
            print(url, 'is visited')
        else:
            print(url, 'is not visited')

上述代码中，FilterURLs 类初始化 Bloom Filter 容量为 1000000， error_rate=0.001 表示错误率为千分之一。is_visited 方法接收 URL 作为参数，通过 hashlib.md5() 方法将 URL 转为 MD5 哈希码，然后检查该哈希码是否在 Bloom Filter 中。如果已经存在，则表明该 URL 已经被访问过，返回 True；否则，将该哈希码添加到 Bloom Filter 中，并返回 False。

代码的输出结果如下：

http://pidancode.com is not visited
https://pidancode.com is not visited
http://www.pidancode.com is not visited
http://www.pidancode.com/page1 is not visited
http://pidancode.com is visited

可以看出，重复的 URL http://pidancode.com 在第二次被检测时被判定为已经访问过。

相关文章