【文章內(nèi)容簡介】 “超圖”，則對這張圖也可以采用寬度優(yōu)先遍歷的方式進行訪問。 寬度優(yōu)先遍歷互聯(lián)網(wǎng)：寬度優(yōu)先遍歷是從一個種子節(jié)點開始的。而實際的爬蟲項目是從一系列的種子鏈接開始的。所謂種子鏈接，就好 比寬度優(yōu)先遍歷中的種子節(jié)點一樣。實際的爬蟲項目中種子鏈接可以有多個，而寬度優(yōu)先遍歷中的種子節(jié)點只有一個。比如，指定 種子鏈接，如何定義一個鏈接的子節(jié)點。每個鏈接對應一個 HTML 頁面或者其他文件 (word、 excel、 pdf、 jpg 等 )，在這些文件中，只有 HTML 頁面有相應的“子節(jié)點”，這些“子節(jié)點”就是 HTML 頁面上對應的超鏈接。如頁面中，“招聘”、“網(wǎng)址”、“更多”以及頁面下方的“搜索產(chǎn)品”、“技術文檔”、“成功案例”、“新聞”、“聯(lián)系我們”、“關于我們”、“ ENGLISH”等都是種子的子節(jié)點。這些子節(jié)點本身又是一個鏈接。對于非 HTML 文檔，比如 Excel 文件等，不能從中提取超鏈接，因此，可以看作是圖的“終端”節(jié)點。整個的寬度優(yōu)先爬蟲過程就是從一系列的種子節(jié)點開始，把這些網(wǎng)頁中的“子節(jié)點” (也就是超鏈接 )提取出來，放入隊列中依次進行抓取。被處理過的鏈接需要放入一張表 (通常稱為 Visited 表 )中。每次新處理一個鏈接之前，需要查看這個鏈接是否已經(jīng)存在于 Visited 表中。如果存在，證明鏈接已經(jīng)處理過，跳過，不做處理，否則進行下一步處理。 山東財經(jīng)大學學士學位論文 5 圖 31寬度優(yōu)先爬蟲過程 初始的 URL 地址是爬蟲系統(tǒng)中提供的種子 URL(一般在系統(tǒng)的配置文件中指定 )。當解析這些種子 URL 所表示的網(wǎng)頁時，會產(chǎn)生新的 URL(比如從頁面中的 a href= “ 這個鏈接 )。然后進行以下工作： (1) 把解析出的鏈接和 Visited 表中的鏈接進行比較，若 Visited 表中不存在此鏈接，表示其未被訪問過。 (2) 把鏈接放入 TODO 表中。 (3) 處理完畢 后，再次從 TODO 表中取得一條鏈接，直接放入 Visited 表中。 (4) 針對這個鏈接所表示的網(wǎng)頁，繼續(xù)上述過程。如此循環(huán)往復。 寬度優(yōu)先遍歷是爬蟲中使用最廣泛的一種爬蟲策略，之所以使用寬度優(yōu)先搜索策略，主要原因有兩點： (1)重要的網(wǎng)頁往往離種子比較近，例如我們打開新聞網(wǎng)站的時候往往是最熱的新聞，隨著不斷的深入沖浪，所看到的網(wǎng)頁的重要性越來越低； (2)萬維網(wǎng)的實際深度最多能達到 17 層，但到達某個網(wǎng)頁總存在一條很短的路徑。而寬度優(yōu)先遍歷會以最快的速度到達這個網(wǎng)頁。 深度優(yōu)先搜索 深度優(yōu)先搜索所遵循的 搜索策略是盡可能“深”地搜索圖。在深度優(yōu)先搜索中 ,對于最新發(fā)現(xiàn)的頂點 ,如果它還有以此為起點而未探測到的邊 ,就沿此邊繼續(xù)下去。當結點 v 的所有邊都己被探尋過 ,搜索將回溯到發(fā)現(xiàn)結點 v 有那條邊的始結點。這一過程一直進行到已發(fā)現(xiàn)從源結點可達的所有結點為止。如果還存在未被發(fā)現(xiàn)的結點 ,則選擇其中一個作為源結點并重復以上過程 ,整個進程反復進行直到所有結點都被發(fā)現(xiàn)為止。深度優(yōu)先在很多情況下會導致爬蟲的陷入 ( trapped )問題 ,所以它既不是完備的 ,也不是最優(yōu)的。 （四）爬取鏈接 網(wǎng)絡爬蟲主要用途就是爬取鏈接。正則表達 式，是指一個用來描述或者匹配一系列符合某個句法規(guī)則的字符串的多個字符串。在很多文本編輯器或其他工具里，正則表達式通常被用來檢索或替換那些符合某個模式的文本內(nèi)容。許多程序設計語言都支持利用正則表達式進行字符串操作。 一個正則表達式通常被稱為一個模式（ pattern ），為用來描述或匹配一系列符合某個句法規(guī)則的字符串。例如， (1)替換 |：數(shù)值分隔符代表替換。例如“ gray|grey”可以匹配grey或 gray； (2)數(shù)量限定：某個字符后的數(shù)量限定服用來先頂前面這個字符允許出現(xiàn)的個數(shù)。最常見的數(shù)量限定符包括“ +”、“？”和“ *”（不加數(shù)量限定則代表出現(xiàn)一次且僅出現(xiàn)一次）； +：加號代表前面的字符必須至少出現(xiàn)一次。例如，“ goo+gle”可匹配 google， gooogle，Todo 表 Todo 表 解析 URL 初始 URL 山東財經(jīng)大學學士學位論文 6 goooogle等；？：問號代表前面的字符最多只可以出現(xiàn)一次。例如，“ colou？ r”可以匹配colour 或 color； *：星號代表前面的字符可以不出現(xiàn)，也可以出現(xiàn)一次或者多次。（）：可以用來定義操作符的范圍和優(yōu)先度。 四、相關技術 （一） WEB 訪問過程 Web的應用層協(xié)議 HTTP是 Web的核心。 HTTP在 Web的客戶程序和服務器程序中得以實現(xiàn)。運 行在不同端系統(tǒng)上的客戶程序和服務器程序通過交換 HTTP消息彼此交流。 HTTP定義這些消息的結構以及客戶和服務器如何交換這些消息。 HTTP定義 Web客戶 (即瀏覽器 )如何從 web服務器請求 Web頁面，以及服務器如何把 Web頁面?zhèn)魉徒o客戶。下圖展示了這種請求 — 響應行為。當用戶請求一個 Web頁面 (譬如說點擊某個超鏈接 )時，瀏覽器把請求該頁面中各個對象的 HTTP請求消息發(fā)送給服務器。服務器收到請求后，以運送含有這些對象 HTTP響應消息作為響應。到 1997年底，基本上所有的瀏覽器和 Web 服務器軟件都實現(xiàn)了在 RFC 1945 中定義的 HTTP/ 版本。 1998 年初，一些 Web服務器軟件和瀏覽器軟件開始實現(xiàn)在 RFC 2616 中定義的 HTTP/ 版本。 H1TP/ 與HTTP/，運行 web服務器可以與運行 “對話”，運行 Web服務器“對話”。 圖 41web訪問過程 HTTP/ HTTP/ TCP作為底層的傳輸協(xié)議。 HTTP客戶首先發(fā)起建立與服務器TCP 連接。一 旦建立連接，瀏覽器進程和服務器進程就可以通過各自的套接字來訪問 TCP。如前所述，客戶端套接字是客戶進程和 TCP 連接之間的“門”，服務器端套接字是服務器進程和同一 TCP連接之間的“門”。客戶往自己的套接字發(fā)送 HTTP請求消息，也從自己的套接字接收 HTTP響應消息。類似地，服務器從自己的套接字接收 HTTP請求消息，也往自己的套接字發(fā)送 HTTP響應消息?？蛻艋蚍掌饕坏┌涯硞€消息送入各自的套接字，這個消息就完全落入 TCP 的控制之中。 TCP 給 HTTP 提供一個可靠的數(shù)據(jù)傳輸服務，這意味著由客戶發(fā)出的每個 HTTP請求消 息最終將無損地到達服務器，由服務器發(fā)出的每個 HTTP響應消息最終也將無損地到達客戶。我們可從中看到分層網(wǎng)絡體系結構的一個明顯優(yōu)勢 —— HTTP 不必擔心數(shù)據(jù)會丟失，也無需關心 TCP如何從數(shù)據(jù)的丟失和錯序中恢復出來的細節(jié)。這些是 TCP和協(xié)議棧中更低協(xié)議層的任務。 運行 Explorer 的 PC 機 運行 NCSA Web 服務器軟件的服務器 運行 Navigator的 Mac機 HTTP 請求 HTTP 響應 HTTP 請求 HTTP 響應 山東財經(jīng)大學學士學位論文 7 TCP還使用一個擁塞控制機制。該機制迫使每個新的 TCP連接一開始以相對緩慢的速率傳輸數(shù)據(jù)，然而只要網(wǎng)絡不擁塞，每個連接可以迅速上升到相對較高的速率。這個慢速傳輸?shù)某跏茧A段稱為緩啟動 (slow start)。 需要注意的是，在向客戶發(fā)送所請求文件的同時，服 務器并沒有存儲關于該客戶的任何狀態(tài)信息。即便某個客戶在幾秒鐘內(nèi)再次請求同一個對象。相反，服務器重新發(fā)送這個對象，因為它已經(jīng)徹底忘記早先做過什么。既然 HTTP服務器不維護客戶的狀態(tài)信息，于是說 HTTP是一個無狀態(tài)的協(xié)議 (stateless protocol)。 HTTP(HyperText Transfer Protocol)是一套計算機通過網(wǎng)絡進行通信的規(guī)則。計算機專家設計出 HTTP，使 HTTP客戶（如 Web瀏覽器）能夠從 HTTP服務器 (Web服務器 )請求信息和服務， HTTP目前協(xié)議的版本是 ，無狀態(tài)是指 Web瀏覽器和Web服務器之間不需要建立持久的連接，這意味著當一個客戶端向服務器端發(fā)出請求，然后Web服務器返回響應 (response)，連接就被關閉了，在服務器端不保留連接的有關信息。 HTTP遵循請求 (Request)/應答 (Response)模型。 Web 瀏覽器向 Web服務器發(fā)送請求， Web 服務器處理請求并返回適當?shù)膽?。所?HTTP連接都被構造成一套請求和應答。 HTTP 使用內(nèi)容類型，是指 Web服務器向 Web 瀏覽器返回的文件都有與之相關的類型。所有這些類型在 MIME Inter郵件協(xié)議上模型化，即 Web服務器告訴 Web瀏覽器該文件所具有的種類，是 HTML 文檔、 GIF 格式圖像、聲音文件還是獨立的應用程序。大多數(shù) Web 瀏覽器都擁有一系列的可配置的輔助應用程序，它們告訴瀏覽器應該如何處理 Web服務器發(fā)送過來的各種內(nèi)容類型。 圖 42動態(tài) web頁面工作原理 （二） JAVA技術 Java是由 Sun Microsystems公司所開發(fā)的一個高級程序語言，它的原名叫做 OAK，是專門為小型的周邊設備所設計的語言 (現(xiàn)在這個部分 已經(jīng)變成 Java Micro Edition)， OAK在推出之后，并沒有獲得大家的重視，所以在 1995年 Sun公司就把它改名為 Java，并把設計的目標訂在互聯(lián)網(wǎng)絡的環(huán)境里。在做了這樣大的突破后， Java 順利的成為了用戶人數(shù)成長最快的語言。 Java的核心可以分為兩個部分，一個是 Java平臺，而另一個是 Java語言。 Sun和其他的公司都有為不同的硬件推出 Java平臺，也就是 Java Virtual Machine(Java虛擬機 )，這些虛擬機忽略了各個平臺的差異，讓程序開發(fā)人員可以用同樣的 Java 程序在完全不 同的環(huán)境下執(zhí)行，甚至會按照平臺的不同顯示不同的輸出。例如你可以在 Linux 上執(zhí)行為 Linux量身定做的虛擬機，然后執(zhí)行在 Windows 環(huán)境下所開發(fā)的 Java程序，讓用戶可以通過瀏覽 Web 服務器 客戶端發(fā)送請求 返回服務端響應 靜態(tài) Html頁面 Servlet 引擎 執(zhí)行對應程序 轉發(fā)請求 返回結果 山東財經(jīng)大學學士學位論文 8 器來執(zhí)行這些程序，最后這些程序又可以安裝在可移動設備中。 （三）網(wǎng)絡編程 包中的類和接口提供了可用于低層和高層網(wǎng)絡編程的 API。低層 API 可以讓你直接訪問網(wǎng)絡協(xié)議，但是為此你不得不使用低層的 TCP 套接字和 UDP 數(shù)據(jù)包。高層的API(如 URL、 URLConnection 和 URLConnection 等類 )可以使你更快的開發(fā)網(wǎng)絡應用，卻不需要寫很多代碼。 包中含有高層 API。它們實現(xiàn)了一些最常用的基于 TCP 的協(xié)議，如 HTTP 和 FTP 等 。其 中兩個 主要 的類 是 URL 和 URLConnection。 另一 個有 用的類 是 HttpURLConnection，它是 URLConnection 的子類，支持 HTTP 的特性。 URL (Uniform Resource Locator，統(tǒng)一資源定位器 )是一個描述 Inter 中文檔 (或者其它常見的資源 ) 位置的地址。 URL 的樣子就像這樣： FTP、HTTPS 和 FILE 協(xié)議。 要從 URL 讀取內(nèi)容，可以用 URL 類非常容易的實現(xiàn)。用這種方法讀取的內(nèi)容不包含服務器回應的頭信息，所以不需要去解析它們。 URL 類會解析輸入的 URL 并處理低層的麻煩的工作。 （四） HTML知識 因為 Web 中的信息都是建立在 HTML 協(xié)議之上的，所以網(wǎng)絡機器人在檢索網(wǎng)頁時的第一個問題就是如何解析 HTML。 當今的 Inter 上面有數(shù)億記的網(wǎng)頁，越來 越多應用程序將這些網(wǎng)頁作為分析和處理的數(shù)據(jù)對象。這些網(wǎng)頁多為半結構化的文本，有著大量的標簽和嵌套的結構。當我們自己開發(fā)一 些處理網(wǎng)頁的應用程序時，會想到要開發(fā)一個單獨的網(wǎng)頁解析器，這一部分的工作必定需要付出相當?shù)木蜁r間。事實上，做為 JAVA 應用程序開發(fā)者， HtmlParser 為其提供了強大而靈活易用的開源類庫，大大節(jié)省了寫一個網(wǎng)頁解析器的開銷。它提供了線性和嵌套兩種方式來解析網(wǎng)頁，主要用于 html 網(wǎng)頁的轉換 (Transformation) 以及網(wǎng)頁內(nèi)容的抽取 (Extraction)。 本文 中利用字符串匹配提取網(wǎng)頁里的鏈接，實現(xiàn)簡易爬蟲里的關鍵部分。 HTML中的幾種數(shù)據(jù)：文本 ,除了腳本和標簽之外的所有數(shù)據(jù)；注釋 ,程序員留下的說明文字，對用戶是不可見的；簡單標簽 ,由單個表示的 HTML標簽；開始標簽和結束標簽 ,用來控制所包含的 HTML 代碼。在進行解析的時候不用關心所有的標簽，只需要對其中幾種重要的進行解析即可。 超連接標簽：超連接定義了 WWW 通過 Inter鏈接文檔的功能。他們的主要目的是使用戶能夠任意遷移到新的頁面，這正是網(wǎng)絡機器人最關心的標簽。 圖像映射標簽：圖像映射是另一種非常重要的標 簽。它可以讓用戶通過點擊圖片來遷移到新的頁面中。 表單標簽：表單是 Web頁面中可以輸入數(shù)據(jù)的單元。許多站點讓用戶填寫數(shù)據(jù)然后通過點擊按鈕來提交內(nèi)容，這就是表單的典型應用。 表格標簽：表格是 HTML的構成部分，通常用來格式化存放、顯示數(shù)據(jù)。 五、需求分析 （一）同步環(huán)境