python考点：网络爬虫有哪些爬行策略？

　　网络爬虫有哪些爬行策略？网络爬虫（web crawler）爬行策略如下：

　　下述的三种网络特征，造成了设计网页爬虫抓取策略变得很难：

　　它巨大的数据量;

　　它快速的更新频率;

　　动态页面的产生

　　它们三个特征一起产生了很多种类的爬虫抓取链接。

　　巨大的数据量暗示了爬虫，在给定的时间内，只可以抓取所下载网络的一部分，所以，它需要对它的抓取页面设置优先级;快速的更新频率说明在爬虫抓取下载某网站一个网页的时候，很有可能在这个站点又有新的网页被添加进来，或者这个页面被更新或者删除了。

　　最近新增的很多页面都是通过服务器端脚本语言产生的，无穷的参数组合也增加了爬虫抓取的难度，只有一小部分这种组合会返回一些独特的内容。例如，一个很小照片存储库仅仅通过get方式可能提供就给用户三种操作方式。如果这里存着四种分类方式，三种缩略图方式，两种文件格式，和一个禁止用户提供内容的选项，那么，同样的内容就可以通过48种方式访问。这种数学组合给网络爬虫创造的难处就是，为了获取不同的内容，他们必须筛选无穷仅有微小变化的组合。

　　正如爱德华等人所说的：“用于检索的带宽不是无限的，也不是免费的;所以，如果引入衡量爬虫抓取质量或者新鲜度的有效指标的话，不但伸缩性，连有效性都将变得十分必要”(爱德华等人，2001年)。一个爬虫就必须小心的选择下一步要访问什么页面。网页爬虫的行为通常是四种策略组合的结果。

　　♦ 选择策略，决定所要下载的页面;

　　♦ 重新访问策略，决定什么时候检查页面的更新变化;

　　♦ 平衡礼貌策略，指出怎样避免站点超载;

　　♦ 并行策略，指出怎么协同达到分布式抓取的效果;

　　1.1 选择策略：

　　就现在网络资源的大小而言，即使很大的搜索引擎也只能获取网络上可得到资源的一小部分。由劳伦斯河盖尔斯共同做的一项研究指出，没有一个搜索引擎抓取的内容达到网络的16%(劳伦斯河盖尔斯，2001)。网络爬虫通常仅仅下载网页内容的一部分，但是大家都还是强烈要求下载的部分包括最多的相关页面，而不仅仅是一个随机的简单的站点。

　　这就要求一个公共标准来区分网页的重要程度，一个页面的重要程度与他自身的质量有关，与按照链接数、访问数得出的受欢迎程度有关，甚至与他本身的网址(后来出现的把搜索放在一个顶级域名或者一个固定页面上的垂直搜索)有关。设计一个好的搜索策略还有额外的困难，它必须在不完全信息下工作，因为整个页面的集合在抓取时是未知的。

　　Cho等人(Cho et al，1998)做了第一份抓取策略的研究。他们的数据是斯坦福大学网站中的18万个页面，使用不同的策略分别模仿抓取。排序的方法使用了广度优先，后链计数，和部分pagerank算法。计算显示，如果你想要优先下载pagerank高的页面，那么，部分PageRank策略是比较好的，其次是广度优先和后链计数。并且，这样的结果仅仅是针对一个站点的。

　　Najork和Wiener (Najork and Wiener, 2001)采用实际的爬虫，对3.28亿个网页，采用广度优先研究。他们发现广度优先会较早的抓到PageRank高的页面(但是他们没有采用其他策略进行研究)。作者给出的解释是：“最重要的页面会有很多的主机连接到他们，并且那些链接会较早的发现，而不用考虑从哪一个主机开始。”

　　Abiteboul (Abiteboul 等人, 2003)，设计了一种基于OPIC(在线页面重要指数)的抓取战略。在OPIC中，每一个页面都有一个相等的初始权值，并把这些权值平均分给它所指向的页面。这种算法与Pagerank相似，但是他的速度很快，并且可以一次完成。OPIC的程序首先抓取获取权值最大的页面，实验在10万个幂指分布的模拟页面中进行。并且，实验没有和其它策略进行比较，也没有在真正的WEB页面测试。

　　Boldi等人(Boldi et al., 2004)的模拟检索实验进行在 从.it网络上取下的4000万个页面和从webbase得到的1亿个页面上，测试广度优先和深度优先，随机序列和有序序列。比较的基础是真实页面pageRank值和计算出来的pageRank值的接近程度。令人惊奇的是，一些计算pageRank很快的页面(特别明显的是广度优先策略和有序序列)仅仅可以达到很小的接近程度。

　　Baeza-Yates等人(Baeza-Yates et al., 2005) 在从.gr域名和.cl域名子网站上获取的300万个页面上模拟实验，比较若干个抓取策略。结果显示OPIC策略和站点队列长度，都比广度优先要好;并且如果可行的话，使用之前的爬行抓取结果来指导这次抓取，总是十分有效的。

