数学应用-图论和网络爬虫 (Web Crawlers)

发表者: 吴军,Google 研究员

[ 离散 是当代的一个重要分支,也是计算机科学的基础。它包括数 理逻辑、集合论、图论和近世代数四个分支。数理逻辑基于布尔运算,我们已经 介绍过了。这里我们介绍图论和互联网自动下载工具网络爬虫 (Web Crawlers) 之间的关系。顺便提一句,我们用 Google Trends 来搜索一下“离散”这 个词,可以发现不少有趣的现象。比如,武汉、哈尔滨、合肥和长沙市对这一数 学题目最有兴趣的。]

我们 上回 谈到了如何建立搜索引擎的索引,那么如何自动下载互联网所有的网页 呢,它要用到图论中的遍历(Traverse) 算法。

图论的起源可追溯到大数学家 欧拉 (Leonhard Euler)。1736 年欧拉来到德国 的哥尼斯堡(Konigsberg,大哲学家康德的故乡,现在是俄罗斯的加里宁格勒), 发现当地市民们有一项消遣活动,就是试图将下图中的 每座桥恰好走过一遍并 回到原出发点,从来没有人成功过。欧拉证明了这件事是不可能的,并写了一篇 论文,一般认为这是图论的开始。

图 论中所讨论的的图由一些节点和连接这些节点的弧组成。如果我们把中国的 当成节点,连接的国道当成弧,那么全国的公路干线网就是图论中所说 的图。关 于图的算法有很多,但最重要的是图的遍历算法,也就是如何通过弧 访问图的各个节点。以中国公路网为例,我们从北京出发,看一看北京和哪些城 市直接相连,比 如说和天津、济南、石家庄、南京、沈阳、大同直接相连。我 们可以依次访问这些,然后我们看看都有哪些和这些已经访问过的城市 相连,比如说北戴河、 秦皇岛与天津相连,青岛、烟台和济南相连,太原、郑 州和石家庄相连等等,我们再一次访问北戴河这些城市,直到中国所有的城市都

访问过一遍为止。这种图的遍 历算法称为“广度优先算法”(BFS),因为它先 要尽可能广地访问每个节点所直接连接的其他节点。另外还有一种策略是从北京 出发,随便找到下一个要访问的 城市,比如是济南,然后从济南出发到下一个 城市,比如说南京,再访问从南京出发的城市,一直走到头。然后再往回找,看 看中间是否有尚未访问的城市。这种方 法叫“深度优先算法”(DFS),因为它 是一条路走到黑。这两种方法都可以保证访问到全部的城市。当然,不论采用哪 种方法,我们都应该用一个小本本,记录 已经访问过的城市,以防同一个城市 访问多次或者漏掉哪个城市。

现在我们看看图论的遍历算法和搜索引擎的关系。互联网其实就是一张大图,我 们可以把每一个网页当作一个节点,把那些超链接(Hyperlinks)当作连接网页 的弧。很多读者可能已经注意到,网页中那些蓝色的、带有下划线的文字 背后 其实藏着对应的网址,当你点下去的的时候,浏览器是通过这些隐含的网址转到 相应的网页中的。这些隐含在文字背后的网址称为“超链接”。有了超链接,我 们可以从任何一个网页出发,用图的遍历算法,自动地访问到每一个网页并把它 们存起来。完成这个功能的程序叫做网络爬虫,或者在一些文献中称为"机器人" (Robot) 。 世 界 上 第 一 个 网 络 爬 虫 是 由 麻 省 理 工 学 院 (MIT) 的 学 生 马 休. 格 雷 (Matthew Gray)在 1993 年写成的。他给他的程序起了个名字叫“互联网漫游 者”("www wanderer")。以后的网络爬虫越写越复杂,但原理是一样的。

我 们来看看网络爬虫如何下载整个互联网。假定我们从一家门户网站的首页出 发,先下载这个网页,然后通过分析这个网页,可以找到藏在它里面的所有超链 接,也就 等于知道了这家门户网站首页所直接连接的全部网页,诸如雅虎邮件、 雅虎财经、雅虎等等。我们接下来访问、下载并分析这家门户网站的邮件等 网页,又能找 到其他相连的网页。我们让计算机不停地做下去,就能下载整个 的互联网。当然,我们也要记载哪个网页下载过了,以免重复。在网络爬虫中, 我们使用一个称为“ 哈希表 ”(Hash Table)的列表而不是一个记事本纪录网页 是否下载过的信息。

现 在的互联网非常巨大,不可能通过一台或几台计算机服务器就能完成下载任 务。比如雅虎公司(Google 没有公开公布我们的数目,所以我这里举了雅虎的 索引大小为例)宣称他们索引了 200 亿个网页,假如下载一个网页需要一秒钟, 下载这 200 亿个网页则需要 634 年。因此,一个商业的网络爬虫需要有成千上 万个服务器,并且由快速网络连接起来。如何建立这样复杂的网络系统,如何协 调这些服务器的任务,就是网络设计和 程序设计的艺术了。

声明: 除非转自他站(如有侵权,请联系处理)外,本文采用 BY-NC-SA 协议进行授权 | 智乐兔
转载请注明:转自《数学应用-图论和网络爬虫 (Web Crawlers)
本文地址:https://www.zhiletu.com/archives-2799.html
关注公众号:智乐兔

赞赏

wechat pay微信赞赏alipay pay支付宝赞赏

上一篇
下一篇

相关文章

在线留言

你必须 登录后 才能留言!

在线客服
在线客服 X

售前: 点击这里给我发消息
售后: 点击这里给我发消息

智乐兔官微