結合有監督廣度優先搜索策略的通用垂直爬蟲方法

高 峰,劉 震,b,高 輝,b

(電子科技大學 a.計算機科學與工程學院; b.大數據研究中心,成都 611731)

0 概述

隨著互聯網的蓬勃發展,互聯網信息數量呈現爆炸性的增長。對互聯網用戶來說,一個很重要的問題就是如何才能快速的找到其想要的網頁內容。信息增長的速度越快,用戶的這種需求就越迫切。

傳統的垂直爬蟲是獲取特定網站或特定主題內容數據較為普遍的方法,但是垂直爬蟲的一大弊端就是無法實現通用的爬取,需要針對不同的網站重新設計程序,而且人工查找URL隊列及人工提取數據解析路徑的工作更為繁瑣,大大影響了工作效率。一般情況下,一個單獨的爬蟲程序只能處理某個獨立站點的某一類型結構的頁面數據。而用戶對于數據的需求是多種多樣的,如果對于每一個網站的數據需求都需要一個相應的爬蟲程序比較費時費力,同時也會影響對應工作或項目的推進速度。

針對上述問題,本文提出一種配置簡單、高效且可移植性高的通用爬蟲設計方法。其核心思想是將通用型爬蟲分為配置信息、初始化和正式爬取3個階段。在配置信息階段,用戶針對待爬取網站完成基本信息配置;在初始化階段,自動識別主題相關目標頁面URL和目錄頁面URL,生成解析路徑模板并且采用URL聚類的方法抽取出URL正則表達式過濾器;在正式的網頁爬取階段,利用初始化階段生成的正則表達式過濾器和解析路徑模板,以及有監督的廣度優先與網頁賦權搜索策略,實現對目標頁面數據的快速準確提取。在此基礎上,本文提出一種GWC(General Web Crawler)原型系統,并且在該原型系統上進行了廣泛的實驗。

1 相關研究

目前比較流行的自動化信息抽取工具有RoadRunner[1]、MDR[2]以及基于MDR的改進方法Depta[3-6]等。但這些工具的目標都是從結構相似的網頁,如目錄列表頁面、查詢結果頁面或表格中,抽取信息,因為這類頁面中的數據記錄子樹具有相似的結構,所以利用子樹相似度算法的研究可達到較好的數據抽取效果,但是該類方法對待抽取網頁中信息的結構化程度要求比較嚴格,這也是該類抽取方法最大的局限。文獻[7-8]對于評論信息的抽取也屬于該類抽取方法,文獻[9]利用深層的匹配節點越多,2棵樹的相似度越大的思想,提出一種高效的深度加權的樹相似性算法,其對于每一個評論記錄中具體數據項的抽取進行了詳細深入的研究,但是同樣也僅適用于評論信息的抽取。同時,這些方法僅利用HTML標簽及結構信息,缺乏語義表達能力,最近很多研究已經注意到這個問題,并且利用頁面的視覺信息來實現Web數據的抽取[10,11]。

目前,國內外對正文信息的抽取也有較多的研究。文獻[12]設計的Crunch系統利用區域中鏈接文本/普通文本(link/text)的比值與某個既定閾值的大小關系來確定網頁的正文區域。文獻[13]改進文獻[12]方法,將基于鏈接/文本比率和基于文本量的方法以類似于信息論中信息量計算的方式進行結合,對博客類網頁的信息抽取達到較好的效果。目前對正文信息抽取的研究大多適用于信息量較大的網頁,如新聞、博客、論壇等,對于正文信息量較少的網頁抽取效果并不好,如大眾點評網等。而且有些方法對于一些閾值的設置介紹并不明確,存在依靠經驗設置的不足。

針對上述研究的不足,設計一種通用的垂直爬蟲技術是非常有必要的,而本文設計方法能夠對不同網站不同類型的網頁實現快速、準確的數據爬取和閾值的動態自動設置。

2 GWC原型系統整體框架

通過配置簡單少量的信息,指導爬蟲搜索策略的設計和數據解析路徑自動提取,是本文通用型垂直爬蟲的設計前提。本文研究方法將用到的幾個基本配置信息如表1所示。

表1 基本配置信息

GWC原型系統的整體框架如圖1所示,根據預先配置的少量基本信息,從不同網站中快速實現定制化數據精確提取,無需二次處理,并將數據存儲到數據庫。

圖1 GWC原型系統的整體框架

GWC原型系統主要模塊的功能介紹如下:

1)配置模塊:完成少量基本信息的配置,如入口鏈接、關鍵詞和目標爬取數據,指導爬蟲實現定制化數據抓取。

2)初始化模塊:在初始化階段預先爬取一定數量的URL,并自動識別出目標頁面URL和目錄頁面URL,同時生成URL正則表達式過濾器和數據精確解析路徑模板(Wrapper),其中,URL正則表達式過濾器包括目錄頁面正則表達式過濾器和目標頁面正則表達式過濾器。

3)正式爬取模塊:依據有監督的廣度優先與網頁帶權搜索策略實現目標頁面的抓取,使用數據精確解析路徑模板實現數據自動準確抽取。

