鄧子云

(長沙商貿(mào)旅游職業(yè)技術(shù)學(xué)院 經(jīng)濟(jì)貿(mào)易學(xué)院， 長沙 410116)

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

本文作者所在的研究團(tuán)隊(duì)已經(jīng)研發(fā)了一種爬取大型商品網(wǎng)站網(wǎng)頁數(shù)據(jù)的爬蟲， 可以爬取獲得海量的網(wǎng)頁數(shù)據(jù)集. 接下來要編制軟件實(shí)現(xiàn)標(biāo)簽刪除工作. 為讓該功能可以實(shí)現(xiàn)快速刪除， 本文在給出標(biāo)簽刪除的算法及軟件設(shè)計(jì)思想后， 還將對設(shè)計(jì)進(jìn)行優(yōu)化.

1 標(biāo)簽刪除算法

網(wǎng)頁中通常有如下標(biāo)簽可以刪除[4，5]:

(1)頭部標(biāo)簽. 包括＜head＞、＜title＞、＜meta＞、＜!doctype＞、＜style＞等， 這些與正文內(nèi)容無關(guān)， 其中＜!doctype＞標(biāo)簽在使用Jsoup的Document對象解析時(shí)結(jié)點(diǎn)名稱為“#doctype”.

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

(3)表單標(biāo)簽. 包括＜input＞、＜select＞、＜o(jì)ption＞等.

(4)文本標(biāo)簽. 應(yīng)去掉內(nèi)容為空的文本標(biāo)簽， 在使用Jsoup的Document對象解析時(shí)結(jié)點(diǎn)名稱為“#text”.

(5)其它標(biāo)簽. 包括＜o(jì)bject＞、＜param＞、＜img＞、＜br＞等. 這些標(biāo)簽分別表示控件對象、控件對象參數(shù)、圖片、換行等， 不影響網(wǎng)頁正文文本內(nèi)容.

可采用遞歸算法， 在遍歷網(wǎng)頁樹結(jié)構(gòu)時(shí)刪除這些多余的標(biāo)簽， 偽代碼如算法1所示.

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

算法1傳入的參數(shù)是網(wǎng)頁結(jié)構(gòu)樹， 在遞歸調(diào)用時(shí)傳入的是子樹. 算法1實(shí)際上是按深度遍歷的方法遍歷網(wǎng)頁結(jié)構(gòu)樹. 現(xiàn)有提出的算法還有按層次遍歷的方法[1-3]， 這種算法需要事先得到樹的深度， 以便逐層訪問， 故算法1的設(shè)計(jì)相對更為簡便， 2種方法的應(yīng)用效果和實(shí)際性能相當(dāng).

算法1采用一個(gè)For循環(huán)依次訪問當(dāng)前結(jié)點(diǎn)的子樹. 在循環(huán)體中， 先聲明一個(gè)要刪除的標(biāo)簽的集合， 再判斷當(dāng)前子樹的頂點(diǎn)名稱是否在這個(gè)集合中， 是則刪除當(dāng)前子樹. 如果當(dāng)前子樹是文本結(jié)點(diǎn)且文本內(nèi)容為空， 也應(yīng)予以刪除. 如果當(dāng)前結(jié)點(diǎn)是不應(yīng)刪除的結(jié)點(diǎn)，則遞歸調(diào)用算法1， 傳入當(dāng)前子樹繼續(xù)執(zhí)行刪除標(biāo)簽工作. 遞歸調(diào)用后再將i值增1.i值為什么不在For循環(huán)中直接設(shè)置步長為1， 而在判定為不用刪除并遞歸調(diào)用后再增1呢？來看如圖1所示的樹結(jié)構(gòu).

圖1 算法1計(jì)算的樹結(jié)構(gòu)示例

