陳澤

摘 要：網(wǎng)絡(luò)爬蟲是計算機(jī)搜索領(lǐng)域內(nèi)一塊非常核心的內(nèi)容，帶偏好的網(wǎng)絡(luò)爬蟲則是目前搜索領(lǐng)域中的一大熱點，也是目前較難解決的問題之一?，F(xiàn)有的大多數(shù)爬蟲算法都是根據(jù)關(guān)鍵詞對網(wǎng)頁鏈接進(jìn)行搜索遍歷，直接將結(jié)果展示出來，這種方法隨著互聯(lián)網(wǎng)上數(shù)據(jù)的增多，會使得搜索結(jié)果越來越偏離用戶的真實需求。

關(guān)鍵詞：網(wǎng)絡(luò)爬蟲；深度寬度優(yōu)先算法；網(wǎng)頁去噪

網(wǎng)絡(luò)爬蟲是計算機(jī)搜索領(lǐng)域的核心內(nèi)容，是各大搜索引擎巨頭都在努力研究的重點內(nèi)容，在互聯(lián)網(wǎng)中有著非常廣泛的應(yīng)用。當(dāng)然，網(wǎng)絡(luò)爬蟲也是計算機(jī)領(lǐng)域的一塊非常有難度的研究內(nèi)容，因為面對復(fù)雜的使用群體、網(wǎng)絡(luò)連接故障、數(shù)據(jù)存取錯誤以及爬蟲自身追求效率帶來的錯誤率，爬蟲的結(jié)果都會出現(xiàn)不同程度的偏差，尤其對于帶偏好的爬蟲，設(shè)計上更加要注重解決以上的問題，而且還要兼顧搜索效率，這些都給爬蟲設(shè)計帶來了很大的困難?；谂判?qū)W習(xí)的爬蟲設(shè)計難點就在于如何克服不同使用群體帶來的搜索結(jié)果的偏差以及提高搜索的效率和搜索結(jié)果的準(zhǔn)確度方面的問題。

大多數(shù)傳統(tǒng)的爬蟲算法，以寬度優(yōu)先搜索遍歷算法作為遍歷url鏈接的基本方法，或者是以深度優(yōu)先搜索算法，遍歷抓取到的網(wǎng)頁中的url鏈接。但是在遍歷的過程中，這兩種算法都缺少了對抓取到的網(wǎng)頁中的url鏈接的權(quán)重值的計算，如果對某些不太重要的url進(jìn)行大量時間的遍歷，則會降低爬蟲的爬行效率，也會導(dǎo)致結(jié)果與搜索預(yù)期出現(xiàn)很大偏差。

另一種是能夠在抓取的過程中通過使用者的興趣愛好以及抓取到的網(wǎng)頁中的url出現(xiàn)頻率來計算各個url的權(quán)重值，按照權(quán)重值的高低將url鏈接加入到爬蟲的優(yōu)先隊列中，再對該隊列進(jìn)行出隊和入隊，這樣重要的url鏈接往往會得到優(yōu)先處理，提高爬行的準(zhǔn)確性。

而一種基于使用人群和排序?qū)W習(xí)的網(wǎng)絡(luò)爬蟲的設(shè)計，獲取更加符合使用人群的爬行結(jié)果。相比于現(xiàn)有的傳統(tǒng)網(wǎng)絡(luò)爬蟲有以下的特點：1）通過關(guān)聯(lián)度來確定網(wǎng)頁鏈接的優(yōu)先級，避免對不太相關(guān)的網(wǎng)絡(luò)鏈接的抓取，減少服務(wù)器壓力；2）基于排序?qū)W習(xí)，能很好的適應(yīng)使用群體，更好的滿足帶有偏好的爬行需求；3）爬行效率有所增加，由于使用了Rank算法來過濾掉一下相關(guān)性不高的網(wǎng)頁URL，使得爬蟲爬行時能減少爬行的路徑，降低爬蟲程序的計算量，從而提高爬行的效率。

一、主要采用的設(shè)計方式

（1）將傳統(tǒng)的爬蟲算法進(jìn)行改進(jìn)，與基礎(chǔ)的深度、寬度優(yōu)先搜索策略相合，利用Rank算法減少爬蟲程序的爬行量。

