姜夢稚
目前,對于全球大多數(shù)互聯(lián)網(wǎng)用戶來說,搜索引擎是其準(zhǔn)確獲得所需要信息或者知識的最有效的工具。但是對于所有的搜索引擎來說,最重要的性能指標(biāo)有兩個:查全率和查準(zhǔn)率。查全率與搜索引擎搜集的網(wǎng)頁數(shù)量和質(zhì)量有關(guān)。
本文介紹的是用于搜集網(wǎng)頁, 提高查全率的最重要的工具—網(wǎng)絡(luò)爬蟲(Web Crawler)的設(shè)計與實現(xiàn)。網(wǎng)絡(luò)爬蟲的主要作用是搜集互聯(lián)網(wǎng)的網(wǎng)頁,也可以用它來定期搜集某個網(wǎng)站的內(nèi)容,跟蹤判斷網(wǎng)站的發(fā)展,或者做站內(nèi)搜索引擎。從網(wǎng)絡(luò)爬蟲的工作原理來看,“網(wǎng)絡(luò)爬蟲”是一個比較形象的名字,它是在互聯(lián)網(wǎng)內(nèi),通過網(wǎng)頁鏈接,從當(dāng)前網(wǎng)頁爬到下一個網(wǎng)頁來進(jìn)行網(wǎng)頁內(nèi)容搜集的工具。它所需完成的工作[1]如下:(1)在一個網(wǎng)頁上,獲取網(wǎng)頁的標(biāo)題和網(wǎng)頁中的摘要;(2)將搜集到的網(wǎng)頁標(biāo)題,鏈接,網(wǎng)頁的摘要放入數(shù)據(jù)庫中;(3)根據(jù)當(dāng)前網(wǎng)頁的內(nèi)容,搜集網(wǎng)頁中的鏈接信息,并根據(jù)鏈接順序搜索相應(yīng)鏈接網(wǎng)頁的內(nèi)容。
不同的Web Crawler,在設(shè)計的時候側(cè)重各有不同,本文所介紹的Web Crawler在設(shè)計的時候主要考慮解決以下幾個問題:(1)Web Crawler遍歷網(wǎng)頁中的所有鏈接,并且能對所搜索的網(wǎng)頁進(jìn)行搜索深度的限制;(2)Web Crawler能夠提取出網(wǎng)頁中的摘要和標(biāo)題信息,并且保存到數(shù)據(jù)庫中;(3)要求能夠?qū)σ延械乃阉饕娴乃阉鹘Y(jié)果再優(yōu)化,提高所設(shè)計的Crawler的擴展能力;(4)要求能夠采用多線程的方式,提高搜索的效率。
針對前述的四個目標(biāo),在設(shè)計Crawler的時候,具體考慮了如下一些問題。首先Crawler的搜索深度的問題,網(wǎng)頁中的鏈接關(guān)系是相當(dāng)復(fù)雜的,一組網(wǎng)頁之間可以互相包含,網(wǎng)頁A中的鏈接可以指向網(wǎng)頁B,同時網(wǎng)頁B中的鏈接也可以指向網(wǎng)頁A。因此,網(wǎng)頁的搜索深度必須作一定的限制,不能無限制的遞歸搜索;其次網(wǎng)頁的搜索方式也有差別,有些爬蟲采用廣度優(yōu)先策略 (BFS),有些采用了深度優(yōu)先策略(DFS)[2],考慮到實現(xiàn)時采用多線程,且所設(shè)計的 Crawler需在搜索的深度上作了限制,所以采用深度搜索的方式。對于搜集所有url鏈接,可以有不同的方式,本文采用的正則表達(dá)式。盡管具體的實現(xiàn)有多種方式,搜集鏈接也可以采用后面所提到的HtmlParser包,但是采用正則表達(dá)式,是一種方便,快捷的手段,Java語言也提供對正則表達(dá)式的支持。
多線程程序是編程中比較復(fù)雜的問題,除了對線程的調(diào)試比較困難外,對線程所使用的資源的控制也同樣復(fù)雜。在Java平臺下對多線程的編程有充分支持,因此在設(shè)計Crawler的多線程實現(xiàn)時,采用了Synchronous關(guān)鍵字,原子數(shù)(AtomicInteger)和線程池[3],通過使用線程池,在應(yīng)用啟動的時候,設(shè)置所需創(chuàng)建的線程數(shù)量,一旦線程池為空,則掛起當(dāng)前請求,等待空閑的線程出現(xiàn);原子數(shù)則可以保證程序中的計數(shù)以互斥的方式操作,保證了遞增和遞減操作的原子性;而Synchronous保證了不同線程在訪問數(shù)據(jù)的時候不會出現(xiàn)兩個線程同時訪問一個數(shù)據(jù)。
本文中實現(xiàn)的Crawler中第三個考慮的問題就是獲取網(wǎng)頁的內(nèi)容、提取網(wǎng)頁摘要信息和標(biāo)題信息。網(wǎng)頁內(nèi)容的獲取方式有多種,比較常用的就是想網(wǎng)頁發(fā)出一個 Http請求,并獲取返回的字符流??紤]到實現(xiàn)這種請求/響應(yīng)方式的復(fù)雜性,本文采用了HtmlParser[4]包來具體實現(xiàn)網(wǎng)頁內(nèi)容的獲取。對于標(biāo)簽的獲取采用兩種方式,一種是采用HtmlParser包來獲取,另外一種提取文本的方式也可以使用正則表達(dá)式[5],在構(gòu)造合適的正則表達(dá)式時,需要考慮到標(biāo)簽的特殊結(jié)構(gòu),為了提高文字的抽取效率,可以對一段 html源碼首先過濾掉一些不需要的標(biāo)簽。采用HtmlParser包除了能夠獲得網(wǎng)頁的內(nèi)容外,該包還能提供一系列的獲取網(wǎng)頁內(nèi)容的工具類,獲取特定標(biāo)簽,并通過標(biāo)簽篩選規(guī)則的運用,獲取包含有文字的標(biāo)簽,提取出其中的文字作為摘要;對于標(biāo)題通過獲取
本節(jié)介紹Web Crawler的設(shè)計,包括類的設(shè)計和時序圖的設(shè)計。本文所實現(xiàn)的Web Crawler采用MVC的設(shè)計方式,前臺設(shè)計成Web頁面,發(fā)送Web請求;后臺Servlet接受前臺發(fā)送過來的請求。在后臺,有如下幾部分的內(nèi)容:描述數(shù)據(jù)實現(xiàn)的ICrawlerModel接口及其實現(xiàn);表示多線程搜索的ICrawler接口、AbstractCrawler和 MultipleThreadCrawler類;工具類IParser接口和HtmlParser類;表示鏈接的數(shù)據(jù)結(jié)構(gòu)Link和LinkDepth類;以及存儲結(jié)果的DbAccess類。上述類的實現(xiàn)都是采用Java,數(shù)據(jù)庫使用MySQL,除此以外還要用Tomcat Web服務(wù)器,如圖1所示。
前臺的設(shè)計使用 jsp+jQuery的方式,jQuery是一種javascript工具包,提供對ajax的支持,能夠?qū)崿F(xiàn)無刷新的頁面布局。Ajax是目前一種流行的設(shè)計網(wǎng)頁的方式。后臺采用Servlet運行方式,獲取前臺通過ajax方式提交的參數(shù),根據(jù)不同的選擇(可能是關(guān)鍵詞的搜索,也可能是某一個網(wǎng)址的搜索)進(jìn)行處理。
圖1 Web Crawler的類圖[6]
MultipleThreadCrawler實現(xiàn)了抽象類AbstractCrawler,它是Crawler實現(xiàn)的核心內(nèi)容,主要對每一次的搜索數(shù)據(jù)的處理,多線程的協(xié)調(diào)等。在該類中實現(xiàn)兩個私有類Worm和TextExtractor,前者實現(xiàn)對網(wǎng)頁鏈接的搜索,并填充入Model中的toVisitUrls數(shù)據(jù)結(jié)構(gòu)中,后者則是對當(dāng)前搜索的網(wǎng)頁提取標(biāo)題和摘要信息。
MaxDepthModel是一個存儲數(shù)據(jù)的類,其包括已經(jīng)訪問過的Url和未訪問過的Url,并且提供向數(shù)據(jù)結(jié)構(gòu)中填充未訪問的Url。采用接口的方式,也是為了能夠在今后擴展具體實現(xiàn)。
HtmlParser提供了對文本解析的方法,圖2給出的用戶提交待搜索的網(wǎng)站的時序圖:
圖2 時序圖[6]
本文設(shè)計的Web Crawler采用Java語言和MySql來實現(xiàn),作為開源工具的組合,被應(yīng)用在很多重要的領(lǐng)域。除了前述提到的實現(xiàn)細(xì)節(jié)外,在獲取html文本中的url鏈接時使用了正則表達(dá)式,可以提高文字的匹配速率和程序的運行效率(采用Java包匹配往往比較復(fù)雜)。同時在抽取html文本的文字信息時,也使用了這種技術(shù),由于正則表達(dá)式表述的靈活性,并沒有一種能夠適合所有情況的匹配表達(dá)式,只有在實踐過程中不斷改進(jìn)和優(yōu)化。
本文總結(jié)了Web Crawler在設(shè)計和實現(xiàn)過程中遇到的問題,并結(jié)合軟件設(shè)計模式,給出一種Web Crawler可行的軟件結(jié)構(gòu),并實現(xiàn)檢索,存儲,顯示等一系列問題,所給出的解決方法有一定的通用性,軟件的框架能夠根據(jù)實際的需要進(jìn)行改寫,可以在對當(dāng)前已有得搜索引擎的搜索結(jié)果進(jìn)行優(yōu)化。Web Crawler是一個需要不斷優(yōu)化和改進(jìn)的工具,其設(shè)計和實現(xiàn)可以采用多種方式,也可以根據(jù)Crawler的實際需要來設(shè)計。
[1]宋暉,張嶺,葉允明.基于標(biāo)記樹對象抽取技術(shù)的 Hidden Web獲取研究[J].計算機工程與應(yīng)用,2002(23).
[2]赫楓齡.用有向圖法解決網(wǎng)頁爬行中循環(huán)鏈接問題[J].吉林大學(xué)學(xué)報,2004.3.
[3]陳昊鵬,饒若楠.Java編程思想,第3版[M].機械工業(yè)出版社,2005.5.
[4]Derrick Oswald等 HtmlParser參考文檔,http://htmlparser.sourceforge.net. [OL].
[5]史壽偉.正則表達(dá)式參考文檔,http://www.regexlab.com/zh/regref.htm [OL].
[6]Martin Fowler UML精粹:標(biāo)準(zhǔn)對象建模語言簡明指南[M].2006.3.