《45位图：如何实现网页爬虫中的URL去重功能？Q群170701297.pdf》由会员分享，可在线阅读，更多相关《45位图：如何实现网页爬虫中的URL去重功能？Q群170701297.pdf（10页珍藏版）》请在三一文库上搜索。
1、45|位图：如何实现网页爬虫中的URL去重功能？ file:/F/geektime/ebook/数据结构与算法之美/45位图：如何实现网页爬虫中的URL去重功能？.html2019/1/22 18:48:26 45|位图：如何实现网页爬虫中的URL去重功能？ 网页爬虫是搜索引擎中的非常重要的系统，负责爬取几十亿、上百亿的网页。爬虫的工作原理是，通过解析已经爬取页面中的网页链接，然后再爬取这些链接对 应的网页。而同一个网页链接有可能被包含在多个页面中，这就会导致爬虫在爬取的过程中，重复爬取相同的网页。如果你是一名负责爬虫的工程师，你会如何 避免这些重复的爬取呢？ 最容易想到的方法就是，我们记录已
2、经爬取的网页链接（也就是URL），在爬取一个新的网页之前，我们拿它的链接，在已经爬取的网页链接列表中搜索。如果 存在，那就说明这个网页已经被爬取过了；如果不存在，那就说明这个网页还没有被爬取过，可以继续去爬取。等爬取到这个网页之后，我们将这个网页的链接 添加到已经爬取的网页链接列表了。 思路非常简单，我想你应该很容易就能想到。不过，我们该如何记录已经爬取的网页链接呢？需要用什么样的数据结构呢？ 算法解析 关于这个问题，我们可以先回想下，是否可以用我们之前学过的数据结构来解决呢？ 这个问题要处理的对象是网页链接，也就是URL，需要支持的操作有两个，添加一个URL和查询一个URL。除了这两个功能性
3、的要求之外，在非功能性方面，我 们还要求这两个操作的执行效率要尽可能高。除此之外，因为我们处理的是上亿的网页链接，内存消耗会非常大，所以在存储效率上，我们要尽可能地高效。 我们回想一下，满足这些条件的数据结构有哪些呢？显然，散列表、红黑树、跳表这些动态数据结构，都能支持快速地插入、查找数据，但是对内存消耗方面， 是否可以接受呢？ 我们拿散列表来举例。假设我们要爬取10亿个网页（像Google、百度这样的通用搜索引擎，爬取的网页可能会更多），为了判重，我们把这10亿网页链接存储在 散列表中。你来估算下，大约需要多少内存？ 假设一个URL的平均长度是64字节，那单纯存储这10亿个URL，需要大约6
4、0GB的内存空间。因为散列表必须维持较小的装载因子，才能保证不会出现过多的散列 冲突，导致操作的性能下降。而且，用链表法解决冲突的散列表，还会存储链表指针。所以，如果将这10亿个URL构建成散列表，那需要的内存空间会远大 于60GB，有可能会超过100GB。 当然，对于一个大型的搜索引擎来说，即便是100GB的内存要求，其实也不算太高，我们可以采用分治的思想，用多台机器（比如20台内存是8GB的机器）来存储 这10亿网页链接。这种分治的处理思路，我们讲过很多次了，这里就不详细说了。 对于爬虫的URL去重这个问题，刚刚讲到的分治加散列表的思路，已经是可以实实在在工作的了。不过，作为一个有追求的工
5、程师，我们应该考虑，在添加、查 询数据的效率以及内存消耗方面，我们是否还有进一步的优化空间呢？ 你可能会说，散列表中添加、查找数据的时间复杂度已经是O(1)，还能有进一步优化的空间吗？实际上，我们前面也讲过，时间复杂度并不能完全代表代码的执 行时间。大O时间复杂度表示法，会忽略掉常数、系数和低阶，并且统计的对象是语句的频度。不同的语句，执行时间也是不同的。时间复杂度只是表示执行时间 随数据规模的变化趋势，并不能度量在特定的数据规模下，代码执行时间的多少。 如果时间复杂度中原来的系数是10，我们现在能够通过优化，将系数降为1，那在时间复杂度没有变化的情况下，执行效率就提高了10倍。对于实际的软件
6、开发来 说，10倍效率的提升，显然是一个非常值得的优化。 如果我们用基于链表的方法解决冲突问题，散列表中存储的是URL，那当查询的时候，通过哈希函数定位到某个链表之后，我们还需要依次比对每个链表中 45|位图：如何实现网页爬虫中的URL去重功能？ file:/F/geektime/ebook/数据结构与算法之美/45位图：如何实现网页爬虫中的URL去重功能？.html2019/1/22 18:48:26 的URL。这个操作是比较耗时的，主要有两点原因。 一方面，链表中的结点在内存中不是连续存储的，所以不能一下子加载到CPU缓存中，没法很好地利用到CPU高速缓存，所以数据访问性能方面会打折扣。
7、另一方面，链表中的每个数据都是URL，而URL不是简单的数字，是平均长度为64字节的字符串。也就是说，我们要让待判重的URL，跟链表中的每个URL，做 字符串匹配。显然，这样一个字符串匹配操作，比起单纯的数字比对，要慢很多。所以，基于这两点，执行效率方面肯定是有优化空间的。 对于内存消耗方面的优化，除了刚刚这种基于散列表的解决方案，貌似没有更好的法子了。实际上，如果要想内存方面有明显的节省，那就得换一种解决方案， 也就是我们今天要着重讲的这种存储结构，布隆过滤器（Bloom Filter）。 在讲布隆过滤器前，我要先讲一下另一种存储结构，位图（BitMap）。因为，布隆过滤器本身就是基于位图的
8、，是对位图的一种改进。 我们先来看一个跟开篇的问题非常类似，但稍微简单的问题。我们有1千万个整数，整数的范围在1到1亿之间。如何快速查找某个整数是否在这1千万个整数中 呢？ 当然，这个问题还是可以用散列表来解决。不过，我们可以使用一种比较“特殊”的散列表，那就是位图。我们申请一个大小为1亿、数据类型为布尔类型（true或 者false）的数组。我们将这1千万个整数作为数组下标，将对应的数组值设置成true。比如，整数5对应下标为5的数组值设置为true，也就是array5=true。 当我们查询某个整数K是否在这1千万个整数中的时候，我们只需要将对应的数组值arrayK取出来，看是否等于tru
9、e。如果等于true，那说明1千万整数中包含这个 整数K；相反，就表示不包含这个整数K。 不过，很多语言中提供的布尔类型，大小是1个字节的，并不能节省太多内存空间。实际上，表示true和false两个值，我们只需要用一个二进制位（bit）就可以 了。那如何通过编程语言，来表示一个二进制位呢？ 这里就要用到位运算了。我们可以借助编程语言中提供的数据类型，比如int、long、char等类型，通过位运算，用其中的某个位表示某个数字。文字描述起来有点 儿不好理解，我把位图的代码实现写了出来，你可以对照着代码看下，应该就能看懂了。 public class BitMap private char by
10、tes; private int nbits; public BitMap(int nbits) this.nbits = nbits; this.bytes = new charnbits/8+1; public void set(int k) if (k nbits) return; int byteIndex = k / 8; int bitIndex = k % 8; bytesbyteIndex |= (1 nbits) return false; int byteIndex = k / 8; int bitIndex = k % 8; return (bytesbyteIndex
11、& (1 nbits-1 更合适? 一修 2019-01-13 14:00:57 老师 对于这段话我的理解不是这样。比如我们今天要解决的爬虫判重这个问题，即便一个没有被爬取过的网页，被误判为已经被爬取，对于搜索引擎来说， 也并不是什么大事情，是可以容忍的，毕竟网页太多了，搜索引擎也不可能 100% 都爬取到。 实际上布隆过滤器的特点是不存在位图中的一定不会判错。所 以结果是对于已经看爬过的网页可能判断为没爬过，这样多爬一次不过是浪费点带宽 而漏爬似乎有点不太好？不知道理解对不对 2019-01-14 10:07:53 45|位图：如何实现网页爬虫中的URL去重功能？ file:/F/geekt
12、ime/ebook/数据结构与算法之美/45位图：如何实现网页爬虫中的URL去重功能？.html2019/1/22 18:48:26 作者回复 应该是判定为存在的 不一定存在 你理解错了 Alexis何春光 2019-01-13 13:10:32 哦不好意思，bitmap那里没问题了，我把 这个操作符的左右看颠倒了。有疑问的朋友可以搜索一下Java 里 bit manipulation Alexis何春光 2019-01-13 13:06:22 bitmap那里，如果以nbits为31的bitmap来说。set(31) : byte3 = 00001110. 然后如果我查找 get(30): return 00001110 & 00001100 = 00001100 !=0, return true, 就不 对了呀？可否解释一下，谢谢！ Alexis何春光 2019-01-13 12:27:51 老师，你提到100gb的内存要求就要用分布式了，但是我在网上搜到很多服务器的内存甚至可以达到tb级别，只有pc的内存才至多16gb，请问您了解的一般的 服务器的内存是多少呢？ likun 2019-01-12 15:06:29 char类型是两个字节 应该除以16吧？ 作者回复2019-01-17 15:31:19 嗯嗯 我改下，我跟c/c+搞混了