数学之美系列 -- 图论和网络爬虫 (Web Crawlers)

╰半橙微兮° 2022-09-18 05:50 180阅读 0赞

发表者: 吴军，Google 研究员   
  
\[[离散数学][Link 1]是当代数学的一个重要分支，也是计算机科学的数学基础。它包括数理逻辑、集合论、图论和近世代数四个分支。数理逻辑基于布尔运算，我们已经介绍过了。这里我们介绍图论和互联网自动下载工具网络爬虫 (Web Crawlers) 之间的关系。顺便提一句，我们用 [Google Trends][] 来搜索一下“离散数学”这个词，可以发现不少有趣的现象。比如，武汉、哈尔滨、合肥和长沙市对这一数学题目最有兴趣的城市。\]  
  
我们[上回][Link 2]谈到了如何建立搜索引擎的索引，那么如何自动下载互联网所有的网页呢，它要用到图论中的遍历（Traverse) 算法。  
  
图论的起源可追溯到大数学家[欧拉][Link 3]（Leonhard Euler）。1736 年欧拉来到德国的哥尼斯堡（Konigsberg，大哲学家康德的故乡，现在是俄罗斯的加里宁格勒），发现当地市民们有一项消遣活动，就是试图将下图中的每座桥恰好走过一遍并回到原出发点，从来没有人成功过。欧拉证明了这件事是不可能的，并写了一篇论文，一般认为这是图论的开始。  
  
![7bridges-785421.JPG][]  
  
图论中所讨论的的图由一些节点和连接这些节点的弧组成。如果我们把中国的城市当成节点，连接城市的国道当成弧，那么全国的公路干线网就是图论中所说的图。关于图的算法有很多，但最重要的是图的遍历算法，也就是如何通过弧访问图的各个节点。以中国公路网为例，我们从北京出发，看一看北京和哪些城市直接相连，比如说和天津、济南、石家庄、南京、沈阳、大同直接相连。我们可以依次访问这些城市，然后我们看看都有哪些城市和这些已经访问过的城市相连，比如说北戴河、秦皇岛与天津相连，青岛、烟台和济南相连，太原、郑州和石家庄相连等等，我们再一次访问北戴河这些城市，直到中国所有的城市都访问过一遍为止。这种图的遍历算法称为“广度优先算法”（BFS)，因为它先要尽可能广地访问每个节点所直接连接的其他节点。另外还有一种策略是从北京出发，随便找到下一个要访问的城市，比如是济南，然后从济南出发到下一个城市，比如说南京，再访问从南京出发的城市，一直走到头。然后再往回找，看看中间是否有尚未访问的城市。这种方法叫“深度优先算法”（DFS)，因为它是一条路走到黑。这两种方法都可以保证访问到全部的城市。当然，不论采用哪种方法，我们都应该用一个小本本，记录已经访问过的城市，以防同一个城市访问多次或者漏掉哪个城市。  
  
现在我们看看图论的遍历算法和搜索引擎的关系。互联网其实就是一张大图，我们可以把每一个网页当作一个节点，把那些超链接（Hyperlinks)当作连接网页的弧。很多读者可能已经注意到，网页中那些蓝色的、带有下划线的文字背后其实藏着对应的网址，当你点下去的的时候，浏览器是通过这些隐含的网址转到相应的网页中的。这些隐含在文字背后的网址称为“超链接”。有了超链接，我们可以从任何一个网页出发，用图的遍历算法，自动地访问到每一个网页并把它们存起来。完成这个功能的程序叫做网络爬虫，或者在一些文献中称为"机器人"（Robot)。世界上第一个网络爬虫是由麻省理工学院 (MIT)的学生马休.格雷（Matthew Gray)在 1993 年写成的。他给他的程序起了个名字叫“互联网漫游者”("www wanderer")。以后的网络爬虫越写越复杂，但原理是一样的。  
  
我们来看看网络爬虫如何下载整个互联网。假定我们从一家门户网站的首页出发，先下载这个网页，然后通过分析这个网页，可以找到藏在它里面的所有超链接，也就等于知道了这家门户网站首页所直接连接的全部网页，诸如雅虎邮件、雅虎财经、雅虎新闻等等。我们接下来访问、下载并分析这家门户网站的邮件等网页，又能找到其他相连的网页。我们让计算机不停地做下去，就能下载整个的互联网。当然，我们也要记载哪个网页下载过了，以免重复。在网络爬虫中，我们使用一个称为“[哈希表][Link 4]”(Hash Table)的列表而不是一个记事本纪录网页是否下载过的信息。  
  
