数据结构与算法之美
王争
前 Google 工程师
283752 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

45 | 位图:如何实现网页爬虫中的URL去重功能?

内存消耗节省
访问效率高
通过位运算表示二进制位
适用于大规模判重场景
可能存在误判
多个哈希函数定位数据
位图
需要分治处理
内存消耗大
布隆过滤器
散列表
布隆过滤器在海量图库中的判重功能
快速省内存地排序1亿个整数
Google的Guava工具包
Redis的BitMap
BitSet类
统计UV数
爬虫网页去重
使用数据结构进行记录
记录已爬取的网页链接
爬取链接对应的网页
解析已爬取页面中的网页链接
课后思考
布隆过滤器的实现
布隆过滤器的应用
避免重复爬取的方法
网页爬虫的工作原理
如何实现网页爬虫中的URL去重功能?

该思维导图由 AI 生成,仅供参考

网页爬虫是搜索引擎中的非常重要的系统,负责爬取几十亿、上百亿的网页。爬虫的工作原理是,通过解析已经爬取页面中的网页链接,然后再爬取这些链接对应的网页。而同一个网页链接有可能被包含在多个页面中,这就会导致爬虫在爬取的过程中,重复爬取相同的网页。如果你是一名负责爬虫的工程师,你会如何避免这些重复的爬取呢?
最容易想到的方法就是,我们记录已经爬取的网页链接(也就是 URL),在爬取一个新的网页之前,我们拿它的链接,在已经爬取的网页链接列表中搜索。如果存在,那就说明这个网页已经被爬取过了;如果不存在,那就说明这个网页还没有被爬取过,可以继续去爬取。等爬取到这个网页之后,我们将这个网页的链接添加到已经爬取的网页链接列表了。
思路非常简单,我想你应该很容易就能想到。不过,我们该如何记录已经爬取的网页链接呢?需要用什么样的数据结构呢?

算法解析

关于这个问题,我们可以先回想下,是否可以用我们之前学过的数据结构来解决呢?
这个问题要处理的对象是网页链接,也就是 URL,需要支持的操作有两个,添加一个 URL 和查询一个 URL。除了这两个功能性的要求之外,在非功能性方面,我们还要求这两个操作的执行效率要尽可能高。除此之外,因为我们处理的是上亿的网页链接,内存消耗会非常大,所以在存储效率上,我们要尽可能地高效。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

本文深入探讨了网页爬虫中的URL去重功能及其实现方法。作者首先讨论了使用散列表、红黑树、跳表等数据结构来解决URL去重问题的挑战,但指出了内存消耗和执行效率方面的限制。随后,文章引入了位图和布隆过滤器的概念,详细解释了它们的原理和优势。位图通过数组下标定位数据,访问效率高且内存消耗较小,适用于数字范围不大的情况。而布隆过滤器则通过多个哈希函数定位数据,降低了冲突概率,适用于数字范围较大的情况。布隆过滤器的引入为URL去重问题提供了更为高效的解决方案。文章还指出布隆过滤器的误判特点,以及在存储空间和执行效率方面与散列表的比较,展示了布隆过滤器在爬虫判重问题中的优势。通过本文的阐述,读者能够全面了解URL去重功能的挑战、解决方案以及各种存储结构的优缺点,为实际应用提供了有力的技术支持。文章还提到了布隆过滤器在其他领域的应用,如统计网站UV数等,展示了其广泛的适用性。文章以简洁清晰的语言,深入浅出地介绍了这些存储结构的原理和应用,为读者快速了解URL去重功能提供了有益的参考。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(98)

  • 最新
  • 精选
  • 越过山丘
    第一题,数字重复了,有什么好方法处理吗

    作者回复: 对于重复的 可以再维护一个小的散列表 记录出现次数超过1次的数据以及对应的个数

    2019-01-10
    8
    74
  • Costar
    有个问题怎么解决的?Bloom filter删除数据时,不能把bit位置0

    作者回复: 一般不用来删除,如果非要支持删除,可以再弄个数据结构记录删除的数据。

    2019-07-02
    5
    19
  • gogo-heidi
    王争哥,您好。你画这个图,用的啥软件画的啊? 比普通的黑白图更容易理解。望求解!感激不尽!

    作者回复: ipad paper

    2019-01-09
    8
  • 蓝色~冰*羽
    请问争哥,new char[nbits/16+1]这里面为什么要做这个计算,看不懂啊

    作者回复: char是16位的

    2019-03-21
    2
    4
  • 公众号:编程指北
    老师,按照你的讲解我写了一个简单的布隆过滤器, 使用了3个简单的哈希函数,判错率在0.9左右 不知道是否是属于偏高了,这是代码,可以的话帮忙看看是否正确https://github.com/MarvinLe/tools/tree/master/BloomFilter

    作者回复: 判错旅太高了 哈希函数不够随机均匀?位图不够大?

    2019-01-09
    4
  • 煦暖
    争哥,位图的代码理解了好久还没懂(;′⌒`),能加几行注释吗??

    作者回复: 好的 我去补充下

    2019-01-11
    3
  • 张凯宇
    第二题用散列表和哈希函数的方法时,存了图片的地址,先哈希值比再全量比,如果允许错判,那当前的方案是不是也可以不存储地址了,只比哈希值

    作者回复: 是的,你说的没错。

    2019-10-14
    1
  • 子嘉
    用位图去存一亿个数 是否存在的下标 但是有个问题 如果是有重复的数值 那就没法存了? 每一位只能0-1 除非用多位来存储?

    作者回复: 见我另一个留言

    2019-01-10
    1
  • Qualifor
    老师我想请问下,在说如果数字范围是1-10亿的时候,需要10亿个二进制位,占用120M内存,”占用的内存不降反增“,这个不降反增是跟谁作比较呢?如果还是存储整数类型,肯定还是位比较省空间呀,而如果跟1亿做比较,肯定是10亿占用空间大啊,因为基数不一样嘛,所以不是很理解在这里突出”不降反增“是什么意思

    作者回复: 跟文章中你摘抄出来的文字的前面一段话给出的存储方式比较

    2019-09-29
    2
  • skull
    bytes[byteIndex] |= (1 << bitIndex); 老师,这段比较的时候,直接与bitIndex进行疑惑不就可以了么,为何要向左移一位呢?

    作者回复: 你自己举个例子看看,直接异或不对的啊

    2019-09-27
    2
收起评论
显示
设置
留言
98
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部