簡(jiǎn)析搜索引擎的網(wǎng)絡(luò)爬蟲技術(shù)

姜從群

（中國(guó)人民解放軍第二炮兵工程大學(xué)士官職業(yè)技術(shù)教育學(xué)院 山東 青州 262500）

1 網(wǎng)絡(luò)爬蟲技術(shù)

網(wǎng)絡(luò)爬蟲也稱為“文檔抽取系統(tǒng)”，是構(gòu)成第三代搜索引擎系統(tǒng)的重要組成部分之一，主要由文檔適配器與信息爬行器組成，文檔適配器能夠處理不同類型的文檔，信息爬行器主要進(jìn)行頁(yè)面信息的收集工作，文檔抽取子系統(tǒng)首先根據(jù)配置文件的約定，定時(shí)產(chǎn)生信息爬行器對(duì)分布在網(wǎng)絡(luò)上的信息節(jié)點(diǎn)進(jìn)行遍歷，然后調(diào)用對(duì)應(yīng)的文檔適配器來抽取網(wǎng)絡(luò)文檔信息。文檔適配器能夠抽取的頁(yè)面文件種類繁多，能夠?qū)Ω鞣N類型的文檔以及多媒體文本信息等。信息爬行器為計(jì)算機(jī)程序的一個(gè)進(jìn)程或線程，通常采用并發(fā)工作方式，以便能可能多、周期盡可能短地搜集網(wǎng)絡(luò)節(jié)點(diǎn)的頁(yè)面信息，同時(shí)還要避免死鏈接或無效鏈接。信息爬行器一般采用分布式并行計(jì)算技術(shù)來提高工作的廣度與速度。

2 圖的遍歷算法

網(wǎng)絡(luò)爬蟲在網(wǎng)絡(luò)中執(zhí)行信息收集的過程實(shí)際上就是一種圖的遍歷。圖的遍歷算法通常有兩種方式：即廣度優(yōu)先算法與深度優(yōu)先算法。下面就具體介紹一下兩種算法。

通常深度優(yōu)先算法使用的數(shù)據(jù)結(jié)構(gòu)為棧，通過棧的出入特點(diǎn)進(jìn)行搜索，其過程首先從該圖的某個(gè)頂點(diǎn)或者子圖出發(fā)，將所有屬于該子圖的頂點(diǎn)信息的鏈接地址（即URL，Universal Resource Locator）進(jìn)行壓棧操作，待所有頂點(diǎn)都操作完成后，然后將棧頂?shù)脑厝〕?，根?jù)該元素的URL，訪問該元素URL所指向的網(wǎng)絡(luò)，然后將該頁(yè)面的信息進(jìn)行收集與分析，從而得到該頁(yè)面內(nèi)部的所有的URL連接信息，再將該頁(yè)面所有的連接信息進(jìn)行壓棧，從而按照?qǐng)D的廣度將圖上所有的鏈接進(jìn)行展開操作，重復(fù)這些步驟就可以對(duì)圖進(jìn)行深度搜索遍歷，達(dá)到遍歷收集所有互聯(lián)網(wǎng)信息資源的目的。

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

在廣度優(yōu)先算法中，根據(jù)是否已經(jīng)對(duì)節(jié)點(diǎn)進(jìn)行訪問，將爬行隊(duì)列構(gòu)造為兩部分：即待爬行隊(duì)列與已爬行隊(duì)列。待爬行隊(duì)列主要存儲(chǔ)需要進(jìn)行訪問的元素節(jié)點(diǎn)URL，而URL在隊(duì)列中的先后順序則體現(xiàn)了算法的爬行策略。而已爬行隊(duì)列則主要存儲(chǔ)已經(jīng)訪問過的URL，由于該隊(duì)列的長(zhǎng)度隨著時(shí)間的增加不斷增長(zhǎng)，因此需要優(yōu)化該隊(duì)列的插入與查詢操作；在網(wǎng)絡(luò)爬蟲的爬行過程中，不論是帶爬行隊(duì)列還是已爬行隊(duì)列，都需要頻繁進(jìn)行插入與查詢操作。因此，該隊(duì)列數(shù)據(jù)結(jié)構(gòu)的性能會(huì)直接影響搜索引擎的搜集性能。

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

1）將待爬行隊(duì)列的第一個(gè)元素取出；