向算法1傳入如圖1所示的樹結(jié)構(gòu)時(shí)， For循環(huán)體第1次執(zhí)行時(shí)， 先得到head標(biāo)簽， 予以刪除該＜head＞標(biāo)簽為頂點(diǎn)的子樹(實(shí)際上該樹只有＜head＞一個(gè)結(jié)點(diǎn)).For循環(huán)體第2次執(zhí)行時(shí)， ＜html＞標(biāo)簽的子結(jié)點(diǎn)數(shù)量由 2 變?yōu)?1， 繼續(xù)得到＜body＞標(biāo)簽為頂點(diǎn)的子樹， 則遞歸調(diào)用算法 1， 傳入＜body＞標(biāo)簽為頂點(diǎn)的樹. 在對＜body＞標(biāo)簽為頂點(diǎn)的子樹執(zhí)行完removeTag()方法后，再將i值增1. 可見， 在判定為不用刪除時(shí)再增1的原因是因?yàn)閯h除后樹頂點(diǎn)的子結(jié)點(diǎn)數(shù)量減少了一個(gè).

2 標(biāo)簽刪除功能的設(shè)計(jì)、優(yōu)化及性能分析

下面先給出軟件開發(fā)及性能實(shí)驗(yàn)的環(huán)境， 再提出軟件設(shè)計(jì)的思想、性能實(shí)驗(yàn)的情況和優(yōu)化的策略.

2.1 實(shí)驗(yàn)環(huán)境

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

2.2 設(shè)計(jì)優(yōu)化過程

對SQL Server的操作需要有一個(gè)緩沖區(qū)， 以滿足快速處理網(wǎng)頁的需要. 這個(gè)緩沖區(qū)數(shù)據(jù)結(jié)構(gòu)及標(biāo)簽刪除功能實(shí)現(xiàn)的設(shè)計(jì)如圖2所示. 為取得較好的網(wǎng)頁處理效率， 研究團(tuán)隊(duì)對設(shè)計(jì)做了2次改進(jìn). 為便于考察設(shè)計(jì)改進(jìn)后的標(biāo)簽刪除功能處理網(wǎng)頁的效率， 按圖2(a)取1個(gè)緩沖區(qū)維系線程1個(gè)標(biāo)簽刪除線程(A1S1D)、1個(gè)緩沖區(qū)維系線程2個(gè)標(biāo)簽刪除線程(A1S2D)，圖2(b)取1個(gè)緩沖區(qū)維系線程1個(gè)標(biāo)簽刪除線程(B1S1D)、1個(gè)緩沖區(qū)維系線程2個(gè)標(biāo)簽刪除線程(B1S2D)， 圖2(C) 取1個(gè)緩沖區(qū)維系線程1個(gè)標(biāo)簽刪除線程(C1S1D)5種情況進(jìn)行對比分析， 如圖3(a)和圖3(b)所示.

表1 實(shí)驗(yàn)用計(jì)算機(jī)配置

圖2 緩沖區(qū)數(shù)據(jù)結(jié)構(gòu)及標(biāo)簽刪除功能實(shí)現(xiàn)的設(shè)計(jì)

最初的圖2(a)的設(shè)計(jì)考慮有2個(gè)方面的因素:

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

圖3 5種情況的每1000個(gè)網(wǎng)頁平均處理時(shí)間和累計(jì)網(wǎng)頁處理時(shí)間

設(shè)定k=10，n=10，l=300，m=40 000， 則緩沖區(qū)大小為:

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

(2)多線程的設(shè)計(jì)思想. 采用一個(gè)緩沖區(qū)維系線程，每次從待作標(biāo)簽刪除頁面隊(duì)列中popup操作取出一個(gè)頁面， 再作push操作放入到緩沖區(qū)頁面的隊(duì)列中， 以為緩沖區(qū)中各個(gè)標(biāo)簽刪除線程的隊(duì)列源源不斷的提供數(shù)據(jù). 理論上認(rèn)為標(biāo)簽刪除線程數(shù)越多， 處理網(wǎng)頁的效率就會越高.

