快速入门网络爬虫系列 Chapter04 | URL管理

网络爬虫的过程：

1. 爬虫通过本地或远程DNS，获取URL对应的IP地址
2. 根据获取的IP地址与访问内容封装HTTP请求
3. 爬虫打出HTTP请求
4. 服务器接收信息，根据HTTP内容寻找web资源
5. 服务器创建HTTP请求并封装
6. 服务器将HTTP响应返回到爬虫
7. 爬虫解析，保存

什么是URL 统一资源定位符是对可以从互联网得到的资源的位置和访问方法的一种简介的表示，是互联网上标准资源的地址。互联网上的每一个文件都有一个唯一的URL，它包含的信息指出文件的位置以及浏览器应该怎样处理它。

一、URL去重

1、URL去重的重要性

• 网络爬虫爬取重复的URL链接，会下载相同网页的内容，造成计算资源的消耗，给服务器带来不必要的负担
• 解决重复下载的问题，可以提高爬虫效率，减少不必要的资源消耗
• 深度优先(DFS)和广度优先(BFS)的抓取策略，遇到的网页链接重复是因为网页的链接形成一个闭环
• 无论是BFS还是DFS都不可避免地反复遍历这个环中的URL，从而造成无限循环
• 为了避免无限循环，更需要取出重复的URL

所有的URL去重都是在内存上进行的——>可提速

2、Hash去重

• Hash，也称为哈希，散列，是把任意长度的输入，通过给定的函数，转换为长度固定的输出
• Hash的实质是一种压缩映射，散列值的空间通常远小于输入的空间
• 不需要遍历所有的元素，提高了查找效率

举个例子：

• 每个散列值对应一个桶，同一个桶存放的是所有散列值相同的元素
• 88经过hash函数之后，得到一个散列值8，所以就把88放在8号桶中

1

Hash算法是检测一个元素是否存在的高效算法。对于一个输入，我们只需要计算其散列值，并在这个散列值对应的桶中查找元素是否存在就行了，不需要遍历所有所有元素。如在上图中，要检测数字88是否存在，只需要检测88号桶中是否存在数字88即可。

2.1、常用的构造Hash函数的方法

• 直接寻址法：取关键字或关键字的某个线性函数值为散列地址(并不常用)
• 数字分析法：抽取关键字中的一部分来计算存储位置(适用于关键词较长的情况)
• 平方取中法：关键字先平方，截取中间X位作为存储位置(适用于不知道关键字的分布)
• 折叠法：拆分关键字
• 随机数法：使用随机数作为存储位置
• 除留余数法：适用余数作为存储位置

2.2、Hash去重所遇到的问题及解决方法

问题:

• 通常hash函数映射得到的散列值，并不能保证唯一性
• 不同的输入可能会得到相同的散列值，这种现象称为Hash碰撞

解决方法：

• 开放寻址法
• 拉链法

1、开放寻址法

开放寻址：所有的元素经过Hash映射后都存放在散列表中

• 当新的元素进入散列表中，检查散列表的各项，直到发现有“空”的位置，将该元素放入为止 eg：学校的厕所门，有人门是关着的，没人门是能拉开的，就这样慢慢能找到“空”的位置
• 常用的开放寻址方法有以下三种： ①线性探测：h(k,i) = (h’(k)+i) mod m, 0 ≤ i ≤ m-1 ②二次探测：h(k,i) = (h’(k)+i*i)% m, 0 ≤ i ≤ m-1 ③双重散列：h(k,i) = (h1(k)+ih2(k)) mod m, 0 ≤ i ≤ m-1
• 开发寻址法通过占用散列表的其他空闲位置，来解决Hash碰撞的问题
• 这样做会导致后续加入的元素发生Hash碰撞的风险升高
• 对于采用开放寻址法的Hash散列表来说，需要控制它的装载因子
• 装载因子是哈希表保存的元素数量和哈希表容量的比。采用开放寻址的Hash散列表的装载因子不大于0.5

2、拉链法

拉链法：将Hash散列表看作一个链表数组。数组中的位置要么为空，要么指向散列到该位置的链表