现在的互联网非常巨大，不可能通过一台或几台计算机服务器就能完成下载任务。比如雅虎公司（Google 没有公开公布我们的数目，所以我这里举了雅虎的索引大小为例）宣称他们索引了 200 亿个网页，假如下载一个网页需要一秒钟，下载这 200 亿个网页则需要 634 年。因此，一个商业的网络爬虫需要有成千上万个服务器，并且由快速网络连接起来。如何建立这样复杂的网络系统，如何协调这些服务器的任务，就是网络设计和程序设计的艺术了。

-----------------------------------------------------------------------------------------------------------------------------------------------------

<table> 
 <tbody> 
  <tr> 
   <td><span> <p><font>吴军的《数学之美》系列文章确实不错，相当的不错，一定要推荐一下。文章介绍了统计语言学的一些基本概念，更结合搜索引擎的技术讲解了这些技术的实际应用。文笔深入浅出，不愧是大牛。</font></p> 
     <div> 
      <p><a href="http://googlechinablog.com/2006/04/blog-post.html" rel="nofollow"><font>数学之美 系列一 -- 统计语言模型</font></a></p> 
      <p><a href="http://googlechinablog.com/2006/04/blog-post_10.html" rel="nofollow"><font>数学之美系列二 -- 谈谈中文分词</font></a></p> 
      <p><a href="http://googlechinablog.com/2006/04/blog-post_17.html" rel="nofollow"><font>数学之美系列三 -- 隐含马尔可夫模型在语言处理中的应用</font></a></p> 
      <p><a href="http://googlechinablog.com/2006/04/4.html" rel="nofollow"><font>数学之美系列四 -- 怎样度量信息?</font></a></p> 
      <p><br><a href="http://googlechinablog.com/2006/05/blog-post_10.html" rel="nofollow"><font>数学之美系列五 -- 简单之美：布尔代数和搜索引擎的索引</font></a></p> 
      <p><a href="http://googlechinablog.com/2006/05/web-crawlers.html" rel="nofollow"><font>数学之美系列六 -- 图论和网络爬虫 (Web Crawlers)</font></a></p> 
      <p><a href="http://googlechinablog.com/2006/05/blog-post_25.html" rel="nofollow"><font>数学之美系列七 -- 信息论在信息处理中的应用</font></a></p> 
      <p><br><a href="http://googlechinablog.com/2006/06/blog-post_08.html" rel="nofollow"><font>数学之美系列八 -- 贾里尼克的故事和现代语言处理</font></a></p> 
      <p><a href="http://googlechinablog.com/2006/06/blog-post_27.html" rel="nofollow"><font>数学之美系列九 -- 如何确定网页和查询的相关性</font></a></p> 
      <p>from <a href="http://www.mrspace.net/index.php" rel="nofollow">http://www.mrspace.net/index.php</a></p> 
     </div> </span></td> 
  </tr> 
 </tbody> 
</table>

**其他文章：**

[google一些鲜为人知的搜索技巧-1][google_-1]

[试图通俗地讲一下庞加莱猜想是怎么回事][Link 5]

[Heroes in My Heart (1)][Heroes in My Heart _1]

[美国如何变成数学超级强国][Link 6]

[月光理论及推论][Link 7]

[对数学未来的思考][Link 8]

[Fields奖获得者分析][Fields]

from [![Google Blog Logo][]][Google Blog Logo 1]

[Link 1]: http://www.google.com/trends?q=%E7%A6%BB%E6%95%A3%E6%95%B0%E5%AD%A6
[Google Trends]: http://www.google.com/trends
[Link 2]: http://googlechinablog.com/2006/05/blog-post_10.html
[Link 3]: http://www.aoshu.cn/Article_D/2004-10/142778573371443.htm
[7bridges-785421.JPG]: http://googlechinablog.com/uploaded_images/7bridges-785421.JPG
[Link 4]: http://www.ddvip.com/program/c/index3/70.htm
[google_-1]: http://blog.csdn.net/suprman/archive/2007/01/10/1478679.aspx
[Link 5]: http://blog.csdn.net/suprman/archive/2007/01/05/1474379.aspx
[Heroes in My Heart _1]: http://blog.csdn.net/suprman/archive/2006/12/29/1467843.aspx
[Link 6]: http://blog.csdn.net/suprman/archive/2006/12/25/1459876.aspx
[Link 7]: http://blog.csdn.net/suprman/archive/2006/12/23/1456612.aspx
[Link 8]: http://blog.csdn.net/suprman/archive/2006/11/14/1383461.aspx
[Fields]: http://blog.csdn.net/suprman/archive/2006/11/08/1373104.aspx
[Google Blog Logo]: http://googlechinablog.com/google_bb.gif
[Google Blog Logo 1]: http://googlechinablog.com/