浅谈从离散数学分支的图论到网络爬虫的探索（下）

封面｜左无向图，右有向图

本篇预计阅读时长12min，难度 🌟🌟🌟🌟

大家好，我是科学羊🐑，这里是数学篇第五季第21篇，今天继续谈图论。

接上篇（建议先阅读上篇），上篇我们已经谈了关于图论的基础知识，这篇我们来谈谈它在计算机算法方面的应用。

我们就从互联网开始谈起，我们的互联网虽看似复杂，但其实你可以把它理解一个很庞大的图（图论）结构。

我们可以将每个网页视为一个节点，把网页之间的超链接视为连接这些节点的边。

可能你平时也注意到网页中那些带下划线的蓝色文字背后其实隐藏着相应的网址，当你点击时，浏览器便通过这些网址跳转到相关的网页。

这些网址称为“超链接”。

借助超链接，我们可以从任何一个网页出发，通过图的遍历算法，自动访问每一个网页并将它们存储起来。

完成这一任务的程序叫作网络爬虫（Web Crawlers），有时也称为“机器人”（Robot）。

世界上第一个网络爬虫是由麻省理工学院的学生马修·格雷（Matthew Gray）在1993年编写的，他为这个程序起名为“互联网漫游者”（WWWWanderer）。

虽然后来的网络爬虫变得越来越复杂，但其基本原理依旧相同。

01 网络爬虫的工作原理

某爬虫结构

我们来看看网络爬虫是如何“下载”整个互联网的。

假设从一家门户网站的首页出发，先下载这个网页，然后分析它，主要是找到页面中的所有超链接，也就等于得到了这个网站首页所直接链接的全部网页，例如腾讯新闻、新浪财经等。

接下来，访问、下载并分析这些页面，又能找到其他相连的网页。

计算机持续这样工作，就能够下载整个互联网。

当然，我们还需要记录哪些网页已经下载过，以避免重复。

一个简单的案例｜通过动画，我们可以看到爬虫一步一步地访问每个网页。当前被访问的网页会被标记为红色，其他网页则显示为蓝色，文末附代码

在网络爬虫中，人们使用“哈希表”（Hash Table，也称“散列表”）而不是记事本来记录网页是否下载过的信息。

什么是哈希表（Hash Table）？

哈希表（Hash Table）是一种非常有用的数据结构，用来快速存储和查找数据。

想象一下，我们有一个非常大的文件柜，它有很多抽屉。

每个抽屉都有一个编号（就像每个家都有一个地址）。当我们需要存放或查找文件时，如果我们能快速找到对应的抽屉，就能很快地完成任务。

这就是哈希表的基本想法。

回到主题，现今的互联网规模庞大，不可能通过一台或几台计算机服务器完成下载任务。

例如，Google在2013年的索引大约包含10,000亿个网页，即使最频繁更新的基础索引也有100亿个网页。

假如下载一个网页需要一秒钟，那么下载这100亿个网页就需要317年，如果是10,000亿个网页则需要32000年左右，是我们人类有文字记载历史的六倍时间。

因此，一个商业的网络爬虫需要成千上万台服务器，并且通过高速网络连接起来。

如何建立这样复杂的网络系统，如何协调这些服务器的任务，就是网络设计和程序设计的艺术了。

02 图论中的经典问题与网络爬虫的启示

以哥尼斯堡七桥问题为例，如果将每块连通的陆地视为一个顶点，每座桥视为图的一条边，那么就可以把哥尼斯堡的七座桥抽象成图。

在这个图中，每个顶点连接的边的数量称为“度”。

定理： 如果一个图能够从某一顶点出发，遍历每条边且不重复，并最终回到该顶点，那么每个顶点的度必须为偶数。

当然，在实际工程中，网络爬虫需要考虑许多细节，其中包括以下几个方面：

a、选择BFS还是DFS？

虽然理论上讲，这两个算法在不考虑时间因素的前提下都能够在大致相同的时间内“爬完”整个“静态”互联网内容，但在现实中，这两个假设都是不可能实现的。

搜索引擎的网络爬虫问题更应定义为“如何在有限时间里最大程度地爬取最重要的网页”。

显然，每个网站最重要的网页应是其首页。

在极端情况下，如果爬虫只能下载有限的网页，应优先下载首页。

如果爬虫规模稍大些，则应下载从首页直接链接的网页，因为这些网页是网站设计者认为重要的。

在这种前提下，BFS显然优于DFS。

事实上，搜索引擎的爬虫虽然不是简单地采用BFS，但其调度程序基本上是基于BFS原理。

b、DFS是否就完全不用了呢？

其实，这与爬虫的分布式结构及网络通信的握手成本有关。

所谓“握手”是指下载服务器与网站服务器建立通信的过程，这需要额外的时间（Overhead Time）。如果握手次数过多，下载效率就会降低。

实际的网络爬虫由成百上千甚至上万台服务器组成分布式系统。

对于某个网站，一般由特定的服务器专门下载。这些服务器先下载完一个网站，再进入下一个网站，而不是每个网站先轮流下载5%。

这样可以减少握手次数，提高效率。

因此，下载同一个网站（或子网站）时，还是需要用BFS。

总结来说，网络爬虫对网页遍历的顺序其实是一个复杂排序系统，并非简单的BFS或DFS。

