一種改進(jìn)的最好優(yōu)先搜索策略算法

余兆釵 傅化權(quán)

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

實(shí)驗(yàn)內(nèi)容是在給定一個(gè)新浪軍事新聞 ：http：//mil．news．sina．com．cn/的請(qǐng)求路徑，并指定其終止的條件是：“臺(tái)媒：菲律賓與中國(guó)在南海激烈對(duì)峙”，分別利用改進(jìn)前與改進(jìn)后的算法進(jìn)行搜索，然后計(jì)算運(yùn)行的時(shí)間。圖1是改進(jìn)前的算法用時(shí)299921毫秒，在圖2是改進(jìn)后算法的用時(shí)為233676毫秒。可以看出改進(jìn)后的算法明顯提高了搜索速度。

4 結(jié)論

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

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

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