傳統(tǒng)的網(wǎng)絡(luò)爬蟲普遍使用寬度、深度優(yōu)先搜索算法對指定的網(wǎng)頁URL中的其他網(wǎng)頁的鏈接進(jìn)行處理，往往由于數(shù)據(jù)量太大造成搜索結(jié)果出現(xiàn)較長時間的等待，雖然數(shù)據(jù)量較為全面，但是包含許多不必要的網(wǎng)頁，往往使得程序在一段較長的時間內(nèi)白白消耗服務(wù)器資源，因此，使用Rank算法對網(wǎng)頁URL進(jìn)行重要度評價是非常有必要的，是否啟用此Rank算法，往往還需要結(jié)合爬行結(jié)構(gòu)的復(fù)雜度，抓取到的各個網(wǎng)頁中URL鏈接的數(shù)量。本課題將對不同情況下使用Rank算法的效率進(jìn)行測試，綜合實驗結(jié)果來考慮使用算法的情景，從算法原理，算法速度上來綜合對比以及進(jìn)行改進(jìn)融合，設(shè)計出實用性更好的網(wǎng)絡(luò)爬蟲。

（2）設(shè)計出一種面向不同使用群體的爬行方法，對不同偏好下的搜索展示出不一樣的結(jié)果，滿足使用群體的搜索預(yù)期，提高爬蟲的適用度。

在獲取到使用群體的偏好后，結(jié)合網(wǎng)頁重要度來重新排列抓取到的網(wǎng)頁中URL的優(yōu)先級，計算出URL在該應(yīng)用場景下的權(quán)重值，通過權(quán)重值來判斷下一個要抓取的節(jié)點，結(jié)合傳統(tǒng)的深度、寬度優(yōu)先搜索策略對鏈接內(nèi)容進(jìn)行抓取，減少傳統(tǒng)爬蟲的爬行量，因為同一標(biāo)簽下的內(nèi)容大致可視為同一類內(nèi)容，所以通過標(biāo)簽對內(nèi)容進(jìn)行判定也可以減輕評價網(wǎng)頁重要度的難度。

（3）設(shè)計一種簡單有效的網(wǎng)頁評價算法。利用大多數(shù)網(wǎng)頁之間相互關(guān)聯(lián)，計算出網(wǎng)頁引用和被引用的頻率，更新鏈接的重要度以及優(yōu)先級。

由于網(wǎng)頁中，往往同一標(biāo)簽下的內(nèi)容屬于同一類的信息，所以，通過標(biāo)簽可預(yù)測該標(biāo)簽下內(nèi)容的大致信息，對網(wǎng)頁內(nèi)容分析時可以不用花費太多時間逐一分析網(wǎng)頁文本，減少分析的復(fù)雜性，提高效率，而網(wǎng)頁被引用的頻率可以通過在其他網(wǎng)頁中該鏈接的出現(xiàn)頻次進(jìn)行分析，結(jié)合二者，便可以快速判斷出該網(wǎng)頁在不同分類下的權(quán)重值，結(jié)合搜索條件便能計算出網(wǎng)頁的重要度，從而決定網(wǎng)頁鏈接在進(jìn)行爬行時的優(yōu)先級別。

（4）設(shè)計一種有效的過濾算法。由于互聯(lián)網(wǎng)中巨大的數(shù)據(jù)量，各個網(wǎng)頁之間往往會出現(xiàn)相互引用，重復(fù)引用的情況，若對重復(fù)出現(xiàn)的URL鏈接進(jìn)行爬行，往往浪費許多服務(wù)器資源和時間。

使用過濾器，避免對同一網(wǎng)頁進(jìn)行重復(fù)抓取，在爬蟲程序每次對網(wǎng)頁進(jìn)行抓取的過程中，可設(shè)計出一種數(shù)據(jù)結(jié)構(gòu)，來存儲爬蟲爬行時的記錄，將已經(jīng)爬行過的URL放入到已經(jīng)訪問的URL隊列中，在進(jìn)行下一次爬行時，先比較爬行的鏈接是否存在于已訪問的URL隊列中，若存在著跳過對此鏈接的抓取，若不存在才對鏈接進(jìn)行處理，這樣能大大減少爬行的路徑，同時也能避免爬蟲陷入某條循環(huán)路徑中，從而快速的給出爬行的結(jié)果。

二、網(wǎng)絡(luò)爬蟲中的爬行隊列設(shè)計

