余兆釵 傅化權(quán)

（閩江學(xué)院計算機科學(xué)系，福建 福州 350108）

0 引言

我國域名總數(shù)為1844萬個，其中“．CN”域名總數(shù)較去年同期增長44．2%，達到1083萬，在中國域名總數(shù)中占比達58．7%，我國網(wǎng)站總數(shù)為320萬個，較去年同期增長19．4%。除了互聯(lián)網(wǎng)中新的網(wǎng)頁不斷增加，互聯(lián)網(wǎng)中原有的網(wǎng)頁也會因為各種原因被刪除，有研究指出：50%網(wǎng)頁的平均生命周期大約為50天，互聯(lián)網(wǎng)中每天都新的網(wǎng)頁增加，每天都網(wǎng)頁被刪除。面對海量的網(wǎng)絡(luò)資源，如何加快搜索引擎信息的更新頻率，成了重要的課題。

網(wǎng)絡(luò)爬蟲是搜索引擎的重要組成部分，搜索引擎存儲的信息資源就是由網(wǎng)絡(luò)爬蟲在海量的互聯(lián)網(wǎng)中搜索下載的，加快網(wǎng)絡(luò)爬蟲的搜索速度，是加快搜索引擎信息更新的有效手段。

1 基于內(nèi)容評價最好優(yōu)先搜索策略

（1）頁面信息提取。網(wǎng)絡(luò)爬蟲從主題種子集隊列中，挑選一個頁面價值度最高的URL，網(wǎng)絡(luò)爬蟲訪問該URL頁面并下載頁面，保存在本地。

（2）頁面解析過濾。對下載的頁面，首先去除頁面中的javascript腳本語言、CSS樣式；然后去除網(wǎng)頁中的HTML標簽，得到頁面的正文文本。同時提取頁面中超鏈接URL。

（3）頁面分詞。頁面得到正文文本后，計算正文文本相鄰字的相似度。對于相關(guān)度大于閾值，將其劃分出來，歸類為詞語；小于閾值的，另作其他處理。

（4）頁面關(guān)鍵字提取。分詞得到的頁面詞語，首先對它們做預(yù)處理，過濾詞語中是虛詞、人稱代詞、疊詞、數(shù)量、連詞、介詞、語句助詞等對頁面內(nèi)容無關(guān)的詞語。依據(jù)詞語在頁面正文中所占比例按照大小排序，去除一定數(shù)量比例大的詞語和比例小的詞語，剩余的詞語選取排列在靠前的作為關(guān)鍵字。

（5）頁面關(guān)鍵字加權(quán)重。對于選出的關(guān)鍵字進行加權(quán)計算，一般采用采用TF-IDF詞頻統(tǒng)計方法。

（6）頁面主題相關(guān)度計算。頁面關(guān)鍵字加權(quán)計算完以后，再根據(jù)向量空間模型（VSM）進行頁面與主題的相關(guān)度計算。如果相關(guān)度高，就加入到搜索隊列中，作為以后搜索到對象；相關(guān)度低或不相關(guān)，丟棄這個網(wǎng)頁。

2 改進的最好優(yōu)先搜索策略

網(wǎng)站開發(fā)者在開發(fā)一個網(wǎng)站時，通常會根據(jù)網(wǎng)頁的主題，為每個網(wǎng)頁劃分各個目錄，這樣每個目錄存放的網(wǎng)頁主題都是有一定相關(guān)性的。比如新浪新聞網(wǎng)站的目錄結(jié)構(gòu)，在新浪新聞網(wǎng)目錄下劃分了國內(nèi)新聞、國際新聞、社會新聞、新聞評論等子目錄，分別管理著不同模塊的新聞信息。子目錄孫目錄下的網(wǎng)頁主題，相關(guān)性更強。因此我們利用這一特點，對最好優(yōu)先搜索策略做了改進。

根據(jù)網(wǎng)站的結(jié)構(gòu)，如果一個網(wǎng)頁的URL是另一個網(wǎng)頁URL的網(wǎng)站目錄，例如：新浪新聞 http：//news．sina．com．cn/是新浪國內(nèi)新聞 http：//news．sina．com．cn/China/的目錄，稱新浪新聞 http：//news．sina．com．cn/為上行鏈，稱新浪國內(nèi)新聞 http：//news．sina．com．cn/China/下行鏈。 同時再為每個網(wǎng)頁的URL分別設(shè)置父鏈、祖先鏈。如果搜索的網(wǎng)頁有上行鏈，則設(shè)置該URL的祖先鏈為這個網(wǎng)頁的上行鏈，否則為空；父鏈則是用于存放提取這個URL的網(wǎng)頁的URL。

