从种子站点开始逐层抓取
一般来说,爬虫选择蝴蝶结左部的网页。即目录型网页作为种子站点(抓取出发点),典型的如sina.com和sohu.com这样的门户网站的主页。每完成一次抓取网页之后提取其中的链接(提取的方法需要一些HTML语法分析,以及区分绝对路径和相对路径的技巧等),这些字符串形式的链接是指向其他网页的URL,它们指引爬虫更加深入地抓取其他网页。一个网页常常包含多个链接,因此在提取网页的链接.
后,如何继续抓取其他网页,爬虫有如下两种选择处理抓取的“顺序”问题。
(1)深度优先策略(Depth-FirstTraversal)。
深度优先的遍历策略类似中华文化中家族继承的策略,典型的如封建帝位的继承。通常为长子继承,如果长子过世,长孙的优先级大于次子的优先级。如长子过世且长子无子,那么次子继承,这种在继承上的优先关系也称作深度优先策略.在继承优先顺序上,长子>长孙>长孙的其他兄弟>次子>次子的其他兄弟。这种首先选择某个分支,继而深入到不能深入的情况下才考虑其他分支的策略即为深度优先策略。
(2)宽度优先策略(Breadth-First Traversal)。
宽度优先也称为“广度优先”,或“层次优先”,它是一种层次型距离不断增大的遍历方式,类似长幼有序的规则。在晚辈给长辈献茶时,总是先献长辈,然后次之.
祖先的优先级最高,第2层的优先级大于第3层,每层的内部优先级以年长者优先。因此这里次子的优先级大于长孙的优先级,这就是宽度优先策略。
在抓取的顺序策略上选择宽度优先出于如下3点原因。
首先,重要的网页往往离种子站点的距离较近,这符合直觉。我们通常在打开某些新闻网站时,进入眼帘的往往是最重要的新闻。随着不断地冲浪(可以理解为深度不断加深),所看到的网页的重要性越来越低,甚至偶尔会出现无法访问的情况。
其次,万维网的深度没有我们想象得那么深,到达某一个网页的路径通常很多,总会存在一条很短的路径到达。有研究表明,中文万维网直径的长度只有17。
最后,宽度优先规则有利于多爬虫合作抓取(这种合作策略在后面还会提到)。这是因为该规则开始抓取的网页通常都是站内网页,逐渐才会遇到站外链接,因此抓取的封闭性较强。
进行宽度优先遍历时,必须要有一个队列(queue)数据结构支持。这个队列理解为其工作负载队列,只要其中存在没有完成的抓取任务,就需要提取队头位置的网页继续抓取。直到完成全部抓取任务,工作负载队列为空为止。