• 链表法把元素添加到链表中来解决Hash碰撞。具有相同散列值的元素会插入相对应的链表中
• 拉链法的代价不会超过向链表中添加元素，也无需执行再散列

拉链法的实现过程：

2

拉链法的优点 优点：

• 解决了Hash表堆叠的现象，减少了平均查询的长度
• 在单链表中执行更改这样的操作相比于开放寻址法更为简单，我们只需要把删除的元素的地址前后关联一下即可

两者对比：

• 数据量比较小的时候开放寻址法是不需要重新开辟空间的，当数据量比较大的时候，开放寻址法要不停的按照装填因子成倍的申请新的空间，会造成存储空间过大。

3、使用Hash来对URL进行去重

• 首先要设置一个Python的数据类型—集合，来保存已经爬取过的URL

import requests,re
count = 3
r = re.compile(r'href=[\'"]?(http[^\'">]+)')
seed = 'http://httpbin.org/'
queue = [seed]
used = set()   # 设置一个集合，保存已经抓取过的URL
storage = {}

3.1、为什么要用集合

Python语言的set：

• 集合对象是一组无序排列的可哈希的值
• 集合本身无序，不能创建索引，执行切片操作
• 集合内元素不重复
• 集合元素为不可变对象

3.2、具体实现的逻辑

• 用深度(或宽度)优先递归地搜寻新地URL
• 如果新发现的URL包含在这个集合中就舍弃
• 否则加入到未爬取队列中

eg：

while len(queue) > 0 and count > 0 :
    try:
        url = queue.pop(0)
        html = requests.get(url).text
        storage[url] = html  #将已经抓取过的URL存入used集合中
        used.add(url)
        new_urls = r.findall(html)   # 将新发行未抓取的URL添加到queue中
        for new_url in new_urls:
            if new_url not in used and new_url not in queue:
                queue.append(new_url)
        count -= 1
    except Exception as e :
        print(url)
        print(e)

3.3、统计URL管理器中的URL数量

from collections import Counter
url_count = Counter(queue)
for url,count in url_count.most_common(10):
    print(url,count)

所得结果如下图：

3

3.4、略加修改的代码：

import requests,re
import time
from collections import Counter
count = 3
recount = 0
allcount = 1
r = re.compile(r'href=[\'"]?(http[^\'">]+)')
seed = 'http://httpbin.org/'
queue = [seed]
used = set()   # 设置一个集合，保存已经抓取过的URL
storage = {}

while len(queue) > 0 and count > 0 :
    try:
        url = queue.pop(0)
        html = requests.get(url).text
        storage[url] = html  #将已经抓取过的URL存入used集合中
        used.add(url)
        new_urls = r.findall(html)   # 将新发行未抓取的URL添加到queue中
        for new_url in new_urls:
            allcount += 1
            if new_url not in used and new_url not in queue:
                queue.append(new_url)
            else:
                print("重复："+url)
                recount += 1
        count -= 1
    except Exception as e :
        print(url)
        print(e)

print("重复网站："+str(recount))
print("总网站："+str(allcount))
url_count = Counter(queue)
for url,count in url_count.most_common(10):
    print(url,count)

4

去重的重要性： 因为网站结构的关系，它会进行重复的引用。

• 上面的代码可以防止无穷循环，但是比较多时就会体现出劣势
• 如果URL过多，那么占用的内存空间也会很大

总结：

• 优点：速度快
• 缺点：占用大量内存空间

2、URL压缩

• URL压缩基于MD5算法对URL进行加密压缩，生成散列值，来判断URL的唯一值
• MD5是一种基于Hash的加密算法，它可以压缩URL生成： ①一个压缩的128位整数 ②一个Hash物理地址
• 使用MD5算法进行Hash映射，发生Hash碰撞的几率小，为网络爬虫抓取所使用

使用第三方库hashlib来实现MD5映射算法

import hashlib
src1 = 'https://baidu.com'
m1 = hashlib.md5()
m1.update(src1.encode('utf-8'))
print(m1.hexdigest())