在不需要修改源代碼的前提下,僅通過修改少量配置信息即可對不同網站實現快速、準確的定制化信息爬取存在兩大難點:1)如何設計高效準確的通用型爬蟲搜索策略;2)如何實現數據解析路徑自動提取。針對以上2個難點,本文提出一種較為有效的通用型垂直爬蟲設計方法。

3 有監督的廣度優先網頁帶權搜索策略

網頁的抓取策略通常可以分為深度優先、廣度優先和最佳優先3種。深度優先在很多情況下會導致爬蟲的陷入問題,目前常見的是廣度優先和最佳優先方法。本文采用的是有監督的廣度優先網頁帶權搜索策略,利用正則表達式過濾器廣度優先大范圍搜索相關頁面,同時輔以基于隧道技術的網頁權值計算達到有監督的最佳優先效果。本文設計的搜索策略能夠保證爬蟲充分、快速、準確的對相關頁面進行定位及下載。

在很多情況下,垂直爬蟲都是被設計用來只抓取某個指定網站中的特定主題網頁,而對于這些頁面的搜索通常設計人員會預先在網頁源碼中人工分析出所要解析的URL,將這些URL的解析路徑預先寫入到程序中,并且通常可能會預先人工維護一個初始爬取URL隊列,以保證爬蟲程序在運行過程中充分、精準的從頁面中解析出相關的URL,從而過濾掉所有的噪音URL,這些工作耗費大量時間和精力。合理的搜索策略將保證爬蟲減少無關頁面的下載和避免陷入的問題,將極大地保證爬蟲的爬取效率和爬取數據的準確性。為此,本文采用一種高效的有監督的廣度優先網頁帶權搜索策略。

3.1 正則表達式過濾器

正則表達式過濾器包括目錄頁面正則表達式過濾器和目標頁面正則表達式過濾器。它的作用包括2個方面:一是當解析頁面的HTML文件獲取到URL時,先用過濾器進行判斷,如果URL與正則表達式匹配,則放入待爬取隊列,如果不匹配,則過濾掉該URL,同時用以區分目標頁面和目錄頁面進行不同的網頁解析;二是在計算頁面權值時作為一個計算參數,用來判斷頁面是否包含目標頁面URL。

在初始化階段,利用預先配置的有限的入口鏈接和關鍵詞信息,使程序在預爬取一定數量的頁面后可以自動準確的找到目標頁面URL和目錄頁面URL并為目錄URL分類,最后將每一類URL抽取出正則表達式,實現過程如下描述。

預配置的入口鏈接一般都是初始目錄頁面鏈接,而需要通過這個入口在網站中找到所有的目標頁面URL,因為之前沒有配置目標頁面URL信息,所以初始時程序并不知道待爬取的目標頁面URL的格式,相關信息只有預先配置的少量關鍵詞信息(關鍵詞是目標頁面的標識信息),同時目標頁面與目錄頁面中所包含的URL數量存在較大差異,而且目標頁面在網站中數量也通常是較大的,利用這些有限信息完成對目標頁面URL的識別和相關目錄頁面的分類。

初始化階段預先從入口鏈接廣度優先爬取一定數量的頁面(一般4 000個～5 000個就可以滿足需求),并且在爬取過程中每下載一個URL則判斷該頁面是否包含關鍵詞信息,如果包含則將頁面權值置為0,否則在父頁面權值的基礎上加1(在后續部分會有帶權網頁計算的詳細介紹,而此部分只利用關鍵詞作為網頁權值計算參數),然后將帶權值的網頁URL加入到爬取隊列中,在程序進行下一次爬取時會優先下載權值低的URL,這樣會保證程序在有限的預爬取時間里盡可能多地爬取到與主題相關的目標頁面和目錄頁面URL。同時在下載頁面時會統計并保存該頁面所包含的URL數量。當預設數量的頁面爬取結束后,通過計算入口鏈接頁面包含的URL數量與這些下載頁面包含的URL數量的差值,并取差值的平均值作為區分目錄頁面和目標頁面的閾值,然后程序對這些URL數量差值大于這個閾值頁面URL進行聚類,最大的類則為預期的目標頁面URL類,再通過URL正則表達式的生成規則抽取出目標頁面正則表達式過濾器。最后將預爬取到的所有URL進行聚類,剔除掉目標頁面URL類,則剩下的URL類即是目標頁面URL類。而通常聚類的數量很多,通過大量實驗證明本文只取前10個最大的類即可包含所有主要目錄頁面類別,并分別抽取出正則表達式作為目錄頁面URL正則表達式過濾器。

本文將這一階段定義為初始化階段,在初始化階段抽取出URL正則表達式過濾器和提取數據解析路徑模板。

3.1.1 URL正則表達式的生成規則

