keyword：广度优先搜索,深度优先搜索,爬虫

上一章（读书笔记：数学之美-简单之美 布尔代数和搜索引擎） 中提到了搜索引擎要完成的三件事情，本章将介绍如何下载互联网上的网页。

图论

本章从欧拉七桥问题引出了关于图的广度优先遍历和深度优先遍历。 所谓图，可以理解为由一些节点和连接这些节点的弧组成。 那么图的遍历算法就是如何通过弧来访问图中的各个节点。 图的遍历算法可以分为以下两种：

• 广度优先搜索 （Breadth-First Search，简称BFS）

  按层进行搜索，优先访问与每个节点直接连接的其他节点。不能递归实现，需要使用队列。

• 深度优先搜索 （Depth-First Search，简称DFS）

  类似于树的前序遍历，优先对纵深方向进行搜索。可以递归实现，非递归需要使用栈。

两种算法具体的思想和伪代码可以参考：深度优先遍历与广度优先遍历

网络爬虫

互联网虽然很复杂，但其实结构就是一张巨大的图：把每个网页当作一个节点，把超链接当作连接网页的弧。 理论上，我们可以从任何一个网页出发，用图的遍历算法，自动地访问到每一个网页并把它们存起来。 完成这个功能的程序就叫做网络爬虫（Web Crawlers）。

网络爬虫下载整个互联网的过程可以简单概括为：从一家门户网站首页出发，下载这个网页，分析提取页面文本中的所有超链接， 再依次下载这些超链接的网页，分析提取这些网页中的超链接，让计算机不停地做下去，理论上就可以下载整个互联网了。 为了避免重复下载一个页面，需要使用散列表（Hash Table，也叫哈希表）来记录下载过的网页信息。

但是现实中互联网非常庞大，不可能通过一台或者几台计算机来完成下载任务。因此，一个商业的网络爬虫需要有成千上万个服务器， 并且通过高速网络连接起来。而随之而来的问题是如何高效、准确地协同调度这个大规模集群。

构建网络爬虫的工程要点

1. 使用BFS还是DFS

   理论上，这两个算法都能够在相同的时间里爬下整个“静态”的互联网，但是现实中，受限于时间和互联网的变化，搜索引擎的网络爬虫更应该考虑 “如何在有限的时间里最多地爬下最重要的网页”。显然每个网站最重要的网页应该是它的首页，在极端情况下，如果爬虫非常小，那么应该让它去下载所有网站的首页。 如果爬虫在扩大些，应该爬下从首页直接链接的网页。在这个前提下，明显BFS优于DFS。

   再考虑爬虫的分布式结构以及网络通信的握手成本，实际网络爬虫都是由上千、上万台服务器组成的分布式系统。 对于某个网站，一般都是由一台或者几台服务器专门下载，这些服务器下载完一个网站后才会进入下一个网站，而不是每个网站下轮流下载5%后再回头下载第二批。 这样可以避免握手次数太多。

   总结，网络爬虫对网页遍历的次序不是简单的BFS或者DFS，而是有一个相对复杂的下载优先级排序的方法，管理整个优先级排序的子系统一般成为调度系统（Scheduler）。 再调度系统中需要存储那些已经发现但是尚未下载的网页的URL，它们一般存在一个优先队列（Priority Queue）里。这在工程上和BFS更加相似。 因此，爬虫中的BFS成分更多些。

2. 页面分析和URL提取

   面对的问题为目前很多网页中的重要信息都是使用脚本语言（如JavaScript）生成的，打开网页源代码，URL不是直接可见的文本，需要运行相关脚本才能得到结果。 因此，网络爬虫的页面分析就变得复杂很多，需要模拟运行一个网页，这涉及到浏览器内核方面的知识。 如果发现爬虫中解析不到想要的内容，一个可能就是爬虫中的解析程序没能成功解析网页中不规范的脚本。

3. 记录下载页面的URL表

   在一台下载服务器建立和维护一张散列表并不难，但是如果成千上万台服务器一起下载，维护一张统一的散列表就不那么简单了。 首先，这张散列表可能大到一台服务器存储不下。其次，每个下载服务器在开始下载前和完成下载后都需要访问和维护这张表， 以免不同服务器做重复工作，因此这个存储散列表的服务器的通信就成了整个爬虫系统的瓶颈。

   这里举出的较好的降低通信次数解决方法包括两点：

   • 首先，明确每台下载服务器的分工，即在调度时一看到某个URL就知道交给哪台服务器去下载，以免每台服务器都要重复判断某个URL是否需要下载。

   • 然后，再明确分工的基础上，判断URL是否下载就可以批处理了，即每次向散列表所在服务器发送一大批查询或者更新内容。