2.1.1　网络爬虫

首先来看一下网络爬虫的具体工作模式和分类。其主要的工作流程是从一个或若干个初始网页的地址URL（Uniform Resource Locator）开始，获得初始网页上的URL列表。然后在抓取网页的过程中，不断地从当前页面上抽取新的URL放入待爬行队列，直到满足系统的停止条件为止。从这个流程中可以看出，如何有效地获取新的URL，对于爬虫执行成功与否非常关键，从这个角度可以将网页获取的策略分为几个大类：深度优先、宽度优先和最佳优先三种。

1.深度优先

该策略从起始网页开始，选择一个URL进入，分析这个网页中的URL，然后再选择另一个URL进入。如此一个链接一个链接地抓取下去，直到处理完整条路线之后再处理下一条路线，图2-1显示了获取的先后顺序，其中每个节点代表一个网页，节点中的数字标号表示该网页的唯一ID，节点旁边的数字标号代表该网页被访问的名次，每条实线代表网页之间的链接，每条虚线代表访问的顺序。对于熟悉计算机数据结构的读者而言，深度优先的抓取策略可以用栈（Stack）来实现，步骤如下：

1）将初始网页节点压入栈中。

2）每次从栈中弹出一个节点，搜索在它下一级的所有节点。

3）将第2步中新发现的节点压入栈中。

4）重复第2步和第3步，直到没有发现新的网页节点为止。

栈的处理过程参见图2-2。

深度优先策略的设计较为简单，但是它面临一个最大的麻烦：陷入（Trapped）问题。门户网站提供的链接往往是最具价值的，评级也很高，但随着每一层的深入，网页的价值就会相应地有所下降。这就暗示了重要网页通常距离种子较近，而过度深入抓取到的网页却价值很低。同时，这种策略下抓取的深度将会直接影响抓取命中率及抓取效率，合理的控制深度是该种策略的关键。因此，相对于其他宽度优先和最佳优先策略而言，此种策略很少被使用。

2.宽度优先

宽度优先又称为广度优先，这个策略是指在抓取过程中，只有在完成当前层次的搜索之后，才进行下一层次的搜索。该算法的设计和实现也是比较简单的，图2-3显示了获取的先后顺序。同样，图2-3中的每个节点代表一个网页，节点中的数字标号表示该网页的唯一ID，节点旁边的数字标号代表该网页被访问的名次，每条实线代表网页之间的链接，每条虚线代表访问的顺序。相对于深度优先而言，宽度优先的策略更容易理解，就好比银行排队办理业务，先来的人先处理。因此，我们可以采用数据结构中的队列（Queue）来实现，步骤如下：

1）将初始网页节点压入栈中。

2）每次从队列首位取出一个节点，搜索在它下一级的所有节点。

3）将第2步中新发现的节点加入队列的末尾。

4）重复第2步和第3步，直到没有发现新的网页节点为止。

队列的处理过程参见图2-4。

当下，为了覆盖尽可能多的网页，一般使用宽度优先搜索方法。相对于深度优先的搜索，该策略不太会陷入低价值的非核心页面搜索上。但是，对于聚焦于某个网站，或者是网站局部频道的特殊爬取需求，宽度优先可能就不如深度优先适合。

3.最佳优先

这种策略通常也称为聚焦、定向爬取，它会按照一定的网页分析算法，预测候选URL与目标网页的相似度，或与主题的相关性，并选取相似度最高的若干个URL进行抓取。当需要爬取的网页数量很庞大的时候，无论是深度优先还是宽度优先可能都不能高效地获取用户所关心的内容，而最佳优先策略只访问经过网页分析算法预测为“相关”的网页，在一定程度上缓解了之前两种策略重“量”不重“质”的局面。

不过，这里又引入了一个新的问题，就是如何判断新获取的网页和用户定义的候选网页之间的相似度呢？这在信息检索的相关性领域中有比较透彻的研究，本章先简单地介绍一下相似度计算的基础概念：相似度或相关性的衡量就是依据一定的模型，预测两个数据对象之间的相似程度，这里主要是注重文本的相似性。常见的模型有布尔模型、基于偏序的布尔模型、向量空间模型、概率模型和语言模型，等等。

布尔模型是最简单的方法，可用于比较不同的文本之间是否存在共同的关键词。如果有就认为是相关或相似的，如果没有就认为不相关或不相似。不过，它的弱点就是对相关性的刻画不足。相关与否是一个模糊的概念，仅仅通过“相关”和“不相关”两个值来表示，未免过于绝对，况且也没有办法体现其中的区别。因此为了增强布尔模型，还需要考虑每个关键词的权重，如今使用最为普遍的是tf-idf机制。这里的tf表示词频（term frequency），就是一个词t在文章d中（或者是文章的某个字段中）出现的次数。一般的假设是，某个词在文章中的tf越高，表示该词t对于该文档d而言越重要。同时，另外一个常用的是idf，它表示逆文档频率（inverse document frequency）。首先，df表示文档频率（document frequency），即文档集合c中出现某个词t的文档数量。也就是说，如果某个文档出现了词t，那么df就增加并且只增加1次。一般的假设是，某个词t在文档集合c中的df越大，那么其重要性越低，反之则越高，因此将df转化为其倒数idf来表达这个理念。如此一来，布尔模型也能获得不同的相关性得分。