首先介紹URL的數據結構。把一個URL分成3個部分(去掉http協議部分):Host,Path和Query。其中,Path由一系列directory參數組成,Query由一系列鍵值對組成。例如URL為http://news.qq.com/a/20150415/044667.htm?tu_biz=1.114.1.0&du=1,其中,Host為news.qq.com,Path為/a/20150415/044667.htm,Query為tu_biz=1.114.1.0&du=1,組成該Query的鍵值對為(tu_biz,1.114.1.0)和(du,1)。

由于本文設計的通用型垂直爬蟲每次的爬取都是針對某個特定網站,所解析到的URL都是該網站中的URL,因此無論是對于每一類的目標頁面還是目錄頁面的正則表達式生成,都會將Host部分直接保留下來,而Path和Query部分都是將其細分,然后對每一個參數都在同類URL中提取共有的正則表達式規則。通過對大量網站的觀察,本文總結出常見的URL正則表達式生成規則,如表2所示,其基本包括了URL常見的參數形式。

表2 正則表達式生成規則

3.1.2 URL聚類

由于可獲取到的主題相關目錄頁面不止一個,這些目錄頁面依據它們的URL結構特點可以劃分聚合成不同的種類,而每一類可以將其依據URL正則表達式的生成規則自動抽取出這一類URL的正則表達式作為其過濾器。

每條URL本質就是一個由簡單字符組成的字符串,URL聚類的實質就是將相似的URL字符串劃分為同一類,因此URL聚類的關鍵就是URL字符串相似度的計算。根據URL的結構,由于本文針對的是特定網站的爬取,因此每一類的Host部分必然是相同的,Path部分不同數量的directory參數和參數值的不同決定了該條URL所指向的同一網站不同類型的網頁,而Query部分的距離不用于對2條URL距離的判斷,如果2條URL除了Query其他部分都相同,則這2個鏈接指向的頁面基本是由同一個模板產生或屬于同一主題,因此URL相似度計算的關鍵就是Path部分相似度的計算。而Path部分的每一個directory參數都具有不同的實際意義,參數之間也通常會有較大的差別,并且每一位置的相似度對于整條URL的相似度貢獻值是不同的,位置越靠前的參數相似度越高也就意味著URL的相似度越高。因此,將Path部分整體作為一個字符串進行比較顯然是不合理的,需要將Path部分按directory參數進行拆分,對每一個參數分別進行相似度計算,再將參數的相似度進行整合從而得到2條URL的相似度。經過大量網站的觀察發現,Path部分的directory參數基本都是非常短的字符串,長度基本在20個字符以內。常見的字符串相似度算法有編輯距離算法、最長公共子串算法、貪心字符串匹配算法等,對于較短字符串的相似度計算,算法之間的時間效率差別不大,因此本文選擇了常見的計算簡單的編輯距離算法進行URL的相似度計算。

基于上文中介紹的URL數據結構,本文利用各個部分的距離來計算URL之間的相似度。2條URLi、j的相似度用sURLij表示,首先要判斷2條URL的Host部分是否相同,若Hosti≠Hostj,則直接將sURLij值置為0,若Hosti=Hostj,判斷Path部分的長度(即參數個數)是否相等,如果Path_Lengthi≠Path_Lengthj,也將sURLij直接置為0,這兩步的計算是為了保證將Host部分不同的URL以及Host部分相同但Path部分長度不同的URL直接聚合成不同的類,即聚成的每一個URL類都必須保證Host部分相同而且Path部分長度也相同。

當Hosti=Hostj且Path_Lengthi=Path_Lengthj時,分別計算出2條URL的Path部分每一位置directory參數的編輯距離edit,并做歸一化處理,將每一部分參數的編輯距離與該部分參數的理論上最大編輯距離(即2條待比較串最長串的長度)做比值,URL之間越相似其相似度的值應該越大,因此將URL比值加1再取倒數。同時,由于Path部分每一位置的directory參數具有實際意義,而且每一位置的參數對于整條URL相似度的貢獻度是不同的,位置越靠前的參數相似度越高就意味著整個URL的相似度越高,因此將每一部分directory參數設置不同的URL相似度參數,如果Path有m個參數,則第一個位置的參數對應的URL相似度參數為m,其余部分參數的URL相似度參數值依次遞減,最后將所有位置參數得到的編輯距離比值倒數與對應位置參數的URL相似度參數乘積求和即為2條URL的相似度。若2個URL的Path部分有m個參數,則URL距離計算公式如下所示:

(1)

其中,m為每條URL Path部分的directory個數,editk為2條URL第k個位置對應的2個directory參數的編輯距離,而max_editk則表示對應的2個directory參數理論上最大的編輯距離,即長度最大的directory參數的長度。

在聚類時通過URL相似度計算公式得到2條URL的相似度,而聚為一類的URL之間的相似度都不小于一個閾值h,本文對于相似度閾值的設定是自動動態設定的,相似度的閾值計算公式為:

(2)

其中,m為每條URL Path部分的directory個數。若滿足閾值條件則聚為一類,如果小于閾值則以該條URL為基準新建一個類。URL聚類算法描述如下:

算法1URL聚類算法

輸入URL_Queue;//輸入為一個URL隊列

輸出URL_Regex_Queue;//輸出URL正則表達式//隊列

