離散數學包括數理邏輯、集合論、圖論和近世代數四個分支。這裡我們介紹圖論和網際網路自動下載工具網絡爬蟲 (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 年。因此,一個商業的網絡爬蟲需要有成千上萬個伺服器,而且由快速網絡連接起來。怎樣創建這樣複雜的網絡系統,怎樣協調這些伺服器的任務,就是網絡設計和程序設計的藝術了。