深圳SEO公司
欢迎您光临浏览!

搜索引擎的下载系统

第一节爬虫和发展历史
在搜索引擎的4大系统中,第1个系统是下载系统。和航天运载火箭系统的动力系统一样,下载系统是搜索引擎大厦的基础。
搜索的数据均来自于下载系统的工作,其工作方式巧妙、合理且强大。爬虫(也称为”Crawler”,中文译为”爬虫”,或者“蜘蛛“)是其中最华彩的乐章。让我们从爬虫开始,逐渐进入闪烁着奇异光芒的领地。
世界上第1个爬虫
爬虫是一种自动抓取万维网网页信息的机器人。世界上第1个网络爬虫由麻省理工学院(MIT)的学生马休•格留(MatthewGray)在1993年写成,并命为”万维网漫游者”.尽管其编写目的不是为了做搜索引擎,但是正是这革命性的创新。为搜索引擎的发展和今天的广泛应用奠定了坚实的基础。
爬虫的发展历程
现代搜索引擎的思路源于Wanderer,不少人改进了MatthewGrey的蜘蛛程序.1994年7月,Michael Mauldin将John Leavitt的蜘蛛程序接入到其索引程序中,创建了目前为人熟知的Lycos(lycos ).其后无数的搜素引擎促使爬虫越写越复杂,并逐渐向多策略、负载均衡及大规模增量抓取等方向发展.爬虫的工作成果使得搜索引擎能够检索几乎全部的万维网网页,甚至被删除的网页也可以通过一个称之为“网页快照’的功能访
问。
前人的辉煌成就令人赞叹不已,那么爬虫是怎么实现这些功能的呢?为什么说它巧妙、合理且强大呢?让我们首先从爬虫开始入手,深入理解搜索引擎的下载系统。
第二节万维网及其网页分析
在深入爬虫领地之前,不妨把爬虫行做是劳动者,把机器和网络带宽资源行做是劳动资料,把万维网上的网页看做是劳动对象.因此,深入并透彻地理解劳动对象才能更加学地理解劳动者的工作原理。
蝴蛛结型的万维网
首先从万维网的静态结构入手,如果将万维网定义为一个相互连通的连通图,网页为结点,链接(link)为边,那么任意一个网页可能被其他网页链接。这种链接称为“反向链接”(backlink )。这个网页也可能链接到其他网页,这种链接称为“正向链接”(简称“链接”).
Broder通过一个有趣的Random-start BFS ( Breadth-Firs)Search》实验随机取得570个网页作为开始结点,依次逐个地试验这570个网页.首先采用正向(forward direction )宽度优先遍历(宽度优先遍历的方法将在后面检素),即按照网页到网页的链接进行遍历。然后采用反向(backward )宽度优先遍历,即按照网页到网页反向链接进行遍历.例如网页A包含网页B的链接,则从网页A开始,正向遍历可以遍历到网页B;从网页B开始,反向遍历可以遍历到网页A.
通过实验发现,无论是正向遍历还是反向遍历,表现出来的是截然不同的遍历效果。要么是在遍历到很小的结果集( 90%的情况下探测到的集合大小不超过90个结点.极端情况下也只有几万个网页而已)后遍历终止;要么是爆炸性地遍历到了大约1亿个网页,但是没有探测到全部的18 600万个结点.此外,对于一部分的起始点,无论是正向,还是反向遍历都能够探测出大约1亿个网页,这部分起始点属于后面提到的SCC部分.通过实验数据.Broder得出这样一个结论,即万维网具有蝴蝶结型(bow tie )结构,如图3-1所示。

蝴蝶型结构图