1.創建一個URL聚類隊列URL_Cluster_Queue;

2.while(URL_Queue不為空){

3.從URL_Queue取出一個Url;

4.If(URL_Cluster_Queue 為空){

5.初始化一個僅包含該Url的聚類URL_Cluster;

6.將該聚類添加到隊列URL_Cluster_Queue;

7.}

8.Else{

9.Boolean flag=false;

10.foreach(URL_Cluster in URL_Cluster_Queue){

11.sURL= Url與URL_Cluster中每個url的相似度均值;

12.If(sURL>=h){

13.將Url添加到該聚類URL_Cluster;

14.flag=true;

15.break;

16.}

17.}

18.If(flag==false){

19.初始化僅包含該url的新聚類URL_Cluster;

20.將新URL_Cluster 添加到URL_Cluster_Queue;

21.}

22.}

23.}

24.對URL_Cluster_Queue中的每個聚類生成對一個正則表達式,輸出到URL_Regex_Queue

在所有的URL聚類結束后,使用URL正則表達式的生成規則為每一類URL抽取出對應類的URL正則表達式,作為目錄頁面正則表達式過濾器,其示例為:

[http://www.dianping.com/shop/[0-9]+(.[a-zA-Z]+)?/?,http://www.dianping.com/search/category/[0-9]+/[0-9]+/w+(.[a-zA-Z]+)?/?,http://www.dianping.com/mylist/[0-9]+(.[a-zA-Z]+)?/?,http://www.dianping.com/member/[0-9]+(.[a-zA-Z]+)?/?,http://www.dianping.com/search/keyword/[0-9]+/.*(.[a-zA-Z]+)?/?,http://www.dianping.com/[a-zA-Z]+/food(.[a-zA-Z]+)?/?,http://www.dianping.com/member/[0-9]+/badge/[0-9]+(.[a-zA-Z]+)?/?]

3.2 帶權網頁計算

大部分網站都可以看作3層結構(如圖2所示):初始種子頁面,目錄頁面,目標頁面(無關頁面)。網絡爬蟲在這種網頁結構上不斷的向深度和廣度游走,搜索與目標主題相關的頁面,最終目標是搜索到全部目標頁面,而在這個過程中將會經過大量的無關頁面和相關的目錄頁面。如果爬蟲沿著無關頁面深度搜索下去將遠遠偏離目標頁面,極大地影響爬蟲的工作效率和爬取數據的準確性。為此,本文提出有監督的廣度優先與網頁帶權搜索策略,以保證爬蟲能夠在網站3層結構中沿著正確的方向游走,減少無關頁面的下載,提高搜索效率,而該策略最關鍵的就是帶權網頁的計算。

圖2 網站3層結構

基于這種網站3層結構,通用型垂直爬蟲的設計在爬取時將其劃分為2個階段,初始化階段和正式爬取階段。在初始化階段,預爬取大量URL找到盡可能多地與目標頁面相關的目錄頁面,從而生成目錄頁面正則表達式過濾器。對于確定一個頁面是否是目錄頁面,本文采用目標頁面正則表達式和目標頁面關鍵詞相結合的方法,如下文詳細介紹。

3.2.1 主題孤島問題

文獻[14]提出在實際的網絡中主題相關的網頁并不總是連在一起的,從一個主題相關的頁面鏈接到另一個主題相關頁面經常需要穿過多個無關頁面,因此也造成網絡中存在主題孤島的現象,即一個主題島周圍往往會被一些主題無關頁面包圍致使與其他主題島分割。

文獻[15]提出了一種簡單的隧道技術來解決主題孤島問題,它們將每個頁面設置一個權值,如果該頁面是主題相關頁面,則它的權值置為0,如果是主題無關頁面,則該頁面的權值在其父頁面的權值基礎上加1。如圖3所示,節點代表頁面,加黑節點代表主題相關頁面,其他節點代表主題無關頁面,箭頭代表一張頁面到另一張頁面的鏈接。根據隧道技術,節點1代表的頁面的權值為0,節點2、3、4代表的頁面的權值為1,節點5代表的頁面的權值為0,節點6、7、8代表的頁面的權值為2,節點9代表的頁面的權值為0,而節點10代表的頁面的權值為1。垂直爬蟲在爬取時只抓取權值小于一個閾值的頁面,如閾值為2,則節點6、7、8、9、10代表的頁面都不會被抓取,如果閥值設為大于2,那么圖3中的所有頁面都將會被抓取。

圖3 頁面距離示意圖

3.2.2 基于隧道技術的網頁權值計算

本文在上述隧道技術的基礎上,明確了與目標頁面相關網頁的判斷和權值計算:對于任意頁面URL1,如果URL1對應的HTML文檔包含指向目標頁面的URL即有可通過目標頁面正則表達式過濾器的URL,或者該HTML文檔中包含配置文件中的關鍵詞,則將該URL1的權值置0,當沒有關鍵詞,而且不指向相關頁面時,則URL1的權值在指向它的頁面的權值基礎上加1。例如,設URL1中指向其他頁面的任意一個URL為URL2,若URL2對應的HTML文檔包含指向目標頁面的URL或者包含關鍵詞,則權值置0,否則在URL1權值的基礎上加1。

URLWeight=

(3)

其中,URLWeight表示網頁的權值。

按照上述定義,URL權值越大代表該URL與目標頁面關系越小。設置不同的閾值爬取的效果一般是不同的,以預爬取5 000個頁面為例,其中,隨機選取新浪股票網站抓取股票相關的頁面和大眾點評網抓取川菜主題相關的店鋪信息頁面結果為示例(此處只關心抓取到的與主題相關的頁面數量),不同閾值和條件爬取結果如表3所示。

表3 不同閾值和條件爬取結果

由表3可知,設置不同閾值對于爬取到的相關頁面數量是有影響的,其中新浪股票的結果不是很顯著,因為這是一個相對較大的專題,在開始爬取時就會有大量的相關頁面,而大眾點評的川菜專題相對較小,爬取時會遇到大量無關頁面。因為閾值的限定可以幫助程序找到更多的相關頁面,所以大眾點評的結果就更為顯著一些。而本文是利用初始化階段預爬取的效果使程序自動預設一個URL權值的閾值,該閾值是所有預爬取頁面權值的平均值并取四舍五入后的值。

系統在進行關鍵字判斷時,首先會剔除HTML文檔中所有a[href]標簽的屬性值和文本內容,因為這樣可以大大減少因跳轉鏈接的不相關內容導致爬取到其他無關頁面,從而得到更準確的判斷且去除干擾使結果更加干凈,而且也會使保存異常結果的文件中的異常結果大大減少。

4 數據解析路徑模板自動抽取

每一個實體數據節點在網頁中都對應一條唯一的XPath路徑,爬蟲在解析實體數據時就是根據這條解析路徑抽取出對應數據項,而實體數據的XPath路徑通常需要開發人員在網頁源碼中人工分析,或者借助其他工具提取。為實現爬蟲程序自動提取數據解析路徑,生成所需實體數據標簽的提取路徑模板,本文設計了有效的數據解析路徑抽取算法。例如大眾點評網中北京新世紀日航飯店這個目標頁面,輸入標題“北京新世紀日航飯店”,可以得到標題所在的路徑,之后所有的目標頁面都可以從該路徑中提取標題信息。

目標頁面模板生成基本流程如圖4所示。

圖4 目標頁面模板生成流程

從預先配置的基本信息中讀取前2條目標頁面URL(可先分別記為A、B),并將它們的HTML文件下載下來,以這2個頁面為模板,將它們的HTML文件解析成HTML樹形結構,然后取出2棵樹中相同的結點,形成一棵新的樹,新生成的樹即為該頁面類型的模板。對于2棵樹A和B,先只遍歷樹A,將A中結點放入節點隊列的同時將該節點的父節點路徑也放入隊列。這里定義的路徑是符合jsoup查詢語法的從根節點到該節點的路徑,這樣做的好處是將路徑保存起來之后可以直接使用。從隊列中提取節點時,先用jsoup查找樹B中相同路徑下是否存在相同的節點,若存在,就把該節點和該節點的路徑放入隊列,且對于葉子節點和非葉子節點需存在不同隊列。遍歷完后便得到了2棵樹所有相同葉子節點的路徑,這樣便形成了一棵樹,即形成了網頁模板。

在得到公共節點及節點路徑的模板后,需要根據預先配置的目標爬取實體數據信息確定待爬取數據的精確解析路徑,實現數據的定制化爬取。其實現思想是:依次從預先配置的目標爬取數據文件中取出每個需爬取的實體數據標簽內容,并以標簽內容為依據先遍歷已保存的葉子節點隊列,若找到了一個葉子節點的文本內容或屬性值與標簽內容相等,則將該葉子節點及該節點的路徑保存到相應的隊列中,如果葉子節點沒有所需的標簽,則自底向上遍歷非葉子結點完成同樣的動作,若葉子節點和非葉子節點隊列中都沒有找到與標簽內容相等的節點,則查找包含實體數據標簽內容的節點;然后將找到的節點路徑向根節點回溯,每回溯一個節點時,如果該節點在同一層兄弟節點中沒有同名節點,則在節點路徑中直接保存其節點名即可,若同一層中有同名節點,需先判斷是否有能區分其他同名節點的屬性值(包括id、class及其他屬性),如果有則在路徑中保存該節點名的同時保存該屬性名及屬性值,若同名節點中沒有這種屬性,則需保存該節點在這層同名中的相對位置,以便其他節點準確找到該節點。

當所需爬取的標簽內容數量不固定的時候(如評論),在提取準確路徑時,將這2個標簽的路徑都提取出來,如以下2條路徑:

1)div[class=tent]>li:nth-of-type(1)>p[class=info]>span:nth-of-type(2)。