src2 = 'https://baidu.com'
m2 = hashlib.md5()
m2.update(src2.encode('utf-8'))
print(m2.hexdigest())

5

三、Bloom Filter

Bloom Filter是在1970年代由Bloom出的一种多哈希函数映射的快速查找算法

它是一种空间效率高的随机数据结构

• 使用位数组表示一个集合
• 判断一个元素是否属于这个集合

Bloom Filter的基本思路是：通过多个不同的Hash函数来解决“冲突”

Bloom Filter主要包含以下两个部分：

• 1个比特数组：长度为m，并初始化为0
• k个hash函数：进行URL哈希，哈希值范围[0,m-1]

Bloom Filter的任务是，判断URL是否已经抓取过

• URL哈希之后，得到k个范围在[0,m-1]的值，然后判断这k个位置上是否都是1，如果都是1，就认为这个URL已经抓取过，否则没有抓取

在下图中，有三个hash函数。假设x,y,z是已经抓取过的URL

6

w是要判断的URL：

• 可以看到，w经过hash之后三个对应的位置上有一个不是1，我们可以肯定这个URL没有被抓取过

3.1、Bloom Filter的缺点

Bloom Filter的查询时间和空间效率虽高，但是有以下缺点：

• Bloom Filter集合中的元素无法删除
• 如何确定位数组的大小以及hash函数的个数
• Bloom Filter会出现错误判断，无法达到零错误

3.2、Bloom Filter通常的应用场景

• 设置黑名单
• 过滤垃圾短信
• 检测重复URL

Python中有很多Bloom Filter的开源实现，我们这里选用pybloom工具包

pybloom的主要类和函数有：

• BloomFilter(capacity,error_rate)
• ScalableBloomFilter(initial_capacity,error_rate,mode)

1、举例

创建一个Bloom Filter：

• 容量为1000，误判率为0.001，pybloom自动计算需要多少个hash函数，需要多少比特的数组

import pybloom_live
f = pybloom_live.BloomFilter(capacity = 1000,error_rate = 0.001)
[f.add(x) for x in range(10)]

7

8

9

10

四、URL重定向

重定向(redirect)允许一个网页在不同的域名下显示

重定向有两种形式：

• Dispatch：服务器端重定向，网页在加载之前先改变了URL
• Redirect：客户端重定向，有时你会在网页上看到“5秒之后自动跳转…”之类的消息，表示在跳转到新URL之前网页需要加载内容

1、客户端重定向

客户端重定向是在服务器将页面内容发送到浏览器之前，由浏览器执行JavaScript完成的页面跳转，而不是服务器完成的跳转

当浏览器访问页面的时候，有时很难区分这两种重定向：

• 由于客户端重定向执行很快，加载页面时你甚至感觉不到任何延迟，所以会让你觉得这个重定向就是一个服务器端重定向

客户端重定向，也成为HTTP重定向，是HTTP协议规定的一种机制。

重定向的机制如下图：

11

2、服务器重定向

服务器重定向是在处理客户端提交的request过程中，服务器将request先后委托多个处理单元接替进行处理的过程

12

3、差别

• 在网络爬虫进行数据采集的时候，这两种重定向的差异是很明显的
• 根据具体情况，服务器端重定向一般可以通过Python的urllib库解决，不需要使用Selenium
• 客户端重定向不能像服务器重定向一样，除非使用工具执行JavaScript

4、客户端重定向的类型

重定向的类型有很多种，301和302是最常见的两种

• 301 Moved Permancently ：永久重定向(稳定，静态化)
• 302 Moved Temporarily：临时重定向(慎用)

5、301重定向的必要性

当网页A用301重定向转到网页B时，搜索殷勤肯定网页A永久的改变位置，或者说实际上不存在，搜索引擎就会把网页B当作唯一有效目标

这样做的好处：

• 没有网址规范化问题
• 网页A的PageRank级别会传到网页B
• 不会因为域名更换而不收录

五、简单小结

1、URL去重的方法

• Hash去重方法速度快，实现简单，但无法应对大数据量
• 使用Bloom Filter来对URL进行去重

2、URL重定向

• Dispatch
• Redirect

3、

13