其中的网页分为如下4种类型,各约占1/4,
1.蝴蝶结的中部(SCC , Strongly Connected Component ).这种类型的网页彼此相连,任意去掉有限个网页,不会影响其连通度.Random-start BFS遍历实验的起始点选择该部分网页,采用正向遍历的方法,从统计的角度上看可以遍历占全部网页3/4的网页数;采用反向遍历的方法也可以遍历大致同样数量的网页。
2.蝴蝶结的左部(IN).
这种类型的网页指向中心部分(SCC )。称为“目录型网页”(hub page),即通常说的导航网页。Random-start BFS遍历实验的起始点选择该部分网页,采用正向遍历的方法可以遍历占全部网页3/4的网页数;采用反向遍历的方法只能遍历很有限的一些网页,所占比例可以忽略不计。
3.蝴媒结的右部(OUT ).
这种类型的网页被中心部分指向,称为“权威性网页”(authority page ).这些网页被引用次数多,表示为大多数网页对其“认可度”高.Random-start BFS遍历实验的起始点选择该部分网页,采用正向遍历的方法只能遍历有限的网页;采用反向遍历的方法可以遍历占全部网页3/4的网页。
4.蝴蝶结的须脚(Tendrils ).
这种类型的网页表现为从左部链出到其他网页,或者其他网页链入右部或从左部直接链入右部,以及少部分与中部、左部或右部都没有链接(非连通分量DISC ),  Random-start BFS遍历实验的起始点选择这部分的网页,无论采用何种遍历方法都只能遍历有限的网页。
通过万维网的结构特征得出如下两个结论。
1.爬虫尽可能选择蝴蝶结的左部,或者中部的网页为起始访问结点集合(starting set of URLs)进行遍历,这样可以得到尽可能完整的遍历效果。如果选择右部或者须脚部分的网页为起始结点,则只能抓取很有限的网页。
2.网页分为目录型网页和权威性网页,目录型网页为普通网民服务,便于网民点击从而继续浏览更多的网页。该部分网页对于深入抓取权威性网页有重大意义;权威性网页是那些处于蝴蝶结中部或者右部的网页,这类网页的反向链接数很多,而正向链接数相对较少,通常认为这类网页比较重要。
万维网的直径
万维网直径(Diameter of the World Wide Web)又称为“Web直径”其定义为如果用d表示存在一条从网页u到网页v的路径,那么这些万维网上所有不同的连通网页对(pair of connectedpage)所构成的最短路径的平均长 度即Web直径.按照这样的定义和大规模网页的计算得到Web直径约为17左右。有兴趣的读者可以参考文献(Reka Albert et al. 1999)。万维网直径计算公式d=0.35 + 2.06 log ( N )(其中N为网页的数.).有研究表明中国万维网的直径为16.26。即如果任何两个网页之间存在一条路径可达的话,平均点击不超过17次即可从一个网页到达另一个网页。
事实上。网页的平均出度为25.7,即平均每一个网页含有25.7个指向其他网页的链接。这些链接引导网民继续在网上冲浪,直到对其个主题厌倦,开始下一个主题。下一章中还会讲到这个冲浪模型。
同样得到如下两个结论。
1.遍历的方法很大程度上影响了爬虫的效率,万维网的网页结构并没有我们想像的深,却出乎我们意料地宽,因此爬虫的遍历方式多采用宽度优先的遍历方式.当然这里还有一个网页重要性的原因,采用这种方式可以较好地抓取重要性高的网页.
2.万维网错综复杂,任选一个抓取路线不能保证总是最优.为了防止爬虫一路走到黑,充分考虑万维网的万维网直径后。采用“深度策略”控制抓取深度,从而完美地解决了这个问题.万维网的规摸及变化特征在了解了万维网宏观静态的一面之后,再来看看其宏观动态变化的一面。
毫无疑问,万维网的规模是巨大的。早在1998年,各种研究就在试图估计万维网的规模。尽管方法各异得出的具体数值不尽相同,但都认为万维网的规模(有价值的网页数目)在十亿数量级上。根据Lawrence和Giles在1999年研究显示,世界万维网网页的数目每两年增加一倍,因此截至目前万维网的规模已达百亿数量级。
2000年斯坦福大学的Cho和Garcia-Molina随机选用50万个网页做样本。发现23%的网页是每天更新的,其中40%域名后缀为.com的网页是每天更新的,网页的半衰期(half-life)为10天.也就是说50万的网页在10天后只剩下25万,再过10天只剩下12.5万。此外,网页的变化可以归结为泊松过程( Poisson process )模型(在网页重访策略部分会详细提到这个模型).可以说万维网的变化是日新月异,一日千里.如何与万维网的变化保持同步成为爬虫的又一个主要难点。
网页的特征
让我们从宏观来到微观,考察一下网页的特性。归纳起来。对于搜索引擎来说,网页具有的3大特征分别是挥发性(volatile ),半结构性(semi-structed)和隐蔽(hidden ).网页诞生到网页消亡(挥发性)总是不可避免的, HTML语言描述的网页是一种半结构化的数据。除了静态网页以外.还有很多隐藏的动态网页,
例如需要登录才能看到的某些动态网页.
接下来从有关爬虫的基本概念开始,由点到面,层层深入地理解爬虫是如何针对万维网的这些特点,采取相应的策略实现了抓得全、抓得快且代价低的基本目标。
第三节有关爬虫的基本概念
爬虫也称为“Wanderers”(漫步者)或者“Robots”(机器人),它首先是一组运行在计算机中的程序,在搜索引擎系统中负责抓取时新的且公共可访问的Web网页、图片和文档等资源.这种抓取的过程为通过下载一个网页,分析其中的链接.继而漫游到其他链接指向的网页,循环往复。
种子站点
种子站点是爬虫开始抓取的起点,通常为各大门户网站和官方网站的首页等。
URL
URL是“niform Resource Locator”(统一资源定位器)的缩写.它是用在万维网和其他万维网资源中的一种编址系统。例如http://www.smiseo.com/index.html,其中包含访i7方式(http协议)、被访问的服务器(www.smiseo.com)和被访问的文件
(index.html).
Backlinks
一个网页的Backlinks是那些除网页自身之外指向自身链接的集合,Backlinks的数目是衡量网页受“欢迎”程度的重要度量方式。
第四节网页抓取原理
爬虫的工作原理包括抓取、策略和存储,抓取是爬虫的基本劳动过程;策略是爬虫的智慧中枢;存储是爬虫的劳动成果.我们按照逐个击破,由浅入深的方式逐步了解整个爬虫的工作原理。
telnet和wget
使用Windows操作系统的用户,执行如下步骤即可下载一个网页。
1.打开Windows命令行窗口.
2.输入telnet www.smiseo.com 80(注意中间的空格).
3.输入GET /index.html(注愈GET要全大写,其后要有空格).
如果以上每一步都正确执行.则应该在桌面上看到深圳SEO网站首页的网页源代码。笔者得到的是如下的网页代码:
<script>location.href二”./index.html”</script>
使用Linux操作系统的用户,则只衡要一步,即输入:vimhttp://www.smiseo.com/index.htmI,可以得到同样的结果.
如果要把该网页文件下载到本地硬盘,对于Linux操作系统的用户,只器要输入命令:
wget www.smiseo.com/index.html
之后使用vi可以打开该文件.Windows操作系统的用户可以下载一个wget程序。使用同样方法下载网页.
由此括来,下载一个网页如此简单。如果要下载整个万维网那么应当采用什么样的遍历规则呢?
从种子站点开始逐层抓取
基于万维网的蝴蝶结型结构,这种非线性的网页组织结构,就出现了抓取“顺序”的问题,即哪些先抓、那些后抓。这种解决抓取“顺序”的策略必须保证尽可能抓取所有网页(本章不区分抓取网页和下载网页的区别).
一般来说,爬虫选择蝴蝶左部的网页。即目录型网页作为种子站点(抓取出发点),典型的如 smiseo.com和:baidu.com这样的门户网站的主页。每完成一次抓取网页之后提取其中的链接(提取的方法需要一些HTML语法分析,以及区分绝对路径和相对路
径的技巧等),这些字符串形式的链接是指向其他网页的URL,它们指引爬虫更加深入地抓取其它网页。一个网页常常包含多个链接,因此在提取网页的链接后,如何继续抓取其他网页,爬虫有如下两种选择处理抓取的“顺序”问题。
1.深度优先策略(Depth-First Traversal).
深度优先的遍历策略类似中华文化中家族继承的策略,典型的如封建帝位的继承。通常为长子继承,如果长子过世,长孙的优先级大于次子的优先级。如长子过世且长子无子.那么次子继承,这种在继承上的优先关系也称作深度优先策略。如图3-2所
示.

