2006年5月15日 上午 07:15:00 作者: google 吳軍

[ 離散數(shù)學(xué) 是當(dāng)代數(shù)學(xué)的一個重要分支，也是計算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)。它包括數(shù)理邏輯、集合論、圖論和近世代數(shù)四個分支。數(shù)理邏輯基于布爾運(yùn)算，我們已經(jīng)介紹過了。這里我們介紹圖論和互聯(lián)網(wǎng)自動下載工具網(wǎng)絡(luò)爬蟲 (Web Crawlers) 之間的關(guān)系。順便提一句，我們用 Google Trends 來搜索一下“離散數(shù)學(xué)”這個詞，可以發(fā)現(xiàn)不少有趣的現(xiàn)象。比如，武漢、哈爾濱、合肥和長沙市對這一數(shù)學(xué)題目最有興趣的城市。]

我們 上回 談到了如何建立搜索引擎的索引，那么如何自動下載互聯(lián)網(wǎng)所有的網(wǎng)頁呢，它要用到圖論中的遍歷（Traverse) 算法。

圖論的起源可追溯到大數(shù)學(xué)家 歐拉 （Leonhard Euler）。1736 年歐拉來到德國的哥尼斯堡（Konigsberg，大哲學(xué)家康德的故鄉(xiāng)，現(xiàn)在是俄羅斯的加里寧格勒），發(fā)現(xiàn)當(dāng)?shù)厥忻駛冇幸豁椣不顒樱褪窃噲D將下圖中的每座橋恰好走過一遍并回到原出發(fā)點(diǎn)，從來沒有人成功過。歐拉證明了這件事是不可能的，并寫了一篇論文，一般認(rèn)為這是圖論的開始。



圖論中所討論的的圖由一些節(jié)點(diǎn)和連接這些節(jié)點(diǎn)的弧組成。如果我們把中國的城市當(dāng)成節(jié)點(diǎn)，連接城市的國道當(dāng)成弧，那么全國的公路干線網(wǎng)就是圖論中所說的圖。關(guān)于圖的算法有很多，但最重要的是圖的遍歷算法，也就是如何通過弧訪問圖的各個節(jié)點(diǎn)。以中國公路網(wǎng)為例，我們從北京出發(fā)，看一看北京和哪些城市直接相連，比如說和天津、濟(jì)南、石家莊、南京、沈陽、大同直接相連。我們可以依次訪問這些城市，然后我們看看都有哪些城市和這些已經(jīng)訪問過的城市相連，比如說北戴河、秦皇島與天津相連，青島、煙臺和濟(jì)南相連，太原、鄭州和石家莊相連等等，我們再一次訪問北戴河這些城市，直到中國所有的城市都訪問過一遍為止。這種圖的遍歷算法稱為“廣度優(yōu)先算法”（BFS)，因為它先要盡可能廣地訪問每個節(jié)點(diǎn)所直接連接的其他節(jié)點(diǎn)。另外還有一種策略是從北京出發(fā)，隨便找到下一個要訪問的城市，比如是濟(jì)南，然后從濟(jì)南出發(fā)到下一個城市，比如說南京，再訪問從南京出發(fā)的城市，一直走到頭。然后再往回找，看看中間是否有尚未訪問的城市。這種方法叫“深度優(yōu)先算法”（DFS)，因為它是一條路走到黑。這兩種方法都可以保證訪問到全部的城市。當(dāng)然，不論采用哪種方法，我們都應(yīng)該用一個小本本，記錄已經(jīng)訪問過的城市，以防同一個城市訪問多次或者漏掉哪個城市。

現(xiàn)在我們看看圖論的遍歷算法和搜索引擎的關(guān)系。互聯(lián)網(wǎng)其實就是一張大圖，我們可以把每一個網(wǎng)頁當(dāng)作一個節(jié)點(diǎn)，把那些超鏈接（Hyperlinks)當(dāng)作連接網(wǎng)頁的弧。很多讀者可能已經(jīng)注意到，網(wǎng)頁中那些藍(lán)色的、帶有下劃線的文字背后其實藏著對應(yīng)的網(wǎng)址，當(dāng)你點(diǎn)下去的的時候，瀏覽器是通過這些隱含的網(wǎng)址轉(zhuǎn)到相應(yīng)的網(wǎng)頁中的。這些隱含在文字背后的網(wǎng)址稱為“超鏈接”。有了超鏈接，我們可以從任何一個網(wǎng)頁出發(fā)，用圖的遍歷算法，自動地訪問到每一個網(wǎng)頁并把它們存起來。完成這個功能的程序叫做網(wǎng)絡(luò)爬蟲，或者在一些文獻(xiàn)中稱為"機(jī)器人"（Robot)。世界上第一個網(wǎng)絡(luò)爬蟲是由麻省理工學(xué)院 (MIT)的學(xué)生馬休.格雷（Matthew Gray)在 1993 年寫成的。他給他的程序起了個名字叫“互聯(lián)網(wǎng)漫游者”("www wanderer")。以后的網(wǎng)絡(luò)爬蟲越寫越復(fù)雜，但原理是一樣的。

我們來看看網(wǎng)絡(luò)爬蟲如何下載整個互聯(lián)網(wǎng)。假定我們從一家門戶網(wǎng)站的首頁出發(fā)，先下載這個網(wǎng)頁，然后通過分析這個網(wǎng)頁，可以找到藏在它里面的所有超鏈接，也就等于知道了這家門戶網(wǎng)站首頁所直接連接的全部網(wǎng)頁，諸如雅虎郵件、雅虎財經(jīng)、雅虎新聞等等。我們接下來訪問、下載并分析這家門戶網(wǎng)站的郵件等網(wǎng)頁，又能找到其他相連的網(wǎng)頁。我們讓計算機(jī)不停地做下去，就能下載整個的互聯(lián)網(wǎng)。當(dāng)然，我們也要記載哪個網(wǎng)頁下載過了，以免重復(fù)。在網(wǎng)絡(luò)爬蟲中，我們使用一個稱為“ 哈希表 ”(Hash Table)的列表而不是一個記事本紀(jì)錄網(wǎng)頁是否下載過的信息。

現(xiàn)在的互聯(lián)網(wǎng)非常巨大，不可能通過一臺或幾臺計算機(jī)服務(wù)器就能完成下載任務(wù)。比如雅虎公司（Google 沒有公開公布我們的數(shù)目，所以我這里舉了雅虎的索引大小為例）宣稱他們索引了 200 億個網(wǎng)頁，假如下載一個網(wǎng)頁需要一秒鐘，下載這 200 億個網(wǎng)頁則需要 634 年。因此，一個商業(yè)的網(wǎng)絡(luò)爬蟲需要有成千上萬個服務(wù)器，并且由快速網(wǎng)絡(luò)連接起來。如何建立這樣復(fù)雜的網(wǎng)絡(luò)系統(tǒng)，如何協(xié)調(diào)這些服務(wù)器的任務(wù)，就是網(wǎng)絡(luò)設(shè)計和程序設(shè)計的藝術(shù)了。

數(shù)學(xué)之美系列六 -- 圖論和網(wǎng)絡(luò)爬蟲 (Web Crawlers)