爬蟲系統中標簽刪除功能的設計及優化①

鄧子云

(長沙商貿旅游職業技術學院 經濟貿易學院， 長沙 410116)

在用爬蟲爬取到大型商品網站的大規模網頁數據集后， 要將網頁數據集作進一步篩選以得到目標數據集， 篩選之前要做的一項準備工作就是刪除網頁中多余的標簽. 已有一些文獻提出了標簽刪除功能的算法，并有工程實現， 但尚未見性能分析及改進的討論[1-3].

本文作者所在的研究團隊已經研發了一種爬取大型商品網站網頁數據的爬蟲， 可以爬取獲得海量的網頁數據集. 接下來要編制軟件實現標簽刪除工作. 為讓該功能可以實現快速刪除， 本文在給出標簽刪除的算法及軟件設計思想后， 還將對設計進行優化.

1 標簽刪除算法

網頁中通常有如下標簽可以刪除[4，5]:

(1)頭部標簽. 包括＜head＞、＜title＞、＜meta＞、＜!doctype＞、＜style＞等， 這些與正文內容無關， 其中＜!doctype＞標簽在使用Jsoup的Document對象解析時結點名稱為“#doctype”.

(2)注釋和腳本標簽. 包括＜script＞、＜!-- --＞， 其中注釋標簽在使用Jsoup的Document對象解析時結點名稱為“#comment”.

(3)表單標簽. 包括＜input＞、＜select＞、＜option＞等.

(4)文本標簽. 應去掉內容為空的文本標簽， 在使用Jsoup的Document對象解析時結點名稱為“#text”.

(5)其它標簽. 包括＜object＞、＜param＞、＜img＞、＜br＞等. 這些標簽分別表示控件對象、控件對象參數、圖片、換行等， 不影響網頁正文文本內容.

可采用遞歸算法， 在遍歷網頁樹結構時刪除這些多余的標簽， 偽代碼如算法1所示.

算法1. removeTag(nodeTree)//功能: 刪除網頁結構樹中多余的標簽//參數說明: nodeTree， 要刪除多余結點的網頁結構樹， 遞歸時為子樹返回值: 無//遍歷網頁結構樹For i=1 to nodeTree.topNode.childNodeSize//得到第i棵子樹childNodeTree=nodeTree.getChildNodeTree(i)//聲明要刪除的標簽集合collectionDeleted={"head"，"title"，…，"br"}/*如果當前結點是要刪除的標簽或為內容為空的文本標簽*/If (childNodeTree.topNode.name in collectionDeleted) or(childNodeTree.topNode.name equal"#text" and childNodeTree.topNode.content is empty) Then childNodeTree.delete() //刪除當前子樹Else removeTag(childNodeTree) //遞歸調用i=i+1 End If End For

算法1傳入的參數是網頁結構樹， 在遞歸調用時傳入的是子樹. 算法1實際上是按深度遍歷的方法遍歷網頁結構樹. 現有提出的算法還有按層次遍歷的方法[1-3]， 這種算法需要事先得到樹的深度， 以便逐層訪問， 故算法1的設計相對更為簡便， 2種方法的應用效果和實際性能相當.

算法1采用一個For循環依次訪問當前結點的子樹. 在循環體中， 先聲明一個要刪除的標簽的集合， 再判斷當前子樹的頂點名稱是否在這個集合中， 是則刪除當前子樹. 如果當前子樹是文本結點且文本內容為空， 也應予以刪除. 如果當前結點是不應刪除的結點，則遞歸調用算法1， 傳入當前子樹繼續執行刪除標簽工作. 遞歸調用后再將i值增1.i值為什么不在For循環中直接設置步長為1， 而在判定為不用刪除并遞歸調用后再增1呢？來看如圖1所示的樹結構.

圖1 算法1計算的樹結構示例

向算法1傳入如圖1所示的樹結構時， For循環體第1次執行時， 先得到head標簽， 予以刪除該＜head＞標簽為頂點的子樹(實際上該樹只有＜head＞一個結點).For循環體第2次執行時， ＜html＞標簽的子結點數量由 2 變為 1， 繼續得到＜body＞標簽為頂點的子樹， 則遞歸調用算法 1， 傳入＜body＞標簽為頂點的樹. 在對＜body＞標簽為頂點的子樹執行完removeTag()方法后，再將i值增1. 可見， 在判定為不用刪除時再增1的原因是因為刪除后樹頂點的子結點數量減少了一個.