继承优化级

在继承优先顺序上,长子>长孙>长孙的其他兄弟>次子>次的其他兄弟。这种首先选择某个分支 ,继而深入到不能深入的情况下才考虑其他分支的策略即为深度优先策略。
2.宽度优先策略(Breadth-First Traversal).
宽度优先也称为“广度优先”,或“层次优先”,它是一种层次型距离不断增大的遍历方式,类似长幼有序的规则。在晚辈给长辈献茶时,总是先献长辈,然后次之,如图3-3所示.

继承顺序

在图3-3中,祖先的优先级最高,第2层的优先级大于第3层,每层的内部优先级以年长者优先。因此这里次子的优先级大于长孙的优先权,这就是宽度优先策略。
在抓取的顺序策略上选择宽度优先出于如下3点原因。
首先.重要的网页往往离种子站点的距离较近,这符合直觉.
我们通常在打开某些新闻网站时,进入眼帘的往往是最重要的新闻.随着不断地冲浪(可以理解 为深度不断加深),所看到的网页的重要性越来越低,甚至偶尔会出现无法访问的摘况。
其次,万维网的深度没有我们想像的那么深,到达某一个网页的路径通常很多,总会存在一条很短的路径到达。有研究表明,中文万维网直径的长度只有17,
最后,宽度优先规则有利于多爬虫合作抓取(这种合作策略在后面还会提到)这是因为该规则开始抓取的网页通常都是站内网页,逐渐才会遇到站外链接,因此抓取的封闭性较强。
进行宽度优先遍历时,必须要有一个队列(queue)数据结构支持。这个队列理解为其工作负载队列,只要其中存在没有完成的抓取任务,就需要提取队头位置的网页继续抓取。直到完成全部抓取任务,工作负载队列为空为止。详细的抓取的过程如图3-4所示。

宽度优化遍历

1.爬虫提取工作负载队列中的网页0(这里假定网页0是种子站点。即抓取的起始结点)。抓取后通过对网页0的链接分析提取指向网页1和网页2的链 接放到工作队列中。此时当前工作负载队列中增加了网页1和网页2,如图3-5所示。

抓虫提取工作

2.工作负载队列中的网页0抓取完毕,继续抓取工作队列中第1个任务,即网页1。并提取指向网页3和网页4的链接放到工作队列中,如图3-6所示。

抓虫工作任务

3.根据宽度优先的规则抓取工作队列中的网页2(注意,这里可以理解为次子的优先级大于长孙,即网页2要在网页3之前抓取),并且分析出指向网页5和网页6的链接放入工作队列中,如图3-7所示。

宽度优化级抓取
4.继续抓取工作队列中的网页3,直到结束,如图3-8所示。
如果将余下的步骤略去,这种按宽度优先顺序的抓取序列就展示在我们的眼前了,即网页0-6,
通过这个例子回顾一下采用宽度优先遍历的策略抓取网页带来的好处。
如果将网页0理解为门户首页,那么距离门户首页越近的网页越重要。把首页理解成一个窗口,那么打开这个窗口,距离越近的网页被浏览的机会越大,因此也就越重要。上面这个例子中网页1比网页3和网页5更加重要,按照距离递增的宽度优先抓取顺序恰好符合了重要网页优先抓取的要求.如果按照深度优先规则抓取,不仅破坏了重要优先的原则。而且破坏了抓取的封闭性。从而不利于多爬虫的合作抓取.在合作抓取策略中还将提到抓取封闭性问题.
然而,以上的例子是不完备的.为了简化描述,这里使用树型结构.树的一个基本特性是任何两点之间只有惟一的路径,即不会出现环路。而万维网中存在大量环路,实际上网页6可能存在指向网页0的链接。如果没有任何判断,则爬虫永远抓取不完,因为存在了0, 2和6这样一个死循环。死循环会带来下面两个不利后果。
1.不该抓的反复抓。如果一个网页变化不大,则只要抓取一次即可,重复抓取相同网页就会占用大量CPU和带宽资源.
2.该抓的没有机会抓.由于大量的资源被用在做无用功,所以必然使得某些网页被歧视,从而不能被及时抓取。为了解决死循环的问题。通常需要一个称为“不重复抓取策
略”和一个称为“深度策略”的方法来解决。
不重复抓取策略
不重复的关键在于记住历史,只有记住过去才可能不重复。那些不需要记忆历史的程序设计往往都比较简单,从计算机的角度上讲即有限状态机模型.每个状态都是对历史的积累,而没有记忆历史。这种只需要有限的存储即可完成的工作通常都比较简单。而那些需要记住历史的程序相对复杂,例如迷宫求解程序,则需要一个栈(stack)结构记住走过的地方.从而在失败时可以回溯。继续寻找出路.而通过动态规划寻找问题最优解等程序,也都需要一个记住历史的功能才能保证不重复计算。
爬虫记录历史的方式是哈希表(也称为“杂凑表”),每一条记录是否被抓取的信息存放在哈希表的某一个槽位上。如果某网页在过去的某个时刻已经被抓取,则将其对应的植位的值置1;反之置0。而具体映射到那一个槽位,则由哈希函数决定.在介绍哈希表前,我们首先简单了解一下MD5签名函数。
1992年8月,Ronald L. Rivest在向LEFT提交的一份重要文件中描述了这种MD5签名算法的原理。由于这种算法的公开性和安全性.所以在90年代被广泛使用。MD5签名是一个哈希函数,可以将任意长度的数据流转换为一个固定长度的数字(通常为4个整型,即128位).这个数字称为“数据流的签名”或者“指纹”( Digital Finger Print )。并且数据流中的任愈一个微小的变化都会导致签名值发生变化。
将URL字符串数字化是通过某种计算将任何一个URL字符串惟一地计算成一个整数,如图3-8所示。

