蜘蛛
抓取策略
在爬虫系统中，待抓取URL是很关键的部分，需要爬虫抓取的网页URL在其中排列，形成一个队列结构，调度程序每次从队列头部取出URL，发送给网页下载器下载页面内容，每个新下载的网页包含的URL会追加到待抓取URL队列的末尾，这样，形成一个抓取循环，整个爬虫系统可以说是由这个队列驱动运转的。
待抓取URL队列中的页面URL顺序是如何确定的？上面所述将新下载页面中包含的链接追加到队列末尾，这虽然是一种确定队列URL顺序的方法，但并非唯一的手段，事实上，还可以采纳很多其他的技术，将队列中待抓取的URL进行排序。而爬虫的不同抓取策略，就是利用不同的方法来确定待抓取URL队列中URL优先顺序的。
爬虫的抓取策略有很多种，但不论方法如何，其基本目标一致：优先选择重要网页进行抓取。在爬虫系统中，所谓网页的重要性，其评判标准可以选择不同方法，但是大部分都是按照网页的流行性来定义的。
抓取策略方法虽然有很多，但是这里只讲解已经被证明效果较好或者是比较有代表性的解决方案，包括以下四种：宽度优先遍历策略、非完全PageRank策略、OPIC策略及大站优先策略。
01 宽度优先遍历策略
宽度优先遍历策略是一种非常简单直观且历史也很悠久的遍历方法，在搜索引擎爬虫一出现就开始采用，新提出的抓取策略往往会将这种方法作为比较基准。但值得注意的是，这种策略也是一种很强悍的方法，很多新方法实际效果不见得比宽度优先遍历策略好，所以至今这种方法实际上也是很多爬虫优先采取的抓取策略。
上文所说的“将新下载的网页包含的URL会追加到待抓取URL队列的末尾”，这就是宽度优先遍历的思想。也就是说，这种方法并没有明确提出和使用网页重要性作为衡量标准，只是机械的将新下载的网页抽取链接，并追加到待抓取URL队列中，以此作为URL的下载顺序。下图是这种策略的示意图：假设队列头部的网页是1号网页，从1号网页中抽取出3个链接分别指向2号、3号和4号，于是按照编号顺序依次放入待抓取队列中，图中网页的编号就是这个网页在待抓取队列的顺序编号，之后爬虫以此顺序进行下载。
实验表明这种策略效果很好，虽然看似机械，但实际上的网页抓取顺序基本是按照网页的重要性排序的。之所以如此，有研究人员认为：如果某个网页包含很多入链，那么更有可能被宽度优先遍历策略早早抓到，而入链数量从侧面体现了网页的重要性，即宽度优先遍历策略实际上也是隐含了一些网页优先级假设。
宽度优先遍历策略
02 非完全PageRank策略
PageRank是一种著名的链接分析算法，可以用来衡量网页的重要性。很自然地，可以想到用PageRank的思想来对URL优先级进行排序。但是这里有个问题，PageRank是个全局性算法，也就是说当所有网页都下载完毕后，其计算结果才是可靠的，而爬虫的目的就是去下载网页，在运行过程中只能看到一部分页面，所以在抓取阶段的网页是无法获得可靠的PageRank得分的。
如果我们仍然坚持在这个不完整的互联网页面子集内计算PageRank呢？这就是非完全PageRank策略的基本思路：对于已经下载的网页，加上待抓取URL队列中的URL一起，形成网页集合，在此集合内进行PageRank计算，计算完成后，将待抓取URL队列里的网页按照PageRank得分由高到低排序，形成的序列就是爬虫接下来应该依次抓取的URL列表。这也是为何称之为“非完全PageRank”的原因。
如果每次新抓取到一个网页，就将所有已经下载的网页重新计算新的非完全PageRank值，明显效率太低，在现实中是不可行的。一个折中的办法是：每当新下载的网页攒够K个，然后将所有下载页面重新计算一遍新的非完全PageRank。这样的计算效率还勉强能够接受，但是又引来了新的问题：在展开下一轮PageRank计算之前，从新下载的网页抽取出包含的链接，很有可能这些链接的重要性非常高，理应优先下载，这种情况该如何解决？非完全PageRank赋予这些新抽取出来但是又没有PageRank值的网页一个临时PageRank值，将这个网页的所有入链传导的PageRank值汇，作为临时PageRank值，如果这个值比待抓取URL队列中已经计算出来PageRank值的网页高，那么优先下载这个URL。
下图是非完全PageRank策略的一个简略示意图。我们设定每下载3个网页进行新的PageRank计算，此时已经有{P1,P2,P3}3个网页下载到本地，这3个网页包含的链接指向{P4,P5,P6},形成了待抓取URL队列。如何决定下载顺序？将这6个网页形成新的集合，对这个集合计算PageRank值，这样P4、P5和P6就获得自己对应的PageRank值，由大到小排序，即可得出其下载顺序。这里可以假设其下载顺序为：P5、P4、P6，当下载P5页面后抽取出链接，指向页面P8，此时赋予P8临时PageRank值，如果这个值大于P4和P6的PageRank值，则接下来优先下载P8。如此不断循环，即形成了非完全PageRank策略的计算思路。
非完全PageRank看上去复杂，那么效果是否一定优于简单的宽度优先遍历策略呢？不同的实验结果存在着争议，有些结果表明非完全PageRank结果略优，有些实验结果却恰恰相反，更有研究人员指出：非完全PageRank计算得出的重要性与完整的PageRank计算结果差异很大，不应作为衡量抓取过程中URL重要性计算的依据。
非完全PageRank策略
03 OPIC策略
OPIC的字面含义是“在线页面重要性计算”，可以将其看作是一种改进的PageRank算法。在算法开始之前，每个互联网页面都给予相同的“现金”，每当下载了某个页面P后，P将自己拥有的“现金”平均分配给页面中包含的链接页面，把自己的“现金”清空。而对于待抓取URL队列中的网页，则根据其手头中拥有的现金金额多少排序，优先下载现金最充裕的网页。OPIC从大的框架上与PageRank思路基本一致，区别在于：PageRank每次需要迭代计算，而OPIC策略不需要迭代过程，所以计算速度远远快于PageRank，适合实时计算使用。同时，PageRank在计算时，存在向无链接关系网页的远程跳转过程，而OPIC没有这一计算因子。实验结果表明，OPIC是种较好的重要性衡量策略，效果略优于宽度优先遍历策略。
04 大站优先策略
大站优先策略思路很直接：以网站为单位衡量网页重要性，对于待抓取URL队列中的网页，根据所属网站归类，如果哪个网站等待下载的页面最多，则优先下载这些链接，其本质思想倾向于优先下载大型网站，因为大型网站往往包含更多的页面。鉴于大型网站往往是著名企业的内容，其网页质量一般较高，所以这个思路虽然简单，但是有一定依据。实验表明这个算法效果也要略优于宽度优先遍历策略。
网页更新策略
互联网的动态性是其显著特征，随时都有新出现的页面，页面内容被更改或者原本存在的页面被删除。对于爬虫来说，并非将网页抓取到本地就算完成任务，也要体现出互联网的这种动态性。本地下载的页面可看作是互联网页面的“镜像”，爬虫要尽可能保证一致性。可以假设一种情况：某个网页已被删除或者内容做出重大改动，而搜索引擎对此擎茫然不知，仍按照旧有内容排序，将其作为搜索结果提供给用户，其用户体验之糟糕不言而喻。所以，对于已经抓取过的网页，爬虫还要负责保持其内容和互联网页面的同步，这取决于爬虫所采取的网页更新策略。
网页更新策略的任务是要决定何时重新抓取已经下载的网页，尽可能使得本地下载网页和互联网原始页面内容保持一致。常用的网页更新策略有3种：历史参考策略、用户体验策略和聚类抽样策略。
01历史参考策略
历史参考策略是最直观的一种更新策略，它建立于如下假设之上：过去频繁更新的网页，那么将来也会频繁更新。所以，为了预估某个网页何时进行更新，可以通过参考历史更新的情况来做出决定。
这种方法往往利用泊松过程来对网页的变化进行建模，根据每个网页过去的变动情况，利用模型预测将来何时内容会再次发生变化，以此来指导爬虫的抓取过程。不同方法，侧重点不同，比如有的研究将一个网页划分成不同的区域，抓取策略应该忽略掉广告栏或者导航栏这种不重要区域的频繁变化，而集中关注内容的变化探测和建模上。
02用户体验策略
一般来说，搜索引擎用户提交查询后，相关的搜索结果可能成千上万，而用户没有耐心等待查看排在后面的搜索结果，可能只看前3页搜索内容。用户体验策略就是利用用户的这个特点来设计更新策略的。
这种更新策略是以用户体验为中心，即使本地索引的网页内容是过时的，但是如果不影响用户体验，那么晚些时候更新这些过时的网页也未尝不可。所以判断一个网页何时更新为好，，取决于这个网页内容变化所带来搜索质量的变化（往往采用搜索结果排名的变化来衡量），影响越大的网页，则应该越快更新。
用户体验策略保存网页的多个历史版本，并根据过去每次内容变化对搜索质量的影响，得出一个平均值，以此作为判断爬虫重新抓取该网页时机的参考依据，对于影响越厉害的网页，则越优先调度重新抓取。
03聚类抽样策略
上面介绍的两种网页更新策略严重依赖网页的历史更新信息，因为这是能够进行后续计算的基础。但是在现实中，为每个网页保存其历史信息，搜索系统会大量增加额外负担。从另外一个角度考虑，如果是首次抓取到的网页，因为没有历史信息，所以也就无法按照这两种思路去预估更新周期。聚类抽样策略正是为了解决上述缺点而提出的。
聚类抽样策略认为：网页具有一些属性，根据这些属性可以预测其更新周期，具有相似属性的网页，其更新周期也是类似的。于是，可以根据这些属性将网页归类，同一类别内的网页具有相同的更新频率。为了计算某个类别的更新周期，只需对类别内网页进行采样，以这些采样网页的更新周期作为该类别内所有网页的更新周期。与之前叙述的两种方法比较，这种策略一方面无须为每个网页保存历史信息；另一方面，对于新网页，即使没有历史信息，也可以根据其所属类别来对其进行更新。
下面这张图描述了聚类抽样策略的基本流程，首先根据网页表现出的特征，将其聚合成不同的类别，每个类别内的网页具有相似的更新周期。从类别中抽取出一部分最有代表性的网页（一般抽取最靠近类中心的那些网页），对这些网页计算更新周期，那么这个更新周期使用于该类别内的所有网页，之后可根据网页所属类别来决定其更新周期。
聚类抽样策略
网页更新周期的属性特征划分为两大类：静态特征和动态特征。静态特征包括：页面的内容、图片数量，页面大小、链接深度、PageRank值等十几种；而动态特征体现了静态特征随时间变化的情况，比如图片数量的变化、入链出链的变化情况等。根据这两类特征，即可对网页进行聚类。
上图是一个较为通用的流程，不同算法在一些细节上有差异。比如有些研究直接省略聚类这个步骤，而是以网站作为聚类单位，即假设属于同一个网站的网页具有相同的更新周期，对网站内页面进行抽样，计算更新周期，之后网站内所有网页以这个更新周期为准。这个假设虽然粗糙，因为很明显同一网站内网页更新周期差异很大，但是可以省略掉聚类这个步骤，在计算效率方面会更高。
相关实验表明，聚类抽样策略效果好于前两种更新策略，但是对以亿计的网页进行聚类，其难度也是非常巨大的。
閱讀更多 努力拼搏的80後 的文章
