第九章 图论和网络爬虫

图论的起源

欧拉证明戈尼斯堡(康德的故乡,现在是俄罗斯的加里宁格勒)七桥问题中的走法不可能实现,并写了一篇论文,一般认为这是图论的开始。

网络爬虫

我们可以从任何一个网页出发,用图的遍历算法,自动地访问到每一个网页并把它们保存起来。完成这个功能的程序叫做网络爬虫。

世界上第一个网络爬虫是由麻省理工学院的学生马休·格雷(Matthew Gray)在1993年写成的。他给自己的程序起了个名字叫做“互联网漫游者”(WWW Wander)。

构建网络爬虫的工程要点

  • 网页的遍历次序(BFS or DFS)
    • 实际的网络爬虫都是一个由成百上千甚至成千上万的服务器组成的分布式系统。对于某个网站,一般是由特定的一台或者几台服务器专门下载。这一台或几台服务器爬取某个网站时,先爬哪个网页,后爬哪个网页的调度程序原理是BFS;
    • 由于下载服务器和网站服务器建立通信需要花费额外的时间,如果在爬取大量的网站的过程中采取BFS,则需要频繁的握手;所以爬取某个网站的一台或几台机器在下载完一个网站,然后下载另一个网站的过程,类似于DFS。
    • 总结起来,网页的遍历次序不是简单的BFS or DFS,二实一个相对复杂的下载优先级排序的方法。管理这个优先级排序的子系统一般称为调度系统(Scheduler),在调度系统中需要存储那些已经发现但是尚未下载的URL,他们一般存储在一个优先级队列(Priority Queue)里。
  • 页面的分析和URL的提取

    • 当一个网页下载完成后,需要从这个网页中提取URL,把他们加入到下载队列中。这个工作在互联网早期并不难,因为当时大多数网页是直接用HTML语言书写的;但是现在很多网页是用一些脚本生成的,爬取这样的网页需要模拟浏览器访问,然后让浏览器进行解析。

    • 因此,需要做浏览器内核的工程师来写网络爬虫中的解析程序。因此,如果一些网页明明存在,但搜索引擎就是没有收录,一个可能的原因就是网络爬虫中的解析程序没有成功解析网页中不规范的脚本程序。

  • 记录哪些网易已经下载过的小本本
    • 在互联网上,一个网页可能被多个网页中的超链接所指向。为了防止一个网页被下载多次,我们需要建立一个哈希表来记录哪些网页已经下载过。
    • 但是上千台服务器建立和维护同一张哈希表不是一件容易的事,存储哈希表的服务器的通信就成了整个爬虫系统的瓶颈。
    • 对于这个问题,好的方法一般都采用了这样两个技术:
    • 明确每台下载服务器的分工,调度时一看到某个URL就知道要交给哪台服务器去下载,从而避免多个服务器对同一个URL做出是否需要下载的判断;
    • 在此基础上,批处理URL,比如每次向哈希表服务器发送一大批询问,或者每次更新一大批哈希表的内容。

随着互联网的出现,图的遍历方法一下自就有了用武之地。很多数学方法就是这样,看上去没有什么实际用途,但是随着时间的推移会一下子派上大用场。