抓取策略

在一个URL哈希函数映射下,任意一个字符串都惟一地对应一个整数.一个64位整数可以表达1 800万TB(1TB=1000 GB),而字符串空间的大小远远大于64位整数所表达的整数空间大小因此碰撞是不可避免的.碰撞是指那些字符串不同,而计算出相同的签名值的情况。然而如果杂凑函数设计得足够好,则相互碰撞的机会可以小到忽略不计。
更加理论化的表示如下:

啥希函数公式

不难看出,对于两个不相同的URL,即URLi和URLj通过哈希函数分别计算出各自的签名值Ti及Tj。这两个签名值相等(碰撞)的概率小于一个足够小的小整数£.正是由于MD5函数符台这种特性,因此被广泛地用做哈希函数。
标准MD5签名的整数空间很大,128位整数能衷达2的128次方个不同的数,这是十分巨大的,而实际分配的哈希表空间确十分有限,一个普通32位处理器.理论上般多可以分配2的32次方大小的内存。即4G大小的内存(Linux系统中操作系统内核还需占用1G内存,实际上可供搜索引擎使用的极限内存只有3G).
因此,在实际处理中将签名值进行模运娜映射到实际的哈希表中(可以理解为哈希表存放在内存中).因此实际的哈希函数是MD5(URL)%n。(%表示取模运算),这样使得一个URL被映射到大小为n的哈希表的某个槽位上。
哈希表是简单的顺序表,即数组.从实际应用的角度看,这个数组要足够大。而且尽可能地全部放在内存中,以保证每一个URL的签名都可以通过查找哈希表来确定是否曾经抓取过,其示例如图3-9所示。

利用哈希表索引网页

假定抓取顺序为sohu , sina和sohu,首先我们在抓取sohu时为该URL签名.假定得到的结果为2,我们存放在数组的第2个槽上。这个过程只要将第2个槽位置1,表示已访问过.继续抓取sina以同样方法,假定将其存放在数组的第7个槽位上,之后重复抓取到了sohu.由于MD5签名函数特性,任何一个自变量惟一对应一个应变量。因此计算sohu的签名,同样得到结果为2。当我们查询第2个槽位时,发现该槽位已经置1,说明已经访问过,因此不再重复访问。
有调查表明,中文万维网页总数超过100亿.如果要存放100亿网页是否被抓取过这样一个历史信息。那么需要的哈希表将会非常大。如果哈希表每一个单元为一个字节(8位).则至少需要10GB的容量。而且为了保证碰简的概率极低.实际燕要的容量远大于10GB,然而32位操作系统的 最大寻址空间为4GB,即理论上最大的物理内存为4 GB,因此在内存中不可能分配一个如此巨大的哈希表。
为了能够将整个哈希表装入内存,通常采用Bitmap的数据结构压缩内存用量,Bitmap需要借助按位与(&)和按位或(丨),以及左移(<<),右移(>>)这4种基本位运算。通过一个例子来说明,如图3-10所示。

搜索引擎哈希表运算

Bitmap结构使用整型作为基本单元,一个整型为32位, 一个int Hash(8)的数组仅通过8个单元来记录历史。而如果将比特作为最小单元,则能扩展到256个单元。
定义这样一个哈希表.即int Hash[8].将sohu作为字符串执行一次MD5签名,假定得到的签名值为34。用34除32,得到商数为1,继续用I对8取模运算得到1,表示槽位在Hash(1)中。用34除32,得到余数为2,表示34映射到Hash(1)这个32位整数的第3个比特位上(从低位算起,余数为0则映射到第1个比特位),将这个比特位置1,则Hach(1)为4,这是国为Hash(1)的第3个比特位被置1.则Hash[1]为4,这是因
不妨将34这个数按比特位的方式展开,如图3-ll所示。通过这种形式进一步理解Bitmap如何扩展存储空间的方法。

Bitmap扩展存储空间

