爬虫扩展——网站爬取 URL 去重方法

r囧r小猫 2023-09-29 12:22 2阅读 0赞

**目录**

前言

一. 为什么要URL 去重

二. URL 去重的常用方法

总结

爬虫文章专栏

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

## 前言 ##

>  上一篇文章我们讨论了网站爬取的两种策略——深度优先和广度优先。我们无论采取这两个策略的哪一个，都不可避免地会碰到一个相对比较严重的问题，那就是URL 去重问题。

## 一. 为什么要URL 去重 ##

*  URL 重复问题

>  无论是什么网站，都会存在大量的 URL 重复的问题，如果不处理好这个问题，最严重的情况是可能会陷入死循环中。因为大多数网站的第一个 URL 都是链接到首页的，如果采用深度优先策略，而不对 URL 进行去重，就会陷入死循环中。

*  内存不足问题

>  那就是虽然能够向整个网站的所有 URL 发起请求，但是将会耗费巨大的内存，甚至还没等爬取完整个网站的 URL，内存就已经不够用了。

>  所以 URL 去重是我们在爬取大量数据的时候不可避免要碰见的问题，接下来，我们来讨论下几种 URL 去重的常用方法。

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

## 二. URL 去重的常用方法 ##

*   **数据库查重**

>  将访问过的 URL 保存到数据库中，当爬取到一个新的 URL 时，就去数据库中查询是否这个 URL 是否已经爬取过；
> 
> **优点：**应用起来最简单；
> 
> **缺点：**效率非常低、耗内存；

*  **set（集合）查重**

>  将访问过的 URL 保存在 set（集合）中，那么只需要 O(1)的时间复杂度就能查询到 URL；
> 
> **优点：**效率很高，查询快，应用起来简单；
> 
> **缺点：**耗内存；

> **举例：**就假设一个网站有 1 亿个 URL，每个 URL 假设有 50 个字符，按照 python 的编码格式 Unicode，按每个字符 2 个字节算，那么需要多大的内存来保存这些 URL 呢？100000000 \* 2 byte \* 50 个字符 / 1024 / 1024 / 1024 ≈ 9G ，那么 2 亿条就需要 18G 的内存，3 亿条就需要 27G 的内存，这是多么恐怖的内存数字。

*  **哈希后保存到set中**

>  URL 经过 md5 等方法哈希之后保存到 set 中（Scrapy 框架采取的 URL 去重方法就是类似这种方法） 
> 
> **优点：**效率很高，查询快 
> 
> **缺点：**耗内存（但相对第二种方法，已经缩小了几倍的内存）

> **举例：**md5 编码能够将一个字符缩减到固定的长度，md5 的一般编码长度是128bit，那么就是 16byte，还是按照 1 亿个 URL 计算，需要耗费多大的内存来保存这些 URL 呢？ 
> 
>  100000000 \* 16 byte / 1024 / 1024 / 1024 ≈ 1.5G

**代码举例：**

# 实现功能：将 URL 通过 md5 哈希之后，得到一个固定长度的字符串
    import hashlib
    def get_md5(url):
        if isinstance(url, str):
            url = url.encode('utf-8')
            m = hashlib.md5(url)
        return m.digest()
    result = get_md5('https://www.baidu.com')
    print(result)
    print(len(result))

*  **bitmap 方法**

>  用 bitmap 方法，将访问过的 URL 通过 hash 函数映射到某一位上，也就是某一个 bit 上；
> 
> **优点：**进一步压缩了保存 URL 需耗费的内存；
> 
> **缺点：**哈希冲突很高，不太适用；

> **举例：**一个 byte 有 8 个 bit，也就是 8 个位，bitmap 就是将一个 URL 通过 hash 函 数，将它映射到 8 个位上的某一个位上，这样就进一步压缩了保存 URL 需耗费的内存，但极有可能将多个 URL 映射到了同一个位上，也就造成了哈希冲突，造成哈希冲突后，就需要向下寻址，有兴趣的童鞋可以网上搜索哈希冲突的解决方法。

*  **bloomfilter 方法**

>  bloomfilter 方法对 bitmap 进行改进，多重 hash 函数降低哈希冲突；
> 
> 优点：既保留了 bitmap 的内存压缩优点，又良好解决了哈希冲突；
> 
> 缺点：难以理解；

> **举例：**还是按照 1 亿个 URL 来计算，采用这种方法需要占用多大的内存呢？ 
> 
>  100000000 \* 1 bit / 8 / 1024 / 1024/ 1024 ≈ 12M 
> 
>  当然这只是理想状况，尽管 bloomfilter 对 bitmap 进行了优化，但不可避免地还是会有哈希冲突的发生，导致内存是 12M 只是一种理想状况下的数字，实际上肯定不止12M，但无论如何，和之前的几种方法比较，内存还是成倍地进行了压缩；

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

## 总结 ##

本文为大家介绍网站爬取 URL 去重方法，希望对大家有帮助~~

欢迎大家留言一起讨论问题~~~

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

**注：本文是参考风变编程课程资料（已经授权）及部分百度资料整理所得，系博主个人整理知识的文章，如有侵权，请联系博主，感谢~**

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

## 爬虫文章专栏 ##

[https://blog.csdn.net/weixin\_53919192/category\_11748211.html![icon-default.png?t=M3K6][icon-default.png_t_M3K6]https://blog.csdn.net/weixin\_53919192/category\_11748211.html][https_blog.csdn.net_weixin_53919192_category_11748211.html_icon-default.png_t_M3K6_icon-default.png_t_M3K6_https_blog.csdn.net_weixin_53919192_category_11748211.html]

[icon-default.png_t_M3K6]: https://csdnimg.cn/release/blog_editor_html/release2.1.0/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=M3K6
[https_blog.csdn.net_weixin_53919192_category_11748211.html_icon-default.png_t_M3K6_icon-default.png_t_M3K6_https_blog.csdn.net_weixin_53919192_category_11748211.html]: https://blog.csdn.net/weixin_53919192/category_11748211.html