要實現(xiàn)設(shè)計基于排序?qū)W習(xí)的網(wǎng)絡(luò)爬蟲，首先要設(shè)計出一個能記錄URL的隊列，由于爬蟲是按照順序逐條對抓取到的URL鏈接進(jìn)行分析處理，所以設(shè)計出的URL隊列要滿足對URL鏈接始終能優(yōu)先按照網(wǎng)頁重要程度排序，且隊列中的URL必須與搜索的內(nèi)容有所關(guān)聯(lián)，這樣才能防止爬蟲在無效的URL或不相關(guān)的URL鏈接上浪費資源。一次，優(yōu)先隊列的設(shè)計對本網(wǎng)絡(luò)爬蟲程序來說是十分重要的，是網(wǎng)絡(luò)爬蟲中較為核心的內(nèi)容，好的優(yōu)先隊列必須具備存取速度快，出隊入隊效率高的特點，這樣才能應(yīng)用到實際的網(wǎng)絡(luò)抓取中。

很多情況下，網(wǎng)頁中都包含許多與主要內(nèi)容無關(guān)的文本、圖片、廣告鏈接、推廣鏈接、flash動畫等，比如一個新聞網(wǎng)頁，除了主要的新聞?wù)臉?biāo)題內(nèi)容以外，都可以視為內(nèi)容無關(guān)文本，也就是俗稱的“噪聲”。

在建立優(yōu)先隊列之前，應(yīng)該先對這些噪聲進(jìn)行處理，不處理的話會引起主題搜索時主題飄移的情況。而且不去掉網(wǎng)頁中的多余內(nèi)容，爬蟲系統(tǒng)對這些噪聲也建立索引，從而導(dǎo)致某張網(wǎng)頁的噪聲內(nèi)容中出現(xiàn)了搜索關(guān)鍵詞，噪聲內(nèi)容代表的網(wǎng)頁也會被返回，而實際進(jìn)行的搜索可能與這個查詢詞毫無關(guān)系，這樣，噪聲內(nèi)容不僅增加了爬行的時間，還引起了索引結(jié)構(gòu)規(guī)模的巨大化，也影響了最后搜索結(jié)果的準(zhǔn)確性，由于網(wǎng)頁種類繁多，雖然用人工去除噪聲的方法效果最好，但是付出的代價往往太大，所以一般用通用的去出網(wǎng)頁噪聲的方法——統(tǒng)計法。

三、過濾器的設(shè)計

在平時的學(xué)習(xí)生活中，往往存在對重復(fù)事物的判斷，這些都可以抽象為數(shù)學(xué)中判斷元素是否在某一個集合中，在計算機(jī)軟件設(shè)計時也是如此，比如對單詞拼寫的檢查，就是判斷單詞是否出現(xiàn)在字典中，換作爬蟲，就是判斷該鏈接是否已經(jīng)被訪問過。當(dāng)然，最直接的方法就是將集合的全部元素存儲到計算機(jī)內(nèi)部，每次都將計算機(jī)內(nèi)部的元素與新出現(xiàn)的元素進(jìn)行比較，這就是最簡單的過濾功能了，在爬蟲中，過濾器的功能就是防止對已經(jīng)訪問過的網(wǎng)頁出現(xiàn)重復(fù)訪問的情況發(fā)生。設(shè)計一個好的過濾器能大大提高爬蟲搜索效率。

采用了布隆過濾器對爬蟲網(wǎng)址進(jìn)行過濾，其設(shè)計基本步驟如下：

（1）將要過濾的地址哈希到一個很大的地址空間，主要是根據(jù)地址中各種不同的字母進(jìn)行計算，使得各個不同的鏈接能夠根據(jù)規(guī)則哈希到某個獨一無二的空間中，并且把內(nèi)容設(shè)置為true。

（2）當(dāng)爬蟲抓取到一個網(wǎng)址時，對這個網(wǎng)址使用設(shè)計好的哈希規(guī)則映射到每一位上，看看是否每一位都為true，如果是這說明這個網(wǎng)址在過濾器中已經(jīng)存在，否則不存在。

四、網(wǎng)頁抓取的設(shè)計

在網(wǎng)絡(luò)爬蟲中，抓取最多的內(nèi)容就是Html頁面，但是信息都是隱藏在Html頁面之中的，搜索引擎感興趣的并不是頁面本身，所以關(guān)于頁面的抓取和對內(nèi)容的處理成了爬蟲之中一個很重要的環(huán)節(jié)，通過對HTML頁面的處理，我們才能得到真正需要的內(nèi)容。