34的二进制的前3位001决定了它存放在数组的第2个位置上(数组的起始下标为0),即存放在Hash(1)上,前面提到的除以32后,对8取模的目的就是取出34这个数的前3位。
具体存放在Hash(1)的从低位算起的第几个比特位则由后5位决定.后5位为00010,表示存放在Hash(1)这个整数的第3个比特位上。前面提到的34除以32后得到余数即为这里的后5位.
通过前面的计算,Hash(1)的实际值为4,表示其第3个比特位被置1.图3-11中,在Hash(1)中用4这个数值完整地表示了34这个签名值.
通常使用移位运算来快速计算除以或者乘以一个2的n次幂;将某个比特位置为1,采用按位或运算;查询某个比特位是否为1,采用按位与运算。对前面计算的过程用C代码的方式表示如下:

C语言运算
上述过程读者可以用纸笔计算一下,从而了解这种解决问题的技巧.通过Bitmap结构。利用计算机速度极快的按位与、按位或和移位运算能够高效地实现记住历史。不重复抓取的策略,同时将原来的哈希表压缩了1/32,除此之外,Bloom filter算法还可以更加经济地利用好哈希表中的比特位,使得更加经济地灵活地使用内存。简单地说,对于一个字符串独立地使用m哈希函数计算,然后将其值映射到哈希表的m槽上。如果这m个槽都置I,说明该字符串已经在历史上出现过;否则说明该字符串是第1 次出现,将m个槽都置1.通图3-12来进一步理解。

Bloom filter算法
在抓取到sohu时。执行3次独立的不同的哈希函数(如图3-12中的Hash1, Hash2和Hash3 )运算.映射到哈希表的3个槽上,假定是1,3和7.接下来如果抓取到sina.经过同样的3次哈希函数运挤,假定计算的结果是1, 3和6。很明显存在一个槽6是之前没有置位的,因此sina没有抓取过.成功抓取sina后,将植位6置1, Bloom算法一方面提高了哈希数组的利用效率,并被证明适宜于应用在大规模集台查找计算中.同时在网络应用中也被大量采用,有兴趣的读者可以进一步阅读文献【Bloom , B.H. 19701】深入理解该算法。
在抓取提速部分讲到通过多爬虫的合作抓取,这样可以进一步降低每个爬虫的用于记录历史抓取情况的哈希表大小.即如果有n个爬虫,则可将哈希表继续压缩到原有大小的n分之一。如果n个爬虫分别运行在不同的机器上,那么每个机器被哈希表占用的内存用量将非常少,通常保持抓取历史记录所需要的内存在百兆字节左右是恰当的。通过不重复抓取的方法初步解决了死循环的问题。即抓过的不再抓.循环的条件被破坏。然而实 际操作中还有这样一个隐含的问题,即如前所述的万维网直径。如果任意两个网页存在链接,则链接它们的最短路径的期望值为17。这样,爬虫无论用何种遍历方法都不能保证一定会按照最佳路径抓取每一个网页,因为任何一个网页都可能从多个种子站点开始宽度优先的被遍历到.
我们来看一个例子:
假如从种子站点A、种子站点B及种子站点C开始均存在一条到达网页P的路径,路径长度分别为3, 27和143.很明显,器要浪费两次检查网页P是否被抓取的开销。由于从种子站点A开始很快抓到了网页P,而种子站点B和C则经过漫长的路径达到P时共计需要两次检查网页P是否被抓取,这显然是不够经济的。
为了防止爬虫无限制的宽度优先抓取,必须在某个深度上进行限制。到达这个深度后就应该停止抓取。这个深度的取值就是万维网直径长度.当在最大深度上停止时,那些深度过大的未抓网页,总是期望可以从其他种子站点更加经济地到达.例如,种子站点B和C在抓取到深度17时即停止抓取,把抓取网页P的机会留给从种子站点A出发的进行抓取工作的爬虫。不难看出,限制抓取深度也破坏了死循环的条件,即使出现循环也会在有限次后停止。此外,深度策略和宽度优先遍历策路的组合可以有效地保证抓取过程中的封闭性.即在抓取过程(遍历路径)中总是在抓取相同域名下的网页,而很少出现其他域名下的网页。
爬虫总在不停地抓取网页,其工作负荷能力总是有限的。同时下载带宽和时间也是有限的,因此必须能够优先下载至要性高的网页.下面的网页抓取顺序策 略保证了即使不能下载全部网页也要保证能下载全部菌要性高的网页.
网页抓取优先策略
网页抓取优先策略也称为“页面选择问题”(Page Selection ) ,通常是尽可能地首先抓取重要性的网页。这样保证在有限的资源内尽可能地照顾到那些重要性高的网页.那么哪些网页才是重要性高的呢?如何量化重要性呢?
重要性度且由链接欢迎度、链接直要度和平均链接深度这3个方面决定【Arvind Arasu et al. 20011.】
定义链接欢迎度为IB(P),它主要由反向链接(Backlinks )的数目和质量决定.首先考察数目,直观地讲,一个网页有越多的链接指向它(反向链接数多),那么表示其他网页对其的认可。同时这个网页被网民访问的机会就大,推测出其重要性也就越高;其次考察质量,如果被越多生要性高的网页指向,那么其重要性也就越高。如果不考虑质量.就会出现局部最优。而不是全局最优的问题。最典型的就是作弊网页。人为地在一些网页中设置了大量反向链接指向其自身的网页,以提高该网页的重要性。如果不考虑链接质,,就会被这些作弊者所利用。
定义链接重要度为IL(P),它是一个关于URL字符串的函数,仅仅考察字符串本身.链接重要度主要通过一些模式,比如认为包含”com”或者“home”的URL重要度高,以及具有较少斜杠(slash)的URL重要度高等。
定义平均链接深度为ID(P),此为笔者所创。ID(P)表示在一个种子站点集合中,每个种子站点如果存在一条链路(宽度优先遍历规则)到达该网页,那么平均链接深度就是这个网页的又一个重要性指标。因为距离种子站点越近,说明被访问的机会越多.因此重要性越高,可以认为种子站点是那些重要性最高的网页;离种子站点越远,重要性越低.事实上,按照宽度优先的遍历规则即可满足这种重要性高的网页被优先抓取的需要。
最后,定义网页重要性的度一为I(P),它由以上两个量化值线性决定,即:
I(P)=A*IB(P)+β*IL(P)
平均链接深度由宽度优先的遍历规则保证,因此不作为重要性评价的指标。在抓取能力有限的情况下。如果能够把重要性高的网页尽可能地抓完。是合理科学的,最终被用户查询到的网页也往往是那些重要性高的网页。
尽管这样看来已经足够完美,事实上。还是忽视了一个重要的要素一一时间。时间导致万维网动态变化的一面.如何抓取那些新增的网页呢?如何重访(revisit)那些被修改了的网页呢?如何发现那些被删除了的网页呢?为了保持和万维网网页的同步变化,就必须有网页重访策略。通过该策略可以识别增加、修改及删除网页这3种网页变化的悄况。
网页重访策略
爬虫日积月累地下载各种各样的网页,然而过去的网页可能变化了.因此爬虫不得不周期性的刷新( refresh ),重访那些已经下载的网页。通过重访以使得这些网页能够与万维网的变化与时俱进(up-to-date).
文献(CHO, J. AND GARCIA-MOLINA, H. 2000a)表明网页变化的可以归结为泊松过程(Poisson process )模型。
为了描述泊松过程模型,使用X( t)表示在一个(0,t )的时间段内网页发生变化的数目,一个参数为λ的泊松分布满足以下性质。
爬虫更新周期公式