2 標簽刪除功能的設計、優化及性能分析

下面先給出軟件開發及性能實驗的環境， 再提出軟件設計的思想、性能實驗的情況和優化的策略.

2.1 實驗環境

為簡便起見， 研究團隊采用了自己使用的筆記本計算機作為實驗環境， 在單機上安裝SQL Server 2017 Desktop Edition 作為數據庫， 用 Eclipse Java EE IDE for Web Developers Neon.3 Release (4.6.3)作為開發工具軟件. 計算機硬件及操作系統配置如表1所示.

2.2 設計優化過程

對SQL Server的操作需要有一個緩沖區， 以滿足快速處理網頁的需要. 這個緩沖區數據結構及標簽刪除功能實現的設計如圖2所示. 為取得較好的網頁處理效率， 研究團隊對設計做了2次改進. 為便于考察設計改進后的標簽刪除功能處理網頁的效率， 按圖2(a)取1個緩沖區維系線程1個標簽刪除線程(A1S1D)、1個緩沖區維系線程2個標簽刪除線程(A1S2D)，圖2(b)取1個緩沖區維系線程1個標簽刪除線程(B1S1D)、1個緩沖區維系線程2個標簽刪除線程(B1S2D)， 圖2(C) 取1個緩沖區維系線程1個標簽刪除線程(C1S1D)5種情況進行對比分析， 如圖3(a)和圖3(b)所示.

表1 實驗用計算機配置

圖2 緩沖區數據結構及標簽刪除功能實現的設計

最初的圖2(a)的設計考慮有2個方面的因素:

(1)隊列和緩沖區的存儲. 隊列存放在SQL Server的表中， 待標簽刪除頁面隊列為一個表， 已作標簽刪除頁面隊列為另一個表， 并使用Spring的組件包中的Driver_ManagerDataSource類來封裝連接數據庫的數據源. 這些隊列中的元素采取Key-Value結構， 這里將Key設置為網頁的網址url， 將Value設置為網頁的內容. 緩沖區頁面隊列中的元素均為Page對象， 這個對象有兩個屬性， 即網頁的網址url和網頁的內容pageContent. 假定緩沖區中有k個隊列， 對應著為k個標簽刪除線程提供要刪除的頁面數據， 又假定緩沖區的一個隊列最多有n個元素， 一個url平均長度為lByte， 頁面內容平均長度為mByte， 則緩沖區大小為:

圖3 5種情況的每1000個網頁平均處理時間和累計網頁處理時間

設定k=10，n=10，l=300，m=40 000， 則緩沖區大小為:

故一共需要4 MB左右的內存空間， 這是當前的主流服務器配置可以接受的. 那么， 緩沖區維系列隊怎么知道要將待過慮的頁面數據放入到哪個緩沖區頁面的隊列中呢？這需要查找出緩沖區頁面隊列中的最短隊列， 再push操作. 而標簽刪除線程則是查找緩沖區頁面列隊中的對應隊列的首元素， 再作如算法1所示的標簽刪除算法. 算法運行完成后將已刪除標簽的頁面隊列放入到SQL Server中的已刪除頁面隊列中.

(2)多線程的設計思想. 采用一個緩沖區維系線程，每次從待作標簽刪除頁面隊列中popup操作取出一個頁面， 再作push操作放入到緩沖區頁面的隊列中， 以為緩沖區中各個標簽刪除線程的隊列源源不斷的提供數據. 理論上認為標簽刪除線程數越多， 處理網頁的效率就會越高.

從圖3可以看出， 采用A1S1D比A1S2D的網頁處理效率更高， 每1000個網頁平均處理效率約要快約35%， 20萬個網頁處理效率約高35%. 而且A1S1D的處理效率也不高， 處理20萬個網頁約需要7.99小時. 那是什么原因呢？經過分析， 研究團隊發現， 其一， 數據庫操作占據了緩沖區維系線程和標簽處理線程的大量時間， 因為使用了org.springframework.jdbc.datasource._DriverManagerDataSource連接數據庫， 每次都會新建和關閉一個數據庫連接； 其二， 由于標簽處理線程只對一個SQL Server數據庫表作insert操作， 而對單機的SQL Server的單個表加大Java線程操作的并發數并不能提升效率， 反而由于數據庫的鎖機制會降低效率.