2)div[class=tent]>li:nth-of-type(2)>p[class=info]>span:nth-of-type(2)。

然后從路徑的最后一個節點往根節點回溯,并同時判斷2條路徑對應的節點是否是兄弟節點,如果不是則繼續回溯,如果是則將路徑的對應節點直接用節點名表示并停止回溯。

3)div[class=tent]> li>p[class=info]>span:nth-of-type(2)。

路徑3)是1)、2)這2條路徑的公共路徑,同時也代表了這類標簽的公共路徑,依據這條路徑,在正式爬取階段就可以將該類標簽內容全部解析出來。

經過以上流程,最終會得到需爬取標簽的通用解析路徑即通用模板,而這些路徑是以json格式保存到數據解析路徑模板文件中。其中,key是“標簽名稱#標簽內容所在部分”的形式表示,標簽內容所在部分指出了該標簽內容在節點中的位置,如果為text說明在節點的內容部分,如果為某一屬性(如id),則說明標簽內容在節點中該屬性的值(如id="top"中的top)的部分,value則是符合jsoup解析規則的標簽的通用路徑。示例如圖5所示。

圖5 通用路徑示例

依據上述描述,本文數據解析路徑模板自動抽取算法包括2部分,如下所示:

算法2公共網頁模板提取

輸入Dom_Tree1,Dom_Tree2