2）訪問DNS服務(wù)器，對(duì)URL進(jìn)行域名解析；

3）根據(jù)ROBOT網(wǎng)絡(luò)協(xié)議，獲取該URL服務(wù)器的權(quán)限；

4）若得到訪問權(quán)限，則對(duì)服務(wù)器發(fā)出URL請(qǐng)求；

5）通過HTTP協(xié)議進(jìn)行訪問。

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

1）對(duì)爬行隊(duì)列上鎖。若爬行隊(duì)列已經(jīng)上鎖，則將該線程或進(jìn)程插入等待對(duì)列。

2）取出待爬行隊(duì)列的URL元素。

3）對(duì)爬行隊(duì)列解鎖，然后喚醒下一個(gè)進(jìn)程或線程。

4）訪問頁(yè)面，將頁(yè)面中的URL進(jìn)行解析。

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

6）將步驟4）得到的URL插入對(duì)列。

7）對(duì)爬行隊(duì)列解鎖，喚醒下一個(gè)進(jìn)程或線程。

8）重復(fù)1）——7）直到結(jié)束。

3 頁(yè)面解析

在解決了互聯(lián)網(wǎng)節(jié)點(diǎn)頁(yè)面遍歷的問題后，網(wǎng)絡(luò)爬蟲剩下的工作就是頁(yè)面解析，頁(yè)面解析主要是分析與理解HTML（超文本標(biāo)記語(yǔ)言）文檔。HTML作為一種標(biāo)記語(yǔ)言，能夠?qū)ヂ?lián)網(wǎng)節(jié)點(diǎn)的頁(yè)面外觀進(jìn)行標(biāo)準(zhǔn)化處理，從而規(guī)范互聯(lián)網(wǎng)節(jié)點(diǎn)頁(yè)面的外觀與功能。實(shí)際上，超文本標(biāo)記語(yǔ)言就是以普通文本為基礎(chǔ)，通過增加各種表現(xiàn)樣式以及字體、顏色標(biāo)簽來實(shí)現(xiàn)文檔的規(guī)范化。通常各種標(biāo)簽都用雙箭頭進(jìn)行標(biāo)識(shí)，而文本信息則位于＜tag＞＜/tag＞之間。圖2為一個(gè)典型的超文本標(biāo)記語(yǔ)言文檔。

在超文本標(biāo)記語(yǔ)言中，能夠表達(dá)連接的標(biāo)簽通常是anchor標(biāo)簽，即通過＜a＞…＜/a＞進(jìn)行標(biāo)識(shí)的標(biāo)簽，長(zhǎng)用來表達(dá)URL的超鏈接。各種頁(yè)面通過該標(biāo)簽，將個(gè)節(jié)點(diǎn)相互獨(dú)立的網(wǎng)頁(yè)進(jìn)行鏈接，從而構(gòu)成了一種頁(yè)面連接圖的結(jié)構(gòu)。解析HTML的文檔包括兩個(gè)步驟：

1）對(duì)表單進(jìn)行識(shí)別解析，然后填寫該表單提交請(qǐng)求，在收到返回結(jié)果后，從結(jié)果中提取錨文本以及URL；

2）把超文本標(biāo)記語(yǔ)言變換為純文本。

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

1）使用HTML分析工具清洗頁(yè)面文檔，使之轉(zhuǎn)變成全部標(biāo)準(zhǔn)化的超文本標(biāo)記語(yǔ)言頁(yè)面；

2）通過字符串處理工具解析HTML網(wǎng)頁(yè)；

3）將結(jié)果進(jìn)行輸出。

通過以上解析過程，將URL信息從頁(yè)面中抽取出來，然后進(jìn)行評(píng)價(jià)，再放入爬行隊(duì)列進(jìn)行處理。

4 結(jié)束語(yǔ)

本文主要介紹了搜索引擎的網(wǎng)絡(luò)爬蟲技術(shù)，該技術(shù)是構(gòu)成現(xiàn)代搜索引擎系統(tǒng)的重要組成部分之一，文章詳細(xì)研究圖的遍歷算法的兩種方式：即廣度優(yōu)先算法與深度優(yōu)先算法。在解決了互聯(lián)網(wǎng)節(jié)點(diǎn)頁(yè)面遍歷的問題后，對(duì)網(wǎng)絡(luò)爬蟲中的重要工作——頁(yè)面解析進(jìn)行了具體的分析。