下面再介绍一个比排序布尔模型稍微复杂一点的向量空间模型。此模型的重点就是将某个文档转换为一个向量，向量的维度是单词，而每个维度的值通常也是用tf-idf来表示的。这样，相关性问题就转化为计算查询向量和文档向量之间的相似度问题了。在实际处理中最常用的相似性度量方式是余弦距离。其好处是，其值正好是一个介于0到1之间的数，如果向量一致就是1，如果正交就是0，符合相似度百分比的特性。相对于标准的布尔数学模型，向量空间模型具有不少优点，包括基于线性代数的简单模型，非常容易理解；词组的权重可以不是二元的，例如可以采用tf-idf这种机制；允许计算文档和索引之间的连续相似程度和基于此的排序等。当然，基本的向量空间模型也存在很多不足，例如对于很长的文档，相似度得分就会不理想；没有考虑到单词所代表的语义，还是限于精准匹配；没有考虑词在文档中出现的顺序，等等。

近几年另一些流行的相似度模型是概率模型和语言模型。它们本身其实并不是新兴的技术，之前在机器翻译、语音识别和中文分词中就已经得到了成功的应用。如果对这些模型的具体内容感兴趣，可以参考5.2节。

不管是哪种模型，垂直搜索引擎大多采用最佳优先的策略来提高定向爬虫的效率，使得数据收集和更新频率的大幅增加成为可能。

除了收集互联网中世界各地的信息，网络爬虫的一个重要附加价值就是可以帮助人们构建网络图（Web Graph）。如果将每个网页看作图论里的一个节点，而网页间的超链接表示图论里的边，那么可以得到类似图2-5的Web网络图，网络爬虫不断获取新页面的过程就是遍历这些节点和边的过程，构建这种图是非常自然和便捷的。网络图的链接分析和挖掘在搜索引擎的排序中起到了举足轻重的作用，最为著名的是PageRank和HITS算法。

Google的创始人拉里佩奇和谢尔盖布林于1998年发明了PageRank技术，并成为Google区别于当时搜索引擎的重要标志之一。其模型的假设是“随机冲浪者”，冲浪者从某张网页出发，根据Web图中的链接关系随机访问。在每个步骤中，他/她都会从当前网页的链出网页中随机选取一张作为下一步访问的目标。在整个Web图中，绝大部分的网页节点都会有链入和链出。那么冲浪者就可以永不停歇地冲浪，持续在图中走下去。PageRank的基本假设就是：在随机访问的过程中，越是被频繁访问的链接越重要。可以看出，每个节点的PageRank值取决于Web图的链接结构。假如一个页面节点有很多的链入链接，或者是链入的网页有较高的被访问率，那么它也将会有更高的被访问概率。同时，PageRank引入了随机的跳转操作，也就是说假设冲浪者不按照Web图的拓扑结构走下去，只是随机挑选了一张网页进行跳转。这样的处理是类比人们打开一张新网页的行为，也是符合实际情况的，避免了信息孤岛的形成。

另一个有名的链接分析算法是HITS，它是由康奈尔大学的Jon Kleinberg博士于1998年提出的。HITS算法和PageRank最大的区别在于：它将每张网页节点的值分为两个，包括权威值（authority）和中心值（hub）。Web上有很多人工编辑的导航性网页，如各种网址导航，其本身不会详细介绍某个主题，但是会指向富含权威内容的网站，这种称之为中心。相对而言，如果一张网页本身不具备导航功能，就是详细介绍某个主题的，那么就称之为权威。一张网页可以同时拥有中心和权威的身份，只是得分有高低。HITS假设一个优质的中心网页会指向更多优质的权威网页，而一个优质的权威网页也会被更多中心网页所指向。因此，我们可以类似PageRank给出中心值和权威值的循环定义，并且通过迭代计算来求解，最终达到收敛的状态。关于链接的分析，更多具体的内容将会在5.5节中进一步探讨。

最后，我们来看一下爬虫实现的大致系统架构，如图2-6所示。

从图2-6可以看出，爬虫的工作流程为：首先根据种子网页的URL，形成初始的待爬取URL集合，然后依次读取并从互联网上下载、保存、分析并获取该网页中新的URL链接。对于新的URL，根据深度、宽度和最佳优先的不同策略，放入到待爬取的集合。如果是基于相似度的最佳定向策略，此时还需要考虑相似度的衡量。对于已经处理完毕的网页，将其内容存入数据库作为镜像缓存。而其URL地址则放入已爬取的集合，以避免重复。需要注意的是，在很多应用场景下，网页爬取仅仅执行一次是不够的，需要定期更新其内容。因此已获取的集合需要定期更新，或者是针对不同类型的网页设置更为精细的更新计划。例如，像时事新闻这种网站，消息的及时性要求很高，因此可以加快对该类型站点的爬取频率，缩短更新的周期。随着整个流程不断的循环和往复，互联网上的数据会不断地收集和存储。由于互联网数据规模庞大的难以想象，所以爬虫通常需要不停地行走，以发现新的大陆，探索未知的信息世界。

“小明哥，那网络爬虫对于我们创业公司而言有什么价值呢？”

“对于创业公司而言，利用现有的外部资源是飞速发展的捷径。因此，网络爬虫将被广泛地运用在互联网世界的数据获取上。例如，对于你们的O2O电商创业而言，可以让爬虫获取某些地区的气候数据，以便于之后做基于天气预报的个性化推荐和精准营销。此外，爬虫还可以从主流电商网站爬取其商品目录结构，以及最新的市场价格，等等。”

在了解网络爬虫的基础知识和一些应用场景之后，我们可以尝试自己动手，搭建最简单的爬虫系统。当然，我们没有必要从零开始，下面即将介绍两个比较著名的开源系统——Apache Nutch和Heritrix，它们能帮助人们快速设计和实现自己的网络爬虫。