//預先配置的2個目標頁面的DOM樹

輸出Leaf_queue,Non_leaf_queue

//保存葉節點路徑的隊列和非葉節點路徑的隊列

1.取Dom_Tree1根節點root1;

2.將root1和空路徑加入新建節點隊列Nodequeue;

3.//隊列Nodequeue中每個元素保存一個節點和父節點//路徑

4.While(Nodequeue不為空){

5.取Nodequeue隊頭節點node和父節點路徑;

6.計算node節點路徑NodePath =父節點路徑+">"+node節點名;

7.If(用NodePath在Dom_Tree2找到相同節點node{

8.If(node沒有孩子節點)

9.將node節點和節點路徑NodePath加入葉節點路徑隊列Leaf_queue;

10.Else{

11.將node節點和節點路徑NodePath加入非葉節點路徑隊列Non_leaf_queue;

12.foreach(childNode in node孩子節點){

13.將childNode和node節點路徑NodePath同時加入Nodequeue;

14.}

15.}

16.}

17.}

18.return Leaf_queue,Non_leaf_queue;

算法3精確節點路徑提取

輸入tags.json,Leaf_queue,Non_leaf_queue

//tags.json為預先配置的目標爬取實體數據

輸出accurate_nodepath_queue

//精確的節點解析路徑隊列

1.foreach(targetData in tags.json){

2.int flag1=0,flag2=0;

3.Node Tnode=null;

4.foreach(leafNode in Leaf_queue){ //遍歷葉子節點

5.If(leafNode文本數據或者屬性值等于targetData){

6.Tnode=leafNode;

7.flag1=1;

8.break;

9.}

10.else if(leafNod文本數據或者屬性值包含targetData){

11.Tnode=leafNode;

12.flag2=1;

13.continue;

14.}

15.}

16.While(flag1=0){

17.foreach(nonLeafNode in Non_leaf_queue){//遍歷非//葉子節點

18.If(nonLeafNode的文本數據或者屬性值等于 targetData){

19.Tnode=nonLeafNode;

20.flag1=1;

21.break;

22.}

23.else if(flag2==0&& nonLeafNode的文本數據或者屬性值包含targetData){

24.Tnode=nonLeafNode;

25.continue;

26.}

27.}

28.}

29.取Tnode 節點路徑TnodePath;

30.foreach(node in TnodePath){//反向遍歷節點路徑//TnodePath上的節點

31.If(node的兄弟節點中不存在同名節點){

32.在節點路徑TnodePath直接保留node節點名;

33.Continue;

34.}else if(node在兄弟同名節點中存在不同的屬性值)//{優先考慮ID和class屬性

35.在節點路徑TnodePath中對應的node節點名后面加上此屬性及屬性值;

36.Continue;

37.}else{

38.計算該節點node在兄弟同名節點中的相對位置并加入TnodePath中;

39.}

40.}

41.將遍歷修改后的TnodePath加入到精確解析路徑隊列accurate_nodepath_queue;

42.}

43.Ruturn accurate_NodePath_queue;

5 實驗結果與分析

5.1 實驗爬蟲設計

在概述部分介紹的信息抽取工具和方法都是針對某一類型的網頁實現數據的抓取,并不是可以對不同網站不同網頁實現抓取的通用信息抽取模型,并且對數據的抽取也較為粗略。而本文所設計的通用型垂直爬蟲設計方法,能夠對不同類型的網站實現快速精確的定制化數據爬取。兩者的實現方法和目標都不同,因此不適合進行實驗比較,并且目前對于通用型數據抽取方法研究的相關文獻較少,沒有找到合適的對比方法。但是本文發現了目前較為流行的一個數據采集應用產品——八爪魚數據采集器,該產品的應用目標和實現方法與本文提出的通用型垂直爬蟲設計方法較為相似,因此本文選擇與該產品進行實驗對比,以驗證本文方法的可行性和有效性。