　　Daneshpajouh等人(Daneshpajouh et al., 2008)设计了一个用于寻找好种子的社区。它们从来自不同社区的高PageRank页面开始检索的方法，迭代次数明显小于使用随机种子的检索。使用这种方式，可以从以前抓取页面之中找到好的种子，使用这些种子是十分有效的。

　　1.1.1 限定访问链接

　　一个爬虫可能仅仅想找到html页面的种子而避免其他的文件类型。为了仅仅得到html的资源，一个爬虫可以首先做一个http head的请求，以在使用request方法获取所有的资源之前，决定这个网络文件的类型。为了避免要发送过多的head请求，爬虫可以交替的检查url并且仅仅对以html，htm和反斜杠结尾的文件发送资源请求。这种策略会导致很多的html资源在无意中错过，一种相似的策略是将网络资源的扩展名同已知是html文件类型的一组扩展名(如.html,.htm,.asp,.php,.aspx,反斜杠)进行比较。

　　一些爬虫也会限制对任何含有“?”的资源(这些是动态生成的)进行获取请求，以避免蜘蛛爬行在某一个站点中陷入下载无穷无尽的URL的困境。

　　1.1.2 路径检索

　　一些爬虫会尽可能多的尝试下载一个特定站点的资源。Cothey(Cothey,2004)引入了一种路径检索的爬虫，它会尝试抓取需要检索资源的所有URL。例如，给定一个种子地址：它将会尝试检索/hamster/menkey/,/hamster/和/ 。Cothey发现路径检索对发现独立资源，或者一些通常爬虫检索不到的的连接是非常有效的。

　　一些路径检索的爬虫也被称为收割机软件，因为他们通常用于收割或者收集所有的内容，可能是从特定的页面或者主机收集相册的照片。

　　1.1.3 聚焦抓取

　　爬虫所抓取页面的重要程度也可以表述成它与给定查询之间相似程度的函数。网络爬虫尝试下载相似页面，可以称为聚焦检索或者主题检索。关于主题检索和聚焦检索的概念，最早是由Menczer(Menczer 1997; Menczer and Belew, 1998)和Chakrabarti等人首先提出来的(Chakrabarti et al., 1999)。

　　聚焦检索的主要问题是网页爬虫的使用环境，我们希望在实际下载页面之前，就可以知道给定页面和查询之间的相似度。一个可能的方法就是在链接之中设置锚点，这就是在早期时候，Pinkerton(Pinkerton，1994)曾经在一个爬虫中采用的策略。Diligenti等人(Diligenti等人，2000)建议使用已经抓取页面的内容去推测查询和未访问页的相似度。一个聚焦查询的表现的好坏主要依赖于查询主题内容的丰富程度，通常还会依赖页面查询引擎提供的查询起点。

　　1.1.4 抓取深层的网页

　　很多的页面隐藏的很深或隐藏在在看不到的网络之中。这些页面通常只有在向数据库提交查询的时候才可以访问到，如果没有链接指向他们的话，一般的爬虫是不能访问到这些页面的。谷歌站点地图协议和mod oai(Nelson等人，2005)尝试允许发现这些深层次的资源。

　　深层页面抓取器增加了抓取网页的链接数。一些爬虫仅仅抓取形如

　　1.1.5 WEB3.0检索

　　Web3.0为下一代搜索技术定义了更先进的技术和新的准则，可以概括为语义网络和网站模板解析的概念。第三代检索技术将建立在人机巧妙的联系的基础上。

　　1.2重新访问策略

　　网络具有动态性很强的特性。抓取网络上的一小部分内容可能会花费真的很长的时间，通常用周或者月来衡量。当爬虫完成它的抓取的任务以后，很多操作是可能会发生的，这些操作包括新建，更新和删除。

　　从搜索引擎的角度来看，不检测这些事件是有成本的，成本就是我们仅仅拥有一份过时的资源。最常使用的成本函数，是新鲜度和过时性(2000年，Cho 和Garcia-Molina)

　　新鲜度：这是一个衡量抓取内容是不是准确的二元值。在时间t内，仓库中页面p的新鲜度是这样定义的：

　　新鲜度 过时性:这是一个衡量本地已抓取的内容过时程度的指标。在时间t时，仓库中页面p的时效性的定义如下：

　　过时性 在页面抓取中，新鲜度和过时性的发展

　　Coffman等人(Edward G. Coffman，1998)是从事爬虫对象定义的，他们提出了一个相当于新鲜度的概念，但是使用了不同的措词：他们建议爬虫必须最小化过时页面部分。他们指出网络爬行的问题就相当于多个队列，一个投票系统;这里，爬虫是服务器，不同的站点是队列。页面修改是到达的顾客，页面切换的时间是页面进入一个单一站点的间隔。在这个模型下，每一个顾客在投票系统的平均时间，相当于爬虫的平均过时性。

　　爬虫的目标是尽可能高的提高页面的新鲜度，同时降低页面的过时性。这一目标并不是完全一样的，第一种情况，爬虫关心的是有多少页面时过时的;在第二种情况，爬虫关心的页面过时了多少。

　　两种最简单的重新访问策略是由Cho和Garcia-Molina研究的(Cho 和Garcia-Molina，2003)：