永州市涔天河庫區(qū)位于湘江流域上游，是永州地區(qū)重要的水源地，其流域控制面積為2423平方公里，多年平均產(chǎn)水量26億立方米，正常蓄水位254.26 m，總庫容1.05億立方米。該工程是湘江流域上游龍頭水利工程，擴建后將形成湖南省最大的灌區(qū)。涔天河庫區(qū)擴建工程可謂“牽一發(fā)而動全身”，不僅占用了大量的土地資源，而且對周圍環(huán)境也產(chǎn)生了巨大的影響。水庫擴建工程浩大，大量人力物力的投入，以及對區(qū)域物質(zhì)能量的擾動，使流域生態(tài)系統(tǒng)的穩(wěn)定性受到一定程度的影響。

最好優(yōu)先搜索策略改進的主要思想：當網(wǎng)絡(luò)爬蟲在進行最好優(yōu)先搜索時，如果遇到一個與主題相關(guān)的網(wǎng)站，就將這個網(wǎng)站內(nèi)的所有具有相同目錄的網(wǎng)頁直接下載，并將這些URL放到搜索隊列中，作為以后搜索到對象，跳過對這些URL進行網(wǎng)頁相關(guān)度計算。

最好優(yōu)先搜索策略改進算法流程圖如圖1所示，描述如下：

（1）將原始URL集加入到網(wǎng)絡(luò)爬蟲搜索隊列中，運行網(wǎng)絡(luò)爬蟲。

（2）在搜索隊列中提取一個請求路徑A，搜索下載網(wǎng)頁，提取A網(wǎng)頁中新的請求路徑B。

（3）對比請求路徑，將請求路徑B和A的祖先鏈比較，如果請求路徑B的開頭為A的祖先鏈，則標記B的祖先鏈為A的祖先鏈且B的父鏈為A，加入到搜索隊列中，跳轉(zhuǎn)到步驟（2）；否則比較A的父鏈和請求路徑B進行比較；如果請求路徑B的開頭為A的父鏈，B的祖先鏈為A的父鏈且B的父鏈也A，加入到搜索隊列中，跳轉(zhuǎn)到步驟（2），否則將請求路徑B和A比較，如果B的開頭為A，則B的祖先鏈為A且B的父親鏈為A，跳轉(zhuǎn)到步驟（2），否則標記A的父鏈的B，祖先鏈為空，跳轉(zhuǎn)到步驟（4）。

（4）對新提取出請求路徑URL，下載網(wǎng)頁，對網(wǎng)頁進行預(yù)處理，獲取純文本。

（5）純文本分詞，提取關(guān)鍵字作為網(wǎng)頁的特征項。

（6）特征項的權(quán)重計算，計算網(wǎng)頁中的特征項的權(quán)重。

（7）相似度計算，利用向量空間模型計算網(wǎng)頁與主題之間的相似度。如果相似度大于或等于閾值f，則網(wǎng)頁與主題相關(guān)，加入到搜索隊列中；反之，丟棄這個URL。

圖1 最好優(yōu)先搜索策略搜索結(jié)果

3 實驗結(jié)果與分析

本實驗的硬件環(huán)境：CPU是 Pentium Dual-Core E6700，內(nèi)存4GB。

軟件環(huán)境：操作系統(tǒng)Windows XP，變成軟件Eclipse V3．5。

圖2 最好優(yōu)先搜索策略改進后的搜索結(jié)果

實驗內(nèi)容是在給定一個新浪軍事新聞 ：http：//mil．news．sina．com．cn/的請求路徑，并指定其終止的條件是：“臺媒：菲律賓與中國在南海激烈對峙”，分別利用改進前與改進后的算法進行搜索，然后計算運行的時間。圖1是改進前的算法用時299921毫秒，在圖2是改進后算法的用時為233676毫秒?？梢钥闯龈倪M后的算法明顯提高了搜索速度。

4 結(jié)論

由于網(wǎng)站開發(fā)過程中，大部分開發(fā)人員都會根據(jù)主題為每個網(wǎng)頁劃分各個目錄，每個目錄存放的網(wǎng)頁主題都是相似的，因此在網(wǎng)絡(luò)爬蟲搜索過程中，碰到目錄相同的網(wǎng)頁，直接放入搜索隊列中，這樣省去了這些網(wǎng)頁的分析評價時間，從而提高爬蟲的搜索效率。根據(jù)這種思路對最好優(yōu)先搜索算法做了改進，并進行了實驗驗證，實驗結(jié)果表明改進后的算法明顯提高了搜索速度。

［1］李耀華,楊海燕．論網(wǎng)絡(luò)爬蟲搜索策略[J]．山西廣播電視大學(xué)學(xué)報,2013(2)：48-50．

［2］S．E．Robertson．Theprobability ranking principle in IR[J]．Journal of Documentation，1977，33：294－304．