簡析搜索引擎的網絡爬蟲技術

姜從群

（中國人民解放軍第二炮兵工程大學士官職業技術教育學院 山東 青州 262500）

1 網絡爬蟲技術

網絡爬蟲也稱為“文檔抽取系統”，是構成第三代搜索引擎系統的重要組成部分之一，主要由文檔適配器與信息爬行器組成，文檔適配器能夠處理不同類型的文檔，信息爬行器主要進行頁面信息的收集工作，文檔抽取子系統首先根據配置文件的約定，定時產生信息爬行器對分布在網絡上的信息節點進行遍歷，然后調用對應的文檔適配器來抽取網絡文檔信息。文檔適配器能夠抽取的頁面文件種類繁多，能夠對各種類型的文檔以及多媒體文本信息等。信息爬行器為計算機程序的一個進程或線程，通常采用并發工作方式，以便能可能多、周期盡可能短地搜集網絡節點的頁面信息，同時還要避免死鏈接或無效鏈接。信息爬行器一般采用分布式并行計算技術來提高工作的廣度與速度。

2 圖的遍歷算法

網絡爬蟲在網絡中執行信息收集的過程實際上就是一種圖的遍歷。圖的遍歷算法通常有兩種方式：即廣度優先算法與深度優先算法。下面就具體介紹一下兩種算法。

通常深度優先算法使用的數據結構為棧，通過棧的出入特點進行搜索，其過程首先從該圖的某個頂點或者子圖出發，將所有屬于該子圖的頂點信息的鏈接地址（即URL，Universal Resource Locator）進行壓棧操作，待所有頂點都操作完成后，然后將棧頂的元素取出，根據該元素的URL，訪問該元素URL所指向的網絡，然后將該頁面的信息進行收集與分析，從而得到該頁面內部的所有的URL連接信息，再將該頁面所有的連接信息進行壓棧，從而按照圖的廣度將圖上所有的鏈接進行展開操作，重復這些步驟就可以對圖進行深度搜索遍歷，達到遍歷收集所有互聯網信息資源的目的。

深度優先搜索算法在展開頁面鏈接時總是從棧頂進行展開，因此隨著時間的增加，棧的深度也在不斷增加，位于底部的元素可能會長時間不能進行處理，從而造成該算法陷入一個大的頁面而不能繼續展開遍歷。為了避免這一問題，可以采用廣度優先搜索算法，廣度優先搜索算法是通過隊列這種數據結構進行展開的，根據各個元素節點距離最初節點的層次對所有的網絡節點進行遍歷，從而對每個節點都能夠在訪問全網一次的時間內進行公平處理，克服了深度優先算法陷入局部節點的不足，也保證了不會漏掉隊列后面的的元素，從而達到了公平對待互聯網上所有節點資源的目的。

在廣度優先算法中，根據是否已經對節點進行訪問，將爬行隊列構造為兩部分：即待爬行隊列與已爬行隊列。待爬行隊列主要存儲需要進行訪問的元素節點URL，而URL在隊列中的先后順序則體現了算法的爬行策略。而已爬行隊列則主要存儲已經訪問過的URL，由于該隊列的長度隨著時間的增加不斷增長，因此需要優化該隊列的插入與查詢操作；在網絡爬蟲的爬行過程中，不論是帶爬行隊列還是已爬行隊列，都需要頻繁進行插入與查詢操作。因此，該隊列數據結構的性能會直接影響搜索引擎的搜集性能。

對爬行器來說，網頁的采集與解析是核心工作。而爬行程序是否高效，主要取決于網頁采集的效率。其過程分為5個步驟：

1）將待爬行隊列的第一個元素取出；

2）訪問DNS服務器，對URL進行域名解析；

3）根據ROBOT網絡協議，獲取該URL服務器的權限；

4）若得到訪問權限，則對服務器發出URL請求；

5）通過HTTP協議進行訪問。

網絡爬蟲在工作時，若頻繁訪問DNS服務器，可能會造成比較繁重的網絡負擔，引起服務器響應以及網絡延遲，會降低爬行程序的效率。因此，通常在本地服務器上建立一個DNS緩存來降低對DNS服務器的訪問頻率。同時，為了提高爬行程序的效率，通常采用多線程或者多進程來對網頁采集程序進行流水線處理，多線程與多進程程序設計相對比較復雜，需要解決的問題主要是進程的同步和互斥；也就是解決多個線程或進程共享資源的問題。造成死鎖的情況通常是占有一個資源然后又請求另一資源，因此，若系統只存在一個共享資源就不會造成會死鎖。為了解決餓死問題，通常只采用一個等待對列，若待爬行隊列處于使用狀態，則將要訪問該隊列的線程插入等待隊列。而隊列的特點能夠保證了所有的等待線程都公平對待，從而解決了餓死問題。具體算法如下：

1）對爬行隊列上鎖。若爬行隊列已經上鎖，則將該線程或進程插入等待對列。

2）取出待爬行隊列的URL元素。

3）對爬行隊列解鎖，然后喚醒下一個進程或線程。

4）訪問頁面，將頁面中的URL進行解析。

5）對爬行隊列上鎖。如爬行隊列已上鎖，則插入等待對列。

6）將步驟4）得到的URL插入對列。

7）對爬行隊列解鎖，喚醒下一個進程或線程。

8）重復1）——7）直到結束。

3 頁面解析

在解決了互聯網節點頁面遍歷的問題后，網絡爬蟲剩下的工作就是頁面解析，頁面解析主要是分析與理解HTML（超文本標記語言）文檔。HTML作為一種標記語言，能夠對互聯網節點的頁面外觀進行標準化處理，從而規范互聯網節點頁面的外觀與功能。實際上，超文本標記語言就是以普通文本為基礎，通過增加各種表現樣式以及字體、顏色標簽來實現文檔的規范化。通常各種標簽都用雙箭頭進行標識，而文本信息則位于＜tag＞＜/tag＞之間。圖2為一個典型的超文本標記語言文檔。

在超文本標記語言中，能夠表達連接的標簽通常是anchor標簽，即通過＜a＞…＜/a＞進行標識的標簽，長用來表達URL的超鏈接。各種頁面通過該標簽，將個節點相互獨立的網頁進行鏈接，從而構成了一種頁面連接圖的結構。解析HTML的文檔包括兩個步驟：

1）對表單進行識別解析，然后填寫該表單提交請求，在收到返回結果后，從結果中提取錨文本以及URL；

2）把超文本標記語言變換為純文本。

在解析頁面的過程中，首先需要獲取＜a＞＜/a＞標簽對之間的純文本信息（錨文本）與該文本標簽的URL地址，然后將HTML文檔中的標簽進行消除。這些工作都是字符串的處理工作，處理步驟如下：

1）使用HTML分析工具清洗頁面文檔，使之轉變成全部標準化的超文本標記語言頁面；

2）通過字符串處理工具解析HTML網頁；

3）將結果進行輸出。

通過以上解析過程，將URL信息從頁面中抽取出來，然后進行評價，再放入爬行隊列進行處理。

4 結束語

本文主要介紹了搜索引擎的網絡爬蟲技術，該技術是構成現代搜索引擎系統的重要組成部分之一，文章詳細研究圖的遍歷算法的兩種方式：即廣度優先算法與深度優先算法。在解決了互聯網節點頁面遍歷的問題后，對網絡爬蟲中的重要工作——頁面解析進行了具體的分析。