　　统一策略：使用相同的频率，重新访问收藏中的所有的链接，而不考虑他们更新频率。

　　正比策略：对变化越多的网页，重新访问的频率也越高。网页访问的频率和网页变化的频率直接相关。

　　(两种情况下，爬虫的重新抓取都可以采用随机方式，或者固定的顺序)

　　Cho和Garcia-Molina证明了一个出人意料的结果。以平均新鲜度方式衡量，统一策略在模拟页面和真实的网络抓取中都比正比策略出色。对于这种结果的解释是：当一个页面变化太快的时候，爬虫将会将会在不断的尝试重新抓取而浪费很多时间，但是却还是不能保证页面的新鲜度。

　　为了提高页面的新鲜度，我们应该宣判变化太快的页面死罪(Cho和Garcia-Molina, 2003a)。最佳的重新访问策略既不是统一策略，也不是正比策略;保持平均页面新鲜度高的最佳方法策略包括忽略那些变化太快的页面，而保持页面平均过时性低的方法则是对每一页按照页面变化率单调变化的策略访问。两种情况下，最佳的策略较正比策略，都更接近统一策略。正如Coffman等人(Edward G.Coffman，1998)所注意到的：“为了最小化页面过时的时间，对任一个页面的访问都应该尽可能的均匀间隔地访问。”对于重新访问的详尽的策略在大体上是不可以达到的，但是他们可以从数学上得到，因为他们依赖于页面的变化。(Cho和Garcia-Molina,2003a)指出指数变化是描述页面变化的好方法，同时(Ipeirotis等人，2005)指出了怎么使用统计工具去发现适合这些变化的参数。注意在这里的重新访问策略认为每一个页面都是相同的(网络上所有的页面价值都是一样的)这不是现实的情况，所以，为了获取更好的抓取策略，更多有关网页质量的信息应该考虑进去。

　　1.3 平衡礼貌策略

　　爬虫相比于人，可以有更快的检索速度和更深的层次，所以，他们可能使一个站点瘫痪。不需要说一个单独的爬虫一秒钟要执行多条请求，下载大的文件。一个服务器也会很难响应多线程爬虫的请求。

　　就像Koster(Koster，1995)所注意的那样，爬虫的使用对很多工作都是很有用的，但是对一般的社区，也需要付出代价。使用爬虫的代价包括：

　　 网络资源：在很长一段时间，爬虫使用相当的带宽高度并行地工作。

　　 服务器超载：尤其是对给定服务器的访问过高时。

　　 质量糟糕的爬虫，可能导致服务器或者路由器瘫痪，或者会尝试下载自己无法处理的页面。

　　 个人爬虫，如果过多的人使用，可能导致网络或者服务器阻塞。

　　对这些问题的一个部分解决方法是漫游器排除协议(Robots exclusion protocol)，也被称为robots.txt议定书(Koster，1996)，这份协议对于管理员指明网络服务器的那一部分不能到达是一个标准。这个标准没有包括重新访问一台服务器的间隔的建议，虽然访问间隔是避免服务器超载的最有效的办法。最近的商业搜索软件，如Ask Jeeves，MSN和Yahoo可以在robots.txt中使用一个额外的 “Crawl-delay”参数来指明请求之间的延迟。

　　对连接间隔时间的第一个建议由Koster 1993年给出，时间是60秒。按照这个速度，如果一个站点有超过10万的页面，即使我们拥有零延迟和无穷带宽的完美连接，它也会需要两个月的时间来下载整个站点，并且，这个服务器中的资源，只有一小部分可以使用。这似乎是不可以接受的。

　　Cho(Cho和Garcia-Molina, 2003)使用10秒作为访问的间隔时间，WIRE爬虫(Baeza-Yates and Castillo, 2002)使用15秒作为默认间隔。MercatorWeb(Heydon 和Najork, 1999)爬虫使用了一种自适应的平衡策略：如果从某一服务器下载一个文档需要t秒钟，爬虫就等待10t秒的时间，然后开始下一个页面。Dill等人 (Dill et al., 2002) 使用1秒。

　　对于那些使用爬虫用于研究目的的，一个更详细的成本-效益分析是必要的，当决定去哪一个站点抓取，使用多快的速度抓取的时候，伦理的因素也需要考虑进来。

　　访问记录显示已知爬虫的访问间隔从20秒钟到3-4分钟不等。需要注意的是即使很礼貌，采取了所有的安全措施来避免服务器超载，还是会引来一些网络服务器管理员的抱怨的。Brin和Page注意到：运行一个针对超过50万服务器的爬虫，会产生很多的邮件和电话。这是因为有无数的人在上网，而这些人不知道爬虫是什么，因为这是他们第一次见到。(Brin和Page，1998)

　　1.4 并行策略

　　一个并行爬虫是并行运行多个进程的爬虫。它的目标是最大化下载的速度，同时尽量减少并行的开销和下载重复的页面。为了避免下载一个页面两次，爬虫系统需要策略来处理爬虫运行时新发现的URL，因为同一个URL地址，可能被不同的爬虫进程抓到。