45 | 位图：如何实现网页爬虫中的URL去重功能？
王争
该思维导图由 AI 生成，仅供参考
网页爬虫是搜索引擎中的非常重要的系统，负责爬取几十亿、上百亿的网页。爬虫的工作原理是，通过解析已经爬取页面中的网页链接，然后再爬取这些链接对应的网页。而同一个网页链接有可能被包含在多个页面中，这就会导致爬虫在爬取的过程中，重复爬取相同的网页。如果你是一名负责爬虫的工程师，你会如何避免这些重复的爬取呢？
最容易想到的方法就是，我们记录已经爬取的网页链接（也就是 URL），在爬取一个新的网页之前，我们拿它的链接，在已经爬取的网页链接列表中搜索。如果存在，那就说明这个网页已经被爬取过了；如果不存在，那就说明这个网页还没有被爬取过，可以继续去爬取。等爬取到这个网页之后，我们将这个网页的链接添加到已经爬取的网页链接列表了。
思路非常简单，我想你应该很容易就能想到。不过，我们该如何记录已经爬取的网页链接呢？需要用什么样的数据结构呢？
算法解析
关于这个问题，我们可以先回想下，是否可以用我们之前学过的数据结构来解决呢？
这个问题要处理的对象是网页链接，也就是 URL，需要支持的操作有两个，添加一个 URL 和查询一个 URL。除了这两个功能性的要求之外，在非功能性方面，我们还要求这两个操作的执行效率要尽可能高。除此之外，因为我们处理的是上亿的网页链接，内存消耗会非常大，所以在存储效率上，我们要尽可能地高效。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入探讨了网页爬虫中的URL去重功能及其实现方法。作者首先讨论了使用散列表、红黑树、跳表等数据结构来解决URL去重问题的挑战，但指出了内存消耗和执行效率方面的限制。随后，文章引入了位图和布隆过滤器的概念，详细解释了它们的原理和优势。位图通过数组下标定位数据，访问效率高且内存消耗较小，适用于数字范围不大的情况。而布隆过滤器则通过多个哈希函数定位数据，降低了冲突概率，适用于数字范围较大的情况。布隆过滤器的引入为URL去重问题提供了更为高效的解决方案。文章还指出布隆过滤器的误判特点，以及在存储空间和执行效率方面与散列表的比较，展示了布隆过滤器在爬虫判重问题中的优势。通过本文的阐述，读者能够全面了解URL去重功能的挑战、解决方案以及各种存储结构的优缺点，为实际应用提供了有力的技术支持。文章还提到了布隆过滤器在其他领域的应用，如统计网站UV数等，展示了其广泛的适用性。文章以简洁清晰的语言，深入浅出地介绍了这些存储结构的原理和应用，为读者快速了解URL去重功能提供了有益的参考。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《数据结构与算法之美》，新⼈⾸单¥68
《数据结构与算法之美》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(98)
- 最新
- 精选
越过山丘第一题，数字重复了，有什么好方法处理吗作者回复: 对于重复的 可以再维护一个小的散列表 记录出现次数超过1次的数据以及对应的个数
2019-01-10874- Costar有个问题怎么解决的？Bloom filter删除数据时，不能把bit位置0
作者回复: 一般不用来删除，如果非要支持删除，可以再弄个数据结构记录删除的数据。
2019-07-02519 
gogo-heidi王争哥，您好。你画这个图，用的啥软件画的啊？ 比普通的黑白图更容易理解。望求解！感激不尽！作者回复: ipad paper
2019-01-098
蓝色~冰*羽请问争哥，new char[nbits/16+1]这里面为什么要做这个计算，看不懂啊作者回复: char是16位的
2019-03-2124
公众号：编程指北老师，按照你的讲解我写了一个简单的布隆过滤器， 使用了3个简单的哈希函数，判错率在0.9左右 不知道是否是属于偏高了，这是代码，可以的话帮忙看看是否正确https://github.com/MarvinLe/tools/tree/master/BloomFilter作者回复: 判错旅太高了 哈希函数不够随机均匀？位图不够大？
2019-01-094
煦暖争哥，位图的代码理解了好久还没懂(；′⌒`)，能加几行注释吗？？作者回复: 好的 我去补充下
2019-01-113
张凯宇第二题用散列表和哈希函数的方法时，存了图片的地址，先哈希值比再全量比，如果允许错判，那当前的方案是不是也可以不存储地址了，只比哈希值作者回复: 是的，你说的没错。
2019-10-141
子嘉用位图去存一亿个数 是否存在的下标 但是有个问题 如果是有重复的数值 那就没法存了？ 每一位只能0-1 除非用多位来存储？作者回复: 见我另一个留言
2019-01-101
Qualifor老师我想请问下，在说如果数字范围是1-10亿的时候，需要10亿个二进制位，占用120M内存，”占用的内存不降反增“，这个不降反增是跟谁作比较呢？如果还是存储整数类型，肯定还是位比较省空间呀，而如果跟1亿做比较，肯定是10亿占用空间大啊，因为基数不一样嘛，所以不是很理解在这里突出”不降反增“是什么意思作者回复: 跟文章中你摘抄出来的文字的前面一段话给出的存储方式比较
2019-09-292
skullbytes[byteIndex] |= (1 << bitIndex); 老师，这段比较的时候，直接与bitIndex进行疑惑不就可以了么，为何要向左移一位呢？作者回复: 你自己举个例子看看，直接异或不对的啊
2019-09-272
收起评论
