数学之美:图论和网络爬虫

作者:吴军 摘自:《数学之美》(人民邮电出版社)

离散数学包括数理逻辑、集合论、图论和近世代数四个分支。这里我们介绍图论和互联网自动下载工具网络爬虫 (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 年。因此,一个商业的网络爬虫需要有成千上万个服务器,而且由快速网络连接起来。

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

原文发布于微信公众号 - 大数据文摘(BigDataDigest)

原文发表时间:2015-10-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SDNLAB

SDN实战团分享(九):Next-Gen光交换技术+ODL构建Cloud Data Center

大家晚上好,首先声明一下,今天在这里分享的内容为个人技术关点,不代表公司立场。SDN和Optical这块知识我不是专家给大家起个穿针引线,哪块说的不对还请各位多...

3438
来自专栏C语言及其他语言

想举办自己的编程比赛? 来这里

大家都知道C语言网(www.dotcpp.com)是一个集在线学习、训练、比赛、求职于一体的综合性编程学习网站。大家除了日常在网站上看视频学习、做题训练、写题...

1722
来自专栏程序人生

浪费内存?多大个事?

遥想盖子当年,MS 红火了,谈笑间,640k 内存足矣。 - 程序君 现在已经不是从指缝中扣内存的时代了。bit 在主流的解释型语言中要么失了踪迹,要么被作为...

4188
来自专栏玉树芝兰

密码怎么设才好?一条标准就够了

又看到网络安全事件的新闻了吧?心慌不慌?其实设置和保管好自己的密码,只需要记住这一条标准就可以了。

985
来自专栏FreeBuf

横古贯今的隐私密史:密码的前世来生

21世纪什么最贵?密(秘)码(密)! 但陈老师高清无码教材红了,某菊订票信息玩票“脱裤”了,数以千万计的开房信息泄露了,各种社工库横行霸道,让我们不禁不去感叹...

2165
来自专栏程序人生

高效能程序员的七个习惯

昨天收到一个读者留言,问作为程序员,有什么学习和工作上的好习惯可以借鉴?想了想,干脆附庸风雅一下,总结个『高效能程序员的七个习惯』吧。Disclaimer:一家...

3609
来自专栏机器人网

11个这类开源名称的词源

  “它适用于信息目前掌握在少数人而非许多人手中的任何领域,少数人控制产品、服务或实体的生产、分发和改进的任何领域。”   我们已搞明白了这点,那么“Kuber...

3505
来自专栏coding

写下这行代码时,只有我和上帝知道是怎么回事01.烂代码的路径依赖02.对于烂代码应采取零容忍03.代码规范的重要性04.文档的重要性

"算了,这里的代码有说不清的玄机,重构相当于在给自己挖更大的坑,还是按照原来的写法吧..."

793
来自专栏FreeBuf

极客DIY:童年的掌上游戏机

写在前面 小伙伴们,还记得过去的掌上游戏机吗?一名网友wermy在YouTube上面上传了一个DIY掌上游戏机的视频,下面就一起来怀念一下童年的见闻。 game...

2326
来自专栏ThoughtWorks

其实你早就学过响应式编程 | TW洞见

今日洞见 文章作者/图片 来自ThoughtWorks:佟达。 本文所有内容,包括文字、图片和音视频资料,版权均属ThoughtWorks公司所有,任何媒体、网...

34912

扫码关注云+社区