本文設計的通用型垂直爬蟲GWC原型系統包括3個模塊:配置模塊——配置基本信息,預爬取模塊——在目標網站預先爬取4 000條URL,正式爬取模塊——完成定制化數據的正式爬取。該爬蟲程序由Java程序語言完成,并應用了HttpClient來模擬瀏覽器完成頁面的下載,使用Jsoup實現頁面的數據解析工作,而Redis則用來實現數據的去重處理和數據的存儲。實驗的軟硬件環境為Windows 7操作系統、AMD A8-5600K APU with Radeon(tm)HD Graphics 3.60 GHz處理器、8 GB安裝內存(RAM)、64位操作系統。

5.2 初始化階段實驗結果及分析

當配置信息配置完成后,GWC原型系統則開始進行初始化,預下載4 000個頁面即4 000條URL,完成URL正則表達式過濾器和通用路徑模板的生成。當達到預設的4 000個頁面閾值時,系統則會自動停止。GWC原型系統在初始化階段的爬取情況如圖6～圖8所示。

圖6 預爬取時間對比

圖7 頁面權值平均值對比

圖8 目標頁面URL識別準確率

由圖6可以看出,預爬取4 000個頁面基本可維持在11 min～13 min左右,不會耗費大量時間,偶爾也會因為網速等網絡環境原因達到15 min以上。但總體來說,僅需要十幾至二十分鐘的時間即可完成初始化的工作,為正式爬取階段做好必要的準備,具有較高的效率。

由圖7可以看出,每個網站爬取到相關頁面的頁面平均權值保持在一個穩定的閾值,不同的網站閾值分布也有差異,由于本文在網頁權值計算時將權值設置為整數,因此對頁面權值的平均值進行四舍五入取整即可,根據爬取結果以上測試的幾個網站在正式爬取階段均可將網頁權值閾值設置為1,在后續實驗中也證明了本文閾值的設置是合理的,可以保證程序充分準確的爬取到主題相關目標頁面。同時,圖8目標頁面URL識別準確率的結果也充分證明本文對目標頁面URL識別的方法完全可以保證識別的準確率,而且對于目錄頁面URL的分類和選取也同樣可以保證系統對于目標頁面的充分爬取(在正式爬取階段的結果可以體現)。

綜上實驗結果,本文設計的搜索策略可以保證爬蟲系統在短時間內抓取到足夠數量的相關目錄頁面,并且可以自動準確的識別出目標頁面URL,完成頁面權值閾值的設置,能夠準確的生成足夠數量的目錄頁面正則表達式過濾器以及目標爬取數據的通用路徑模板,為正式爬取階段做好準備。

5.3 正式爬取階段與現有通用爬蟲技術實驗對比

依據本文的實現策略設計的爬蟲系統與八爪魚數據采集器從爬取效率、數據完整性和數據準確性3個方面進行對比。

5.3.1 爬取效率

八爪魚僅可以爬取具有分頁列表的頁面,而且在爬取的過程中是以翻頁的方式進行采集,因此其在總爬取時間上是占優勢的。而GWC原型系統的批量爬取是采取有監督的廣度優先與網頁帶權搜索策略以全網站搜索的方式進行,因此總的爬取時間要慢一些,但也不是絕對的,有些時候在總的爬取時間上該系統還是會更快一些。一旦程序定位到了目標頁面的目錄頁面,GWC原型系統對于該目錄頁面的目標頁面數據抓取相對更快,而且單位時間內的網頁抓取效率也更優。

在爬取眾籌網數據時(30 min),GWC原型系統可以爬取2 000～3 000多條數據,而八爪魚即使是以翻頁的方式進行爬取,也只能爬取500～600多條數據。

當爬取新浪股票數據時(5 h),GWC原型系統可以爬取2 300～2 500條數據,雖然在正式爬取時其爬取總時間是15 h左右,而在實際爬取工作中,5 h～6 h即可爬取到近85%的數據量,剩余的10 h時間是為了保證爬取數據的數據量足夠多,以保證數據的完整性。而八爪魚在5 h的時間只抓取到了1 500多條數據,而且隨著爬取時間的增長,可以明顯觀察到其爬取速度在減慢。雖然GWC原型系統有時在總爬取時間上要慢一些,但是全網站搜索可以保證數據的完整性。

5.3.2 數據完整性

在前文提到,八爪魚僅可以爬取具有分頁列表的頁面,而一旦要爬取的目標頁面沒有給出分頁列表或者分頁列表數據不全時,就無法對數據進行批量采集或者采集的數據有大量的遺漏缺失。

以大眾點評網數據為例,爬取川菜專題時,網站顯示的總店鋪數量有近17 000家(而實際存在的只有14 000～15 000家左右,因為區域重疊和分類重疊的原因造成店鋪有重疊),而其分頁列表中則一共只給出了1 000多家店鋪,用八爪魚進行爬取只采集到了700多條數據,而GWC原型系統則采集到了14 000多條數據,但是要去掉2 000多條異常數據,在很大程度上保證了數據量的完整。對于八爪魚遺漏的數據,當然用戶可以花費一定時間去尋找其他分頁列表再次進行配置和爬取,但是對于其通用性和效率來說是有一定影響的,且進行再次爬取時會爬取到大量已下載的重復數據。即使分頁列表中給出了所有的數據量,經過幾次抓取測試,八爪魚也不會將數據爬取完全,仍然有大量數據遺漏丟失。