在對Html頁面進(jìn)行處理時，需要用到正則表達(dá)式。正則表達(dá)式能幫助我們將某種特定格式的內(nèi)容抽取出來，而其他不符合的內(nèi)容則直接丟棄。在本課題中，主要使用正則表達(dá)式提取特定格式的URL鏈接，對URL鏈接進(jìn)行過濾和對網(wǎng)頁內(nèi)容進(jìn)行提取。

網(wǎng)頁展現(xiàn)給我們的只是它的文本，所以爬蟲程序的主題就是抽取網(wǎng)頁的文本內(nèi)容，利用正則表達(dá)式和抽取工具（HtmlParser）來抽取這些內(nèi)容。

HtmlParser工具能實現(xiàn)文本抽取，鏈接抽取，資源抽取，鏈接檢查，站點檢查等功能，在轉(zhuǎn)換功能方面，也能提供URL重寫，廣告清除，將Html頁面轉(zhuǎn)化為XML頁面以及對Html頁面進(jìn)行清理。HtmlParser中有描述HTML元素的各種Tag，利用抓取功能對各種Tag進(jìn)行分類處理就能很好的提取出網(wǎng)頁的主要內(nèi)容。在本課題中，由于需要對正文進(jìn)行抽取，考慮到目前各種網(wǎng)頁的不規(guī)范設(shè)計，所以從統(tǒng)計的角度，往往將正文定義為在一個Table，Div，ParagraphTag里的內(nèi)容，所以在本課題中，處理正文主要是對Table，Div，ParagraphTag進(jìn)行處理。

根據(jù)正則表達(dá)式的相關(guān)用法，可以結(jié)合HtmlParser實現(xiàn)一個網(wǎng)頁內(nèi)容抽取程序，對網(wǎng)頁內(nèi)容處理之前會判斷網(wǎng)址受歡迎程度，本次采用Berkeley DB存儲網(wǎng)址的信息，如網(wǎng)址權(quán)重，標(biāo)題，類型，爬取層數(shù)，作者，引用的鏈接，域名的ip地址等，數(shù)據(jù)庫中的數(shù)據(jù)為key，value格式，其中key值為網(wǎng)址的md5碼。數(shù)據(jù)庫中分為行鍵和列族，主要通過行鍵對數(shù)據(jù)進(jìn)行定位，查詢，列族是指相似的數(shù)據(jù)的集合，主要是方便同一類數(shù)據(jù)的存儲，在本課題中，列族為網(wǎng)址的主域名地址，方便數(shù)據(jù)的查找。將查找后的數(shù)據(jù)進(jìn)行權(quán)重值的比較，按權(quán)重優(yōu)先順序?qū)⒕W(wǎng)址加入優(yōu)先隊列，爬行程序按照優(yōu)先順序進(jìn)行網(wǎng)頁的抓取，這樣能快速的得到想要搜索的網(wǎng)頁，使得爬行更加高。

通過對網(wǎng)絡(luò)爬蟲的基本算法進(jìn)行了改進(jìn)，優(yōu)化了爬蟲的去重，過濾步驟，使用統(tǒng)計法對網(wǎng)頁噪聲進(jìn)行清除，防止噪聲干燥搜索的正確性，通過布隆過濾器對重復(fù)出現(xiàn)的URL進(jìn)行過濾操作，這些都大大降低了爬蟲的計算量。還對一些重復(fù)文檔的存儲進(jìn)行了校驗，通過使用checksum來判斷文檔是否唯一，防止重復(fù)文檔浪費大量存儲空間。對網(wǎng)頁內(nèi)容的抓取也進(jìn)行了優(yōu)化，使用HtmlParser工具，將網(wǎng)頁提取為串行節(jié)點，在對各個標(biāo)簽的處理中有充分考慮到實際情況，對網(wǎng)頁內(nèi)容按照不同的標(biāo)簽進(jìn)行劃分。對不同鏈接進(jìn)行了引用與被引用的統(tǒng)計，使用這些數(shù)據(jù)能在后續(xù)過程中對網(wǎng)頁的權(quán)重值進(jìn)行計算，方便判斷網(wǎng)頁鏈接以及網(wǎng)頁內(nèi)容中鏈接的重要程度，通過各種占比剔除掉一些與主題關(guān)聯(lián)度低的鏈接內(nèi)容。