從圖3可以看出， 采用A1S1D比A1S2D的網(wǎng)頁處理效率更高， 每1000個(gè)網(wǎng)頁平均處理效率約要快約35%， 20萬個(gè)網(wǎng)頁處理效率約高35%. 而且A1S1D的處理效率也不高， 處理20萬個(gè)網(wǎng)頁約需要7.99小時(shí). 那是什么原因呢？經(jīng)過分析， 研究團(tuán)隊(duì)發(fā)現(xiàn)， 其一， 數(shù)據(jù)庫操作占據(jù)了緩沖區(qū)維系線程和標(biāo)簽處理線程的大量時(shí)間， 因?yàn)槭褂昧薿rg.springframework.jdbc.datasource._DriverManagerDataSource連接數(shù)據(jù)庫， 每次都會新建和關(guān)閉一個(gè)數(shù)據(jù)庫連接； 其二， 由于標(biāo)簽處理線程只對一個(gè)SQL Server數(shù)據(jù)庫表作insert操作， 而對單機(jī)的SQL Server的單個(gè)表加大Java線程操作的并發(fā)數(shù)并不能提升效率， 反而由于數(shù)據(jù)庫的鎖機(jī)制會降低效率.

這就需要作出改進(jìn)， 策略如下:

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

(2)標(biāo)簽處理線程只設(shè)一個(gè).

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

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

(1)緩沖區(qū)維系線程每次從數(shù)據(jù)庫表中查詢出500條網(wǎng)頁數(shù)據(jù)， 以100個(gè)網(wǎng)頁數(shù)據(jù)為一個(gè)塊向緩沖區(qū)中填充隊(duì)列.

(2)緩沖區(qū)以100個(gè)網(wǎng)頁數(shù)據(jù)為一個(gè)數(shù)據(jù)塊， 設(shè)置10個(gè)數(shù)據(jù)塊， 保持一個(gè)1000個(gè)網(wǎng)頁數(shù)據(jù)的緩沖區(qū).

(3)標(biāo)簽刪除線程一次取出100個(gè)網(wǎng)頁數(shù)據(jù)作批處理， 相應(yīng)的insert操作也采用批處理， 每次向數(shù)據(jù)庫表中插入100個(gè)刪除標(biāo)簽后的網(wǎng)頁數(shù)據(jù).

圖4 B1S1D和C1S1D的處理時(shí)間對比

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

圖5 標(biāo)簽刪除功能的Sprint AOP和IoC設(shè)計(jì)思想

綜合上述分析， 課題研究團(tuán)隊(duì)對設(shè)計(jì)優(yōu)化的方法是從“并行、連接池、批處理”3個(gè)重要方面進(jìn)行， 即:

(1)采用雙線程設(shè)計(jì)思想， 使系統(tǒng)可以并行工作；

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

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

2.3 改進(jìn)后設(shè)計(jì)的Spring實(shí)現(xiàn)

為實(shí)現(xiàn)如圖2(c)所示的設(shè)計(jì)， 采用了Spring的AOP 和 IoC 設(shè)計(jì)思想， 如圖 5 所示， 其中， 圖 5(a)為緩沖區(qū)維系線程的設(shè)計(jì)， 圖5(b)為標(biāo)簽刪除線程的設(shè)計(jì)[6].Spring容器支持異步的任務(wù)執(zhí)行器， 緩沖區(qū)維系線程和標(biāo)簽刪除線程之間可互不影響， 并行執(zhí)行.

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

3 結(jié)束語

給出了用遞歸思想設(shè)計(jì)的標(biāo)簽刪除算法， 采用Eclipse開發(fā)工具用Java語言開發(fā)實(shí)現(xiàn)了標(biāo)簽刪除功能. 提出了標(biāo)簽刪除功能的設(shè)計(jì)思想， 并作了2次性能優(yōu)化和設(shè)計(jì)改進(jìn). 由最初的多線程設(shè)計(jì)思想， 改為最終的雙線程設(shè)計(jì)思想， 并利用數(shù)據(jù)庫連接池作網(wǎng)頁數(shù)據(jù)的批量處理. 最終將性能提升至在單機(jī)上標(biāo)簽刪除功能每1000個(gè)網(wǎng)頁的平均處理時(shí)間只需19.7秒， 處理20萬個(gè)網(wǎng)頁只需1.1小時(shí).