管理这个优先级排序的子系统称为调度系统（Scheduler），它决定了每个网页下载完成后，接下来下载哪个网页。

在调度系统中需要存储那些已经发现但尚未下载的网页URL，这些URL一般存在一个优先级队列（Priority Queue）中。

当一个网页下载完成后，需要从中提取URL并将其加入下载队列。

早期互联网网页大多使用HTML书写，URL以文本形式存在，容易提取。但如今很多网页使用脚本语言（如JavaScript）生成，URL不是直接可见的文本，而是运行脚本后才能得到的结果。

因此，网络爬虫的页面分析变得复杂，需要模拟浏览器运行网页，才能得到隐含的URL。

某些网页脚本不规范，解析困难，但浏览器能打开说明它们可以解析。

因此，需要具备浏览器内核开发技能的工程师来编写解析程序，而出色的浏览器内核工程师数量有限。

如果一些网页存在但搜索引擎未收录，可能是因为爬虫解析程序未能成功解析其中的不规范脚本。

互联网上一个网页可能被多个超链接指向，遍历互联网这张图时，某网页可能多次被访问。

为了防止重复下载，可以用哈希表记录已下载网页。采用哈希表的好处是判断一个URL是否在表中平均只需一次查找。

若遇到未下载的网页，除了下载该网页，还要将其URL存入哈希表。

维护一张哈希表在一台服务器上并不难，需要超级多的服务器同时下载网页才行，那么就意味着要管理一张统一的哈希表就不简单了。

首先，哈希表可能大到一台服务器无法存储。

其次，每台下载服务器在开始和完成下载前都要访问和维护这张表，以免重复下载，导致存储哈希表的服务器成为瓶颈。

如何解决这个瓶颈呢？

有各种方法，没有绝对正确的，但却有好坏之分。

好的方法一般包括以下两个技术：首先明确每台下载服务器的分工，即看到某个URL就知道交给哪台服务器下载，以免多台服务器重复判断某URL是否需下载。

其次，在明确分工的基础上，判断URL是否下载可以批处理，例如每次向哈希表（由一组独立服务器组成）发送一批询问或更新一批哈希表内容，从而大大减少通信次数。

总结

综上所述，网络爬虫通过图论的遍历算法，实现了从一个网页出发自动访问并存储每一个网页的功能。

尽管现代互联网规模庞大，技术复杂，但通过分布式系统、优先级调度、页面分析与哈希表等技术手段，网络爬虫依然能高效地爬取和下载网页。

这一过程不仅考验计算机科学理论与算法能力，更需要深厚的工程素养与创新精神，正如在Google面试中常见的那道经典题目一样，网络爬虫的设计与实现始终是对技术与艺术的完美结合。

科学羊🐏  2024/07/16

祝幸福~ 

附件📎：图论动态代码（Python）：

import matplotlib.pyplot as plt
import networkx as nx
import collections
import matplotlib.animation as animation

# 模拟网页链接图的类
class WebGraph:
    def __init__(self):
        self.graph = collections.defaultdict(list)

    def add_page(self, page, links):
        self.graph[page].extend(links)

# 模拟网络爬虫的类
class WebCrawler:
    def __init__(self, graph):
        self.graph = graph
        self.visited = set()
        self.queue = collections.deque()
        self.frames = []

    def crawl(self, start_page):
        self.queue.append(start_page)
        while self.queue:
            page = self.queue.popleft()
            if page not in self.visited:
                self.visited.add(page)
                self.frames.append((list(self.graph.keys()), page))
                for linked_page in self.graph[page]:
                    if linked_page not in self.visited:
                        self.queue.append(linked_page)

    def draw_graph(self, G, interval=1000):
        pos = nx.spring_layout(G)
        fig, ax = plt.subplots()

        def update(frame):
            ax.clear()
            nodes, current_node = frame
            nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color='gray', ax=ax)
            nx.draw_networkx_nodes(G, pos, nodelist=[current_node], node_color='red', ax=ax)
            plt.title(f"Visiting: {current_node}")

        ani = animation.FuncAnimation(fig, update, frames=self.frames, repeat=False, interval=interval)
        plt.show()

# 创建一个网页链接图
web_graph = WebGraph()
web_graph.add_page("Home", ["About", "Contact", "Blog"])
web_graph.add_page("About", ["Team", "History"])
web_graph.add_page("Contact", ["Email", "Phone"])
web_graph.add_page("Blog", ["Post1", "Post2"])
web_graph.add_page("Team", [])
web_graph.add_page("History", [])
web_graph.add_page("Email", [])
web_graph.add_page("Phone", [])
web_graph.add_page("Post1", [])
web_graph.add_page("Post2", [])

# 创建一个NetworkX图
G = nx.DiGraph()
for page, links in web_graph.graph.items():
    for link in links:
        G.add_edge(page, link)

# 创建一个网络爬虫并从主页开始爬取
crawler = WebCrawler(web_graph.graph)
crawler.crawl("Home")
crawler.draw_graph(G, interval=1000)  # 每1秒更新一次

参考文献：

[1]. 《数学之美》·吴军

强烈推荐大家读读吴军老师的数学之美～

「感恩关注，科学羊持续为您带来最好的科普知识」

往期推荐