可以通过简单的方法验证,假定时间周期(时间间隔)为I(t=1),则有:

爬虫更新周期公式

Cho和Garcia-Molina通过对50万个随机网页的跟踪分析,得出大部分网页的更新属于泊松公布 的重要结论,如图3-13所示:

网页跟踪分析

横坐标表示网页更新的事件间隔,纵坐标是在时间间隔下发生变化的网页所占比例〔该比例取对数).在泊松模型下,若t是泊松过程中下一个事件发生的间隔时间。则下一个事件发生的时间间隔的概率分布符合指数分布。在这里表示网页变化的时间间隔符合指数分布,即:

泊松模型

对ψ(t)取自然对数,得到In( ψ(t) )=-{μtln( p )。因此In( ψ(t) )是一个关于t的线性函数,如图3-13所示。直观上可以看到,网页变化的可能性随粉变化周期(时间间隔)变长越来越小,文献(CHO, J. AND GARCIA-MOLINA, H. 2000c]较完整地论述了关于变化间隔的计算方法及其他有趣的话题。

间隔的计算方法

这样如果把平均的时间间隔看做是网页寿命,则的μ倒数就是网页的期望寿命。
在泊松模型的理论基础上,结合人们的直观感知。目前网页重访策略大致可以归为以下两类。
1.统一的重访策略:爬虫以同样的频率重访已经抓取的全部网页,以获得统一的更新机会,所有的网页不加区别地按照同样的频率被爬虫重访。
2.个体的重访策略:不同网页的改变频率不同,爬虫根据其更新频率来决定重访该个体页面的频率。即对每一个页面都一身定做一个爬虫重访频率。并且网页的变化频率与重访频率的比率对任何个体网页来说都是相等的。即对于任愈网页P;。其固有的更新频率之λi(次数/单位时间).爬虫对其重访的频率为fi,

爬虫重访频率

更新频率高的网页,重访频率就高;更新频率低的网页重访频率就低。

两种重访策略各有利弊,深入的研究表明对于那些更新频致的网页采用更加频繁的重访策略反而有害[CHO, J. ANDGARCIA-MOLINA, H. 2000b).因此策略(2)还摇要增加一些其他子策略,例如限定最小重抓频率等.策略(1)的效果在数学上可以证明总是不低于个体重访策略[CHO,  J.  ANDGARCIA-MOLINA, H. 2000b]。并且具有计耳.小的优势.但是策略(1)不具有优化的空间,难以满足质量不断改善的要求。
此外,不同类型的网站更新频率也不同。通过对不同类型的网页寿命的半衰期实验证明了这一点,网页更新的泊松分布如图3-14所示[CHO et al.2000c).

网站更新频率

通过该图,得到.com类型的网页变化最剧烈,.gov类型的网页变化最少,因此给予不同类型的网页不同的旅访频率是科学的。
回顾网页更新策略既能保证抓取历史的网页,也能够抓取随时出现的新网页。几个重要的结论如下。
1.网页更新过程符合泊松过程.
2.网页更新时间间隔符合指数分布.
3.对于不同类型的网页采用不同的更新策略.
粗放的工作做完了,然而还远远没有达到完美。爬虫的工作模式和方法存在一些问题,甚 至可以说是社会问题(BRIN, S.AND PAGE, L. 1998),爬虫的工作方式某些方面上看是脆弱的,不可控的。因为在其中包含了数以千计的万维网上的Web主机,以及大量的DNS服务器。这些都是爬虫所不能控制的.只有协调好这些外部资源,才能达到理想的抓取效果.
有些网站不希望爬虫抓取敏感信息;有些网站希望爬虫避免在白天对其网页进行抓取,从而不影响白天正常的对外公众服务;DNS服务提供商也不希望大量的域名解析工作量被搜索爬虫的域名请求所占用。
因为爬虫的工作可能带来的社会性的问题,为此要求爬虫一方面像绅士一样工作,了解网站管理员的需要。例如有些Web主机不希望爬虫抓取某些敏感目录,或者网页,这样网站管理员必须有办法告诉爬虫哪些是不希望被抓取的网页或目录.爬虫也需要礼貌地按照对方的要求执行,这就是著名的Robots协议;另一方面。爬虫尽可能自身维护一台DNS解析的服务器‘而减少访问公开DNS域名解析服务器的机会;最后,抓取的工作尽可能放在夜间,从而减少Web主机在白天的访问压力。
不同Web主机的带宽不同,能够接受的抓取强度也不同.爬虫需要尽可能平衡地抓取Web主机上的网页,即将集中抓取平衡化;反之,如果集中抓取某一个站点,很可能会把某个Web主机抓瘫痪,而影响Web站点的正常公众服务。
遵守Robots协议是爬虫礼貌工作的第1步。
Robots协议
Robots协议是Web站点和搜索引擎爬虫交互的一种方式,即将一个robots.txt的文件放在网站的根目录上.例如
http://www.smiseo.com/robots.txt。
该文件的内容如下:
User-agent: *
Disallow: /plus/ad_js.php
Disallow: /plus/advancedsearch.php
Disallow: /plus/car.php
Disallow: /plus/carbuyaction.php
Disallow: /plus/shops_buyaction.php
Disallow: /plus/erraddsave.php
Disallow: /plus/posttocar.php
Disallow: /plus/disdls.php
Disallow: /plus/feedback_js.php
Disallow: /plus/mytag_js.php
Disallow: /plus/rss.php
Disallow: /plus/search.php
Disallow: /plus/recommend.php
Disallow: /plus/stow.php
Disallow: /plus/count.php
Disallow: /include
Disallow: /templets
Sitemap: http://www.smiseo.com/sitemap.html
Sitemap: http://www.smiseo.com/sitemap1.html
在上述文件中,Robots协议通过User-agent和Disallow告知搜索引擎非公开目录和非公开网页,说明如下。
1.User-agent: *:表示对一切搜索引擎爬虫有效.如果特别针对某个爬虫,则可以写明。
2.Disallow: /plus/ad_js.php 表示禁止抓取这个目录。
3.Sitemap:是网站地图,用来告诉搜索擎你网站下所有希望被抓取的链接。
通过遵守Robots协议,表示出爬虫尊重和执行Web站点的要求。因此爬虫需要有一个分析Robots协议的模块,并严格按照Robots协议的规定只抓取Web主机允许访问的目录和网页。
其他应该注意的礼貌性问题
除了遵守Robots协议以外.通常搜索爬虫需要自身维护一个DNS域名解析的服务模块.以便减少对公开域名解析服务器的频繁请求,本书不展开讨论这部分内容。
此外,应尽可能合理地规划抓取强度。在白天尽可能地减弱抓取强度,例如每10秒抓取一次;在夜间Web主机访问量低,搜索爬虫可以适当增加抓取强度,例如每秒抓取一次。由于时差的原因,东半球的白天恰好是西半球的夜晚,因此白天可以加强抓取美国及欧洲站点的强度,夜间增加对本国站点的抓取强度。
即便如此,爬虫总不可避免会给其他万维网上的Web主机带来麻烦.因此站点抓取监控程序也是必不可少的,该程序记录每个站点的抓取流量,避免在偶然情况下因抓取强度太大而导致的各种问题.
这样,最后的问题就只剩下规模问题。如此巨大规模的万维网,每天新增的大量网页需要及时地被抓取到。对于爬虫来说,一方面对历史的网页需要重抓;另一方面要及时抓到新增的网页,在如此沉重的工作负荷下, 必须提高抓取速度才能满足这种需要。
抓取提速策略(合作抓取策略)提速基本可以采用下面几种方法.
1.提高抓取单个网页的速度.
2.尽可能减少不必要的抓取任务.
3.增加同时工作的爬虫数量.
事实证明,受到万维网发展水平的限制,第(1)种方法基本不可行,单个网页的抓取速度受到下载带宽的限制,在现有技术条件下很难任意提高;第(2)种方法难度很大,由于需要和万维网的变化保持紧密同步.所以冗余的抓取总是不可避免的.减少不必要的抓取会导致网页重访不及时,这样就不能快速同步目标网页的变化;第(3)种方法通过增加爬虫数且提高总体抓取速度是可行的。
在多个爬虫抓取的情况下,如何将工作量分解成为主要的问题.即要解决一个网页交给哪一个爬虫抓取?如果分工不明.很可能多个爬虫抓取了相同的网页。从而引入额外的开销。通常采用以下两种方法来进行抓取任务的分解。
1.通过Web主机的IP地址来分解,使某个爬虫抓取某个地址段的网页。
2.通过网页的域名来分解,使某个爬虫仅抓取某个域名段的网页。
如何选择这两种方案呢?
万维网在网络基础设施中按照IP地址来确定主机位置,IP地址为点分十进制数,难于记忆.由此采用了域名对IP地址进行一次映射,由于域名对人友好,于是出现了这样一些问题。即存在多个域名对应同样的IP的怕况,对于中小网站来说,通常采用这种方法提供不同的Web服务。这主要出于经济的考虑,因为可以只配置一台服务器;而对于大型网站,如新浪和搜狐这些门户网站通常采用负载均衡的iP组技术,同样的域名对应于多个IP地址。一方面提高系统健壮性,一方面做到了负载均衡。
鉴于多域名对应相同IP和同域名对应多IP的倩况,通常的做法是按照域名分解任务。即只要保证不重复抓取大型网站的网页,小型网站即便重复抓取也可以接受的策略分配任务。这种分配方法将不同的域名分配给不同的爬虫抓取,某一个爬虫只抓取“指定”的一个域名集合下的网页.例如smiseo.com被“指定“交给spiderl抓取,baidu.com被“指定’交给spider2抓取,smiseobaidu.com被“指定”交给spider3抓取等.
这两种方案的主要区别可以通过下面这两个例子进一步理解。
假定baidu.com和smiseobaidu.com是两个域名不同.但IP相同的网站,假定为192.168.1.1。有这样两个网页,即http:// wwwbaidu.com/index.html和http://smiseobaidu.com/index. html.在经过域名解析后,实际上它们同为http://192.168.1.1/index.html。采用域名分解的方案,spider2和spider3就会重复抓到这个网页.但是由于这两站点信息较小。所以可以容忍因抓重而带来的损失。
反之,我们如果通过IP分配抓取任务的方案,例如smiseo.com( 71.5.7.138)被’指定”交给spiderl抓取smiseo.com(71.5.6.136)被“指定“交给spider2抓取,baidu.com(10.10.67. 208)被’指定“交给spider3抓取,smiseobaidu.com(10.10.67.208)被“指定“交 给spider3抓取.
这种分配方案,对于不同域名指向相同IP的情况。例如baidu.com和smiseobaidu.com的抓取工作都由spider3完成,没有重复抓取问题。但是smiseo.com对应多个IP,所以被分配由spiderl和spider2分别抓取,这样spiderl和spider2抓取工作就相互重复.很显然,深圳SEO属于大型网站,这种因为抓重带来的损失往往是巨大的。
通过比较,为了照顾大站按照域名分解的策略更加合理。在下载系统中,按照域名分解抓取任务(网页集合)的工作由一个称为“调度员”的模块来处理,通过域名分解将不同的网页调度给不同的爬虫进行抓取.因此,下载系统主要由爬虫和调度员构成。
形式化的调度分配方式如下:
首先假定有n个爬虫可以并行工作,并且定义一个可以提取URL域名的函数domain.例如:
URL=http://www.smiseo.com/seoyouhua/70.htmldomain(URL) =  www.smiseo.com
说明如下.
1.对于任意的URL,利用domain函数提取URL的域名.
2.用MD5签名函数签名域名,MD5 ( domain(URL)).
3.将MD5签名值对n取棋运算, int spider_no=MD5(domain(URL))%n.
4.该URL分配给编号为spider_no。的爬虫进行抓取。
由于模运算可以实现将一个全集分成多个等价类。所以等价类的并集等于全集,且一个等价类中的元素必然不属于另一个等价类中.
等价关系形式化表述如下。
令U为全集,通过某种等价关系可以将集合U分别映射到集合S1,S2 ,…,Sn上,并且满足如下两个条件。

搜索引擎模运算

通常n取2的整数幂,例如4,8,16 , 32•••取模时可以利用按位与(&)的方法快速求得,int spider_no,MD5 ( domain(URL )) & ( n-1)通常对2的挂数幂n取模,都可以用&(n-1)的方法(其中n必须是2的整数幂才可以进行这样的计算)来快速计算。
这种策略的好处在于每个爬虫的任务一尽可能地均匀分配,同一个域名必然只由一个爬虫抓取,所有爬虫的工作量组合就是全部的抓取任务。在介绍了爬虫和调度员之后,已经能够完整地理解搜索引擎下载系统的体系结构,如图3-15所示。

爬虫均衡分配抓取任务

这里我们引入了URL库和Page库这两个概念,URL库存放全部历史上曾经抓取过的URL和新增的URL , Page库存放爬虫实际抓取下来的原始网页.这样完整的合作抓取过程如下。注意下面的标号对应于上图中的数字.
1.调度员通过更新规则向URL请求一个URL抓取任务.
2.调度员计算出该URL,然后分配给编号为0的爬虫抓取。
3.爬虫0实际抓取的网页存放在Page库中。
4.爬虫0在抓取的网页中提取其他链接后反馈给调度员。
5.调度员判断网页类型,并设定初始更新时间等后存放在URL库中。继续转(1),周而复始.
在实际应用中,多采用多爬虫多调度员的体系结构,如图3-16所示。
值得注意的是,抓取的封闭性越强,对外的通信开销越小。如上图所示。假如爬虫1从smiseo.com这个种子站点开始抓取。由于总是抓取smiseo.com的网页,而这些网页总是应该归属爬虫1抓取,因此不需要和其他爬虫通信(不需要经过总调度);反过来,如果抓取的封闭性差,表示可能抓到各种各样域名下的网页,并且可能需要交给其他爬虫抓取。总调度不得不把这些信息相互转发。这样就会增加额外的通信代价.因此提高抓取的封闭性可以减少这种合作抓取带来的通信开 销,前面提到过的宽度优先的遍历方法及深度策略能够有效的保证这种抓取的封闭性。

蜘蛛完整抓取过程

最后,简单了解一下大规模网页存储的有关知识。

本文出自深圳SEO公司,未经允许不得转载:深圳SEO-微笑SEO服务公司 » 搜索引擎的下载系统
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址