网络爬虫之网页URL去重的5种方法详解

ゞ浴缸里的玫瑰 2023-06-07 05:50 12阅读 0赞

对网络爬虫有一定了解的小伙伴们应该都知道，网络爬虫在爬取信息的时候，为了避免爬虫爬到重复数据、爬虫陷入死循环等问题，我们就需要对URL去重。

**目录**

1、什么是URL去重？

2、为什么要进行URL去重？

2.1、先了解爬虫的基本框架：

2.2、URL为什么会重复，爬虫又为什么会陷入死循环？

3、URL去重的5种方式

3.1、列表

3.2、set集合

3.3、set+md5

3.4、bitmap（位图）

3.5、boomfilter(布隆过滤器)

--------------------

# 1、什么是URL去重？ #

字面意思，去除相同的URL，使得爬虫在爬取过程中尽可能少的爬取重复数据。

# 2、为什么要进行URL去重？ #

反过来说，就是不对URL进行去重，会产生那些问题呢？

*  1、数据重复爬取
 *  2、爬虫陷入死循环
 *  3、爬取效率低下
 *  .....

上面的问题是怎么产生的呢？

首先，我们要明确一点，URL去重是应用于[网络爬虫][Link 1]（不知道什么是网络爬虫自己度娘一下）的。

## 2.1、先了解爬虫的基本框架： ##

**单机版** (这里的单机版指的是一台机器)：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyNTk3MA_size_16_color_FFFFFF_t_70][]

单机版中URL去重体现在： 爬取每一个页面前，先看看以前是否已经爬取过这个页面，如果没有爬取过就爬取，否则直接跳过。

**分布式**：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyNTk3MA_size_16_color_FFFFFF_t_70 1][]

分布式爬虫中URL去重体现在：维护一个不重复的请求队列。

## 2.2、URL为什么会重复，爬虫又为什么会陷入死循环？ ##

这里以3个url为例：一个页面中会包括多个超链接，而所有的超链接都是我们可能要爬取的目标。

我们假设url1中有url2的超链接，url2有url3的超链接，url3又有url1的超链接，那么这三个页面就可以构成下面的关系。

![20191013141300237.png][]

相信聪明的你已经看出了端倪，如果再多几个页面，那么这些页面就形成了一个网（有回路），这是网络爬虫不对url去重而会陷入死循环的原因。

**所以，要想编写出功能强大的网络爬虫，url去重是必不可少的。**

# 3、URL去重的5种方式 #

## 3.1、列表 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyNTk3MA_size_16_color_FFFFFF_t_70 2][]

列表优点：简单易操作

缺点：每次添加URL到列表之前，都要先查询一下是否已存在，非常耗费时间和内存空间。

## 3.2、set集合 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyNTk3MA_size_16_color_FFFFFF_t_70 3][]

集合优点：对比list来说，省去了过多的查询，节省了一些时间和内存空间

缺点：耗费内存空间较大，如果有一亿条URL，一个URL50字符：

100000000 \* 50字符 \* 2byte / 1024 / 1024 / 1024 约= 9.3GB

## 3.3、set+md5 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyNTk3MA_size_16_color_FFFFFF_t_70 4][]

优点：对比单纯使用set来说，md5加密方式大大缩小了占用内存空间

缺点：耗费内存空间还是很大，如果有一亿条URL，一个URL16字节：

100000000 \* 16byte / 1024 / 1024 / 1024 约= 1.4GB

## 3.4、bitmap（位图） ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyNTk3MA_size_16_color_FFFFFF_t_70 5][]

优点：对比使用set+md5来说，位图的方式将空间占用缩小到了极限。如果有一亿条URL，一个URL1位：  
              100000000 / 8bit / 1024 / 1024 / 1024 约= 12M

缺点：产生哈希冲突的可能性很大。

## 3.5、boomfilter(布隆过滤器) ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyNTk3MA_size_16_color_FFFFFF_t_70 6][]

优点：对比使用bitmap来说，BloomFilter降低了的哈希冲突的出现率。

缺点：对比bitmap方式来说，BloomFilter较多的耗费内存空间，有一定的误识别率和删除困难。

不存在漏报（False Negative），即某个元素在某个集合中，肯定能报出来。  
             可能存在误报（False Positive），即某个元素不在某个集合中，可能也被爆出来。

总结一下：

1、list : 简单易操作，耗费内存空间多，耗费资源多

2、set：比list耗费资源少

3、set+md5：比set耗费内存空间少（scrapy-redis中使用的就是类似这种的）

4、bitmap： 耗费内存空间最少，产生hash冲突的概率极大。

5、boomfilter: 耗费内存空间比bitmap多一点，产生hash冲突的概率比bitmap小一些，但是可能存在误报，而且删除困难。

最后多说一点：去重是一种思想，去重并不是只能用在url上，还可以用在任何东西上。比如说：爬取100万首音乐，就可以用去重来保证爬取到的音乐的内容不重复。

[Link 1]: https://baike.baidu.com/item/%E7%BD%91%E7%BB%9C%E7%88%AC%E8%99%AB/5162711?fr=aladdin
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyNTk3MA_size_16_color_FFFFFF_t_70]: /images/20230601/aed793163dab45089b4655aac9c95dda.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyNTk3MA_size_16_color_FFFFFF_t_70 1]: /images/20230601/452eacc054f64be4bbaabd7c7b920d6d.png
[20191013141300237.png]: /images/20230601/810405a90058440d865b98cc1b72e92f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyNTk3MA_size_16_color_FFFFFF_t_70 2]: /images/20230601/c8ab7fedbeb4418c8cca78f9c9106a12.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyNTk3MA_size_16_color_FFFFFF_t_70 3]: /images/20230601/19f867eb206b4b6c95975e1bd7dbf7e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyNTk3MA_size_16_color_FFFFFF_t_70 4]: /images/20230601/4f210f2d7aff4bfeac6c30415f85de3f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyNTk3MA_size_16_color_FFFFFF_t_70 5]: /images/20230601/1d05d2719fb44e0dba00117f56d0efbc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyNTk3MA_size_16_color_FFFFFF_t_70 6]: /images/20230601/289df470e2b24acf8ed8c886d0dbe7a4.png