爬虫之URL去重

URL去重

我们在协爬虫时为什么需要进行URL去重？

在爬虫启动工作的过程中，我们不希望同一个url地址被多次请求，因为重复请求不仅会浪费CPU，还会降低爬虫的效率，加大对方服务器的压力。而想要控制这种重复请求的问题，就要考虑请求所依据的url，只要能够控制待下载的URL不重复，基本可以解决同一个网页重复请求的问题。
对于已经抓取过的url，进行持久化，并且在启动的时候加载进入去重队列，是一个比较强的需求。它主要应对爬虫故障重跑，不需要重新请求所有链接

URL去重及策略简介

从表面上看，url去重策略就是消除url重复的方法，常见的url去重策略有五种，如下：

# 1.将访问过的ur保存到数据库中
# 2.将访问过的ur保存到set(集合)中,只需要o(1)的代价就可以查询url
#       10000000*2byte*50个字符/1024/1024/1024=9G
# 3.url经过md5等方法哈希后保存到set（或者Redis中）中
# 4. bloomfilter方法对 bitmap进行改进,多重hash函数降低冲突

方式一：将访问过的ur保存到数据库中

实现起来最简单，但效率最低。
其核心思想是，把页面上爬取到的每个url存储到数据库，为了避免重复，每次存储前都要遍历查询数据库中当前url是否存在（即是否已经爬取过了）,若存在，则不保存，否则，保存当前url,继续保存下一条，直至结束。

方式二：将访问过的ur保存到set内存中

实现简单，原理和方式一类似，使用这种方式存取方便，基本不用查询，但是如果url过多，则会占用极大的内存，浪费空间。

# 简单计算：假设有1亿条url,每个url平均长度为50个字符，python里unicode编码，每个字符16位，占2
# 个字节（byte）
# 计算式：10^8 x 50个字符 x 2个byte / 1024 / 1024 / 1024 = 9G
#                                    B      M      G
如果是2亿个url,那么占用内存将达18G，也不是特别方便，适合小型爬虫。

方式三.url经过md5等方法哈希后保存到set（或者Redis中）中（实现方法如下）

简单计算：一个url经MD5转换，变成一个128bit(位)的字符串，占16byte(字节)，方法二中一个url保守估
计占50个字符 x 2 = 100byte(字节)，
计算式： 这样一比较，MD5的空间节省率为：（100-16）/100 = 84%（相比于方法二）
(Scrapy框架url去重就是采用的类似方法)

    def request_fingerprint(self, url):
        """Returns a fingerprint for a given url
        Parameters
        ----------
        url : 待请求的url地址
        Returns： str
        """
        #根据url生成指纹
        print('未加密之前:',url)
        md5_obj = hashlib.md5()
        # 进行MD5加密前必须 encode(编码)，python里默认是unicode编码，必须转换成utf-8
        # 否则报错：TypeError: Unicode-objects must be encoded before hashing
        md5_obj.update(url.encode(encoding='utf-8'))
        md5_url = md5_obj.hexdigest()
        print('MD5加密后:',md5_url)
        return md5_url

方式四： bloomfilter方法对 bitmap进行改进,多重hash函数降低冲突

原理概述

布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个
点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点
有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。

爬虫之URL去重

优缺点

布隆过滤器可以用于检索一个元素是否在一个集合中。
优点是空间效率和查询时间都远远超过一般的算法。
缺点是有一定的误识别率(随着数据的变大，误识概率变大)和不允许删除。

# 设置散列函数的个数
BLOOMFILTER_HASH_NUMBER = 6
# 布隆过滤器设置bit参数，默认30，占用128M空间，去重量在1亿左右
此参数决定了位数组的位数，如果BLOOMFILTER_BIT为30，则位数组
位2的30次方，这将暂用Redis 128MB的存储空间，url去重数量在1亿左右，
如果爬取的量在10亿，20亿或则更高，则需要将此参数调高
BLOOMFILTER_BIT = 30

class HashMap(object):
    def __init__(self, m, seed):
        self.m = m
        self.seed = seed
    
    def hash(self, value):
        """
        Hash Algorithm
        :param value: Value
        :return: Hash Value
        """
        ret = 0
        for i in range(len(value)):
            ret += self.seed * ret + ord(value[i])
        return (self.m - 1) & ret


class BloomFilter(object):
    def __init__(self, server, key, bit=BLOOMFILTER_BIT, hash_number=BLOOMFILTER_HASH_NUMBER):
        """
        Initialize BloomFilter
        :param server: Redis Server
        :param key: BloomFilter Key
        :param bit: m = 2 ^ bit
        :param hash_number: the number of hash function
        """
        # default to 1 << 30 = 10,7374,1824 = 2^30 = 128MB, max filter 2^30/hash_number = 1,7895,6970 fingerprints
        self.m = 1 << bit
        self.seeds = range(hash_number)
        self.server = server
        self.key = key
        self.maps = [HashMap(self.m, seed) for seed in self.seeds]
    
    def exists(self, value):
        """
        if value exists
        :param value:
        :return:
        """
        if not value:
            return False
        exist = True
        for map in self.maps:
            offset = map.hash(value)
            exist = exist & self.server.getbit(self.key, offset)
        return exist == 1
    
    def insert(self, value):
        """
        add value to bloom
        :param value:
        :return:
        """
        for f in self.maps:
            offset = f.hash(value)
            self.server.setbit(self.key, offset, 1)

单独使用如下

	client = redis.StrictRedis(host='118.24.255.219',port=6380)
    bl = BloomFilter(client,'bl:url')
    url = 'http://www.wanfangdata.com.cn/details/detaype=conference&id=7363410'
    bl.insert(url)
    result = bl.exists(url)
    print(result)
    url1 = 'http://www.wanfangdata.com.cn/details/detaype=conference&id=73634101'
    result = bl.exists(url1)
    print(result)

为了方便使用我们还可以和scrpay-redis对接，这里不需要重复造*，我们可以直接使用pip3 来安装ScrapyRedisBloomFilter：

Installation

pip3 install scrapy-redis-bloomfilter

Usage

# Ensure use this Scheduler(使用自定义的调度器组件)
SCHEDULER = "scrapy_redis_bloomfilter.scheduler.Scheduler"

# Ensure all spiders share same duplicates filter through redis(使用自定义的去重组件)
DUPEFILTER_CLASS = "scrapy_redis_bloomfilter.dupefilter.RFPDupeFilter"

# Redis URL（设置去重指纹需要保存的redis数据库信息）
REDIS_URL = 'redis://:[email protected]:6379'

# Number of Hash Functions to use, defaults to 6
#设置散列函数的个数
BLOOMFILTER_HASH_NUMBER = 6

# Redis Memory Bit of Bloomfilter Usage, 30 means 2^30 = 128MB, defaults to 30
# 布隆过滤器设置bit参数，默认30，占用128M空间，去重量在1亿左右
此参数决定了位数组的位数，如果BLOOMFILTER_BIT为30，则位数组
位2的30次方，这将暂用Redis 128MB的存储空间，url去重数量在1亿左右，
如果爬取的量在10亿，20亿或则更高，则需要将此参数调高
BLOOMFILTER_BIT = 30

# Persist
#是否支持断点爬取
SCHEDULER_PERSIST = True

其实ScrapyRedisBloomFilter就是在scrapy-redis的基础上将DUPEFILTER去重组件中的去重部分代码判断修改了，如下图所示：
爬虫之URL去重

学习了本小结之后，再也不用担心url的去重了，感谢阅读。