垂直搜索引擎爬蟲系統(tǒng)DIPRE算法及改進(jìn)

趙君

摘 要：針對垂直搜索引擎中精確抽取網(wǎng)頁中特定字段的問題，對DIPRE算法進(jìn)行了研究和改進(jìn)。闡述了DIPRE算法在垂直搜索引擎中的重要作用，探討了DIPRE算法在抽取復(fù)雜結(jié)構(gòu)網(wǎng)頁時(shí)的不足，并提出了改進(jìn)，包括種子定位方式，將單模匹配擴(kuò)展成多模匹配并引入定位索引，再根據(jù)已有技術(shù)對改進(jìn)后的算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證。結(jié)果表明，改進(jìn)后的算法在精度和效率上都符合預(yù)期。

關(guān)鍵詞關(guān)鍵詞：垂直搜索引擎；DIPRE算法；種子定位；單模匹配；多模匹配；定位索引

DOIDOI：10.11907/rjdk.161451

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2016）008-0030-03

0 引言

垂直搜索引擎是針對某一特定領(lǐng)域、人群或需求提供的信息檢索服務(wù)，因此垂直搜索引擎的爬蟲（Spider）在抽取數(shù)據(jù)時(shí)應(yīng)該具有相當(dāng)?shù)倪x擇性。DIPRE（Dual Iterative Pattern Relation Extraction）是Google創(chuàng)始人之一Sergey Brin針對抽取互聯(lián)網(wǎng)上特定格式或類型的數(shù)據(jù)而提出的一種算法，由于垂直搜索引擎具有較強(qiáng)的專業(yè)性和針對性，因而DIPRE算法在垂直搜索領(lǐng)域里具有較為廣闊的應(yīng)用前景，但隨著Internet上的信息量呈指數(shù)級增長，網(wǎng)頁結(jié)構(gòu)越來越多樣化，利用DIPRE算法抽取數(shù)據(jù)無論是在廣度還是在精度上都已遇到瓶頸[1]，如何在發(fā)揮DIPRE算法優(yōu)勢的基礎(chǔ)上彌補(bǔ)其不足成為一個值得研究的問題。

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

實(shí)驗(yàn)以某大型網(wǎng)上書城的圖書信息為檢索對象，包括作者、出版社、出版時(shí)間、版次、頁數(shù)共5個字段，此5個字段之間不含噪聲，是測試的理想之選。使用的服務(wù)器配置如表2所示。

以采集40萬條數(shù)據(jù)為測試目標(biāo)，采用兩種算法的爬蟲檢索性能情況如表3所示。

通過抽樣檢測，以上檢索的ER值均低于10%。根據(jù)表3繪制出性能對比圖，如圖4所示。

由式（3）、式（5）和圖4可知，爬蟲檢索頁面時(shí)間和頁面數(shù)量呈線性關(guān)系，其中采用傳統(tǒng)DIPRE算法的斜率為t1+α·β·t2，采用改進(jìn)后算法的斜率為t1+α·γ·t2；改進(jìn)后算法的效率要略低于原算法，即γ值要大于β值。

4 結(jié)語

本文對DIPRE算法進(jìn)行了擴(kuò)展和改進(jìn)，將原算法中的單模模式擴(kuò)展成多模模式，同時(shí)引入定位索引，使得改進(jìn)后的算法具有很強(qiáng)的實(shí)用性和可擴(kuò)展性。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后算法的性能曲線斜率要比原算法的大，效率比原算法低，這是因?yàn)閨|過小導(dǎo)致無法有效過濾數(shù)據(jù)，使得L遠(yuǎn)大于R中字段數(shù)量，爬蟲檢索了很多無效值，降低了檢索效率。在后續(xù)改進(jìn)中，重點(diǎn)在于降低式（5）中的值，即L的值，這就必須使||達(dá)到一個合理的范圍，圖2中闡述的前后綴延伸方法是個不錯的解決方案，如何控制延伸的程度則是后續(xù)研究的主要內(nèi)容。

參考文獻(xiàn)：

[1]OREN KURLAND，LILLIAN LEE.PageRank without hyperlinks[J].ACM Transactions on Information Systems （TOIS），2010，28（4）：1-38.

[2]LIU GUI-MEI.An adaptive improvement on PageRank algorithm[J].Applied Mathematics：A Journal of Chinese Universities（Series B），2013，28（1）：17-26.

[3]GHOLAM R AMIN，ALI EMROUZNEJAD.Optimizing search engines results using linear programming[J].Expert Systems With Applications，2011，38（9）：11534-11537.

[4]LIN LI，GUANDONG XU，YANCHUN ZHANG，et al.Random walk based rank aggregation to improving web search[J].Knowledge-Based Systems，2011，24（7）：943-951.

[5]E GARCIA，F(xiàn) PEDROCHE，M ROMANCE.On the localization of the personalized PageRank of complex networks[J]. Linear Algebra and Its Applications，2013，439（3）：640-652.

[6]SHAYAN A，TABRIZI，AZADEH SHAKERY，et al.Personalized pagerank clustering：a graph clustering algorithm based on random walks[J].Physica A：Statistical Mechanics and its Applications，2013，12（5）：15-24.

[7]ALEXGOH KWANG LENG，P RAVI KUMAR，ASHUTOSHKUMAR SINGH，et al.Link-Based spam algorithms in adversarial information retrieval[J].Cybernetics and Systems，2012，43（6）：459-475.

[8]LI LIAN，ZHU AI HONG，SU TAO.An improved text similarity calculation algorithm based on vsm[J].Advanced Materials Research，2011，1250（225）：1105-1108.

[9]LI MIN，ZHAO JUN.Research and design of the crawler system in a vertical search engine[C].Guilin：In Proceedings of the 2010 International Conference on Intelligent Computing and Integrated Systems，2010：790-792.

[10]EVANTHIA E TRIPOLITI，DIMITRIOS I FOTIADIS，GEORGE MANIS.Modifications of the construction and voting mechanisms of the random forests algorithm[J].Data & Knowledge Engineering，2013，87（7）：112-118.

[11]柳廳文，孫永，卜東波，等.正則表達(dá)式分組的1/（1-1/k）-近似算法[J].軟件學(xué)報(bào)，2012，23（9）：2261-2272.

（責(zé)任編輯：孫 娟）