《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+搞混了