這就需要作出改進， 策略如下:

(1)改為使用org.apache.commons.dbcp._BasicDataSource數據庫連接池， 從而減少數據庫操作和關閉的操作， 節省整體數據庫操作的時間.

(2)標簽處理線程只設一個.

如此改進后， 設計如圖2(b)所示， 再行作測試實驗. 為便于做對比分析， 改用連接池后， 仍按圖2(b)所示的設計采取標簽處理線程1個和標簽處理線程2個2種情況作對比， 如圖3中的B1S1D和B1S2D所示，從圖中可看出， 網頁處理效率加快了， B1S1D比A1S1D每1000個網頁處理效率約提升56%， 20萬個網頁處理效率也提升約56%， 僅需3.48小時； B1S2D處理20萬個網頁需5.42小時， 效率明顯不如B1S1D.

B1S1D還有改進的空間. 通過運用Spring的AOP特性， 研究團隊在數據庫操作的方法前后用Advice記錄下了數據操作的時間， 如圖4所示. 圖4的左邊的圖表示了數據庫操作與非數據庫操作的時間情況， 右邊的圖用百分比占比表示了數據庫操作與非數據庫操作的時間占比. 從圖4的B1S1D的情況來看， 緩沖區維系線程中數據庫操作的時間占比很大， 可見一個一個從數據庫表中查詢出數據是比較耗時的， 使得緩沖區維系線程供應網頁數據不及時， 成為標簽刪除功能的瓶頸. 故對B1S1D改進的策略是使用批處理， 具體方法如下文.

(1)緩沖區維系線程每次從數據庫表中查詢出500條網頁數據， 以100個網頁數據為一個塊向緩沖區中填充隊列.

(2)緩沖區以100個網頁數據為一個數據塊， 設置10個數據塊， 保持一個1000個網頁數據的緩沖區.

(3)標簽刪除線程一次取出100個網頁數據作批處理， 相應的insert操作也采用批處理， 每次向數據庫表中插入100個刪除標簽后的網頁數據.

圖4 B1S1D和C1S1D的處理時間對比

改進后的設計如圖2(c)所示， 再行作測試實驗. 實驗結果如圖3和圖4所示， C1S1D每1000個網頁的平均處理時間只需19.7秒， 處理20萬個網頁只需1.1小時. 后續我們不再討論引擎的問題， 后續的各種過濾方法均采用C1S1D類似的結構設計. C1S1D在Spring容器中的設計思想如圖5所示.

圖5 標簽刪除功能的Sprint AOP和IoC設計思想

綜合上述分析， 課題研究團隊對設計優化的方法是從“并行、連接池、批處理”3個重要方面進行， 即:

(1)采用雙線程設計思想， 使系統可以并行工作；

(2)采用連接池和數據緩沖區， 加快數據處理速度；

(3)采用批處理方式， 一次成批處理方式操作數據庫， 使效率數倍于逐條記錄處理方式.

2.3 改進后設計的Spring實現

為實現如圖2(c)所示的設計， 采用了Spring的AOP 和 IoC 設計思想， 如圖 5 所示， 其中， 圖 5(a)為緩沖區維系線程的設計， 圖5(b)為標簽刪除線程的設計[6].Spring容器支持異步的任務執行器， 緩沖區維系線程和標簽刪除線程之間可互不影響， 并行執行.

從依賴關系來看， 線程Bean依賴于緩沖區操作Bean和隊列操作Bean. 緩沖區操作Bean和隊列操作Bean再分別依賴于緩沖區Bean和隊列Bean. 緩沖區Bean和隊列Bean分別封裝緩沖區和隊列. 這種設計思想就是延用的DAO (Data Access Object， 數據訪問對象)的設計思想. 切面位于每個Bean的方法執行前后， 可根據方法的不同進行不同的Advice增強， 比較常用的是日志記錄、效率分析等.

3 結束語

給出了用遞歸思想設計的標簽刪除算法， 采用Eclipse開發工具用Java語言開發實現了標簽刪除功能. 提出了標簽刪除功能的設計思想， 并作了2次性能優化和設計改進. 由最初的多線程設計思想， 改為最終的雙線程設計思想， 并利用數據庫連接池作網頁數據的批量處理. 最終將性能提升至在單機上標簽刪除功能每1000個網頁的平均處理時間只需19.7秒， 處理20萬個網頁只需1.1小時.