垂直搜索引擎爬蟲系統DIPRE算法及改進

趙君

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

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

DOIDOI：10.11907/rjdk.161451

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2016）008-0030-03

0 引言

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

3 實驗結果

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

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

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

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

4 結語

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

參考文獻：

[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 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]柳廳文，孫永，卜東波，等.正則表達式分組的1/（1-1/k）-近似算法[J].軟件學報，2012，23（9）：2261-2272.

（責任編輯：孫 娟）