在爬取眾籌網數據(預期約4 400條)時,八爪魚在進行了1 h后即停止了爬取,但是其只爬到800多條數據,而經過幾次測試GWC原型系統則是在2 h后完成了爬取,與預期數據量相比數據誤差沒有超過20條數據。對于GWC原型系統而言,利用本文設計的搜索策略,采用全網站搜索的方式,因此在充分時間爬取后數據量基本可以達到預期效果,不會大量遺漏數據。

在爬取新浪股票數據(預期約4 400條)時,八爪魚在近11 h的時間爬取了2 600多條數據,而GWC原型系統則最終能夠爬取到近3 050條數據。圖9所示為3個例子的數據完整性對比圖。

圖9 3個例子的數據完整性對比

對于八爪魚而言,無法完成一個目標頁面中的數量不固定標簽數據(如評論)的爬取,只能一次爬取其中一條數據,如果強迫一次爬取所有數據則會增加大量無關的雜質數據。有些數據在HTML樹中的節點定位也不如GWC原型系統準確,即會造成在爬取數據時增加部分雜質數據。而GWC原型系統利用在初始化階段生成的目標爬取數據精確解析路徑模板,在正式爬取階段能夠準確直接的從目標頁面中找到目標數據節點,從而能夠準確的抽取出干凈的目標數據。因此,本系統的數據爬取相對更加完整干凈。

5.3.3 數據準確性

數據準確性是指是否爬取到主題目標頁面數據。八爪魚以翻頁的形式下載頁面,爬取數據的準確率很高,只要爬取的分頁列表中給出的目標頁面都是準確的,其準確率都可以達到100%,而對于大眾點評網,在川菜列表中同樣出現了很多火鍋、小吃快餐、西餐等其他類別的店鋪,八爪魚無法對這些非目標頁面過濾掉而是全部爬取下來,此時準確率也會降低。

GWC原型系統是采取有監督的廣度優先與網頁帶權搜索策略的形式隨機下載頁面爬取數據,因此,其數據的準確性對于不同的網站難以全部達到100%的準確性,但是經過大量測試,其也可以達到很高的準確率,有部分網站是可以達到100%。如果該網站的URL格式對于區分不同類別的頁面有很好的效果,則可以使系統生成一個非常準確的目標頁面正則表達式過濾器,再增加關鍵詞的輔助判斷,系統就能保證非常高的準確性。反之,如果該網站的URL格式不能很好地區分不同類別的頁面,準確性就會降低。但是關鍵詞如果選取合適,則可以保持或增加準確性。

表4和表5是每個網站爬取2次的結果,且隨機抽取20 min的爬取結果作為統計量。因為20 min的爬取時間較短,且每次程序都是隨機下載頁面,所以每個網站的2次爬取總量會有不定的差距。

表4 八爪魚數據準確性測試實例

表5 GWC原型系統數據準確性測試實例

從表4、表5可以看出,系統對于新浪股票、搜狐軍事、眾籌網等網站的爬取效果很好,準確性很高,對于這幾個大專題基本是可以達到100%的準確性,因為這些網站都有很好的URL格式,對于區分不同類別的網頁有決定性的效果,加上關鍵詞的判斷,所以準確率非常高。而對于大眾點評網這一類網站,許多類別頁面的URL格式是相同或類似的,程序不能生成一個準確的目標頁面正則表達式過濾器,對于有些網站,可以通過選擇準確合適的關鍵詞來進行輔助定位,也可以維持和提高準確性,例如爬取天涯論壇中的股市談論,其URL也不能做一個準確的區分,但是輔以“股市”和“股票”的關鍵詞就可以幫助程序較為準確的抓取目標頁面。本文對于大眾點評網是用了“成都&&川菜”的關鍵詞,但是由于其他類別的店鋪頁面(如火鍋、小吃快餐、西餐和外地的川菜店鋪等)也具有目標頁面的URL格式,而且在頁面的評論區或其他文本位置也都可能會出現這2個關鍵詞,導致程序無法將這些無關頁面過濾掉,因此造成了準確性的下降。

6 結束語

研究一種高可移植性的通用型自動化垂直爬蟲設計方法具有重要的應用價值。通過分析總結傳統垂直爬蟲的弊端和實現通用化的難點,本文提出一種高效的有監督的廣度優先與網頁帶權搜索策略和數據解析路徑模板自動提取方法。實驗結果證明,該方法的通用性效果較好,可以對不同類型的網站實現快速爬取,爬取數據的效率較高,數據完整性很好,且對于大部分網站也能保證很高的準確性。下一步將在本文研究的基礎上,繼續對搜索策略進行優化,并提升通用型垂直爬蟲自動化程度。