周孝錁 郭克華，2

1(中南大學(xué)信息科學(xué)與工程學(xué)院 湖南 長沙 410000)

基于網(wǎng)絡(luò)爬蟲和改進(jìn)的LCS算法的網(wǎng)站更新監(jiān)測

周孝錁1郭克華1，2

1(中南大學(xué)信息科學(xué)與工程學(xué)院 湖南 長沙 410000)

2(高維信息智能感知與系統(tǒng)教育部重點實驗室 江蘇 南京 210094)

互聯(lián)網(wǎng)時代，信息爆炸式增長，用戶需要方便及時地獲取自己所需的信息。傳統(tǒng)的搜索引擎和以RSS為代表的訂閱具有一些缺陷，難以滿足用戶高質(zhì)量需求。在此基礎(chǔ)上，利用網(wǎng)絡(luò)爬蟲和文本對比，提出一種新型網(wǎng)站更新監(jiān)測與訂閱的通用方法。該方法將先后抓取的網(wǎng)頁內(nèi)容分析處理后，進(jìn)行文本對比，檢測更新內(nèi)容，將結(jié)果以結(jié)構(gòu)化形式返回給用戶查看。實驗表明，該方法解決了RSS訂閱受訂閱源限制的缺點，實現(xiàn)了用戶添加任意網(wǎng)站，在高校、企業(yè)、新聞、電影、博客、論壇等網(wǎng)站的監(jiān)測方面具有較好的效果。

網(wǎng)絡(luò)爬蟲 網(wǎng)頁去噪 網(wǎng)站訂閱 文本對比 更新監(jiān)測

0 引 言

隨著互聯(lián)網(wǎng)的迅猛發(fā)展，社會進(jìn)入全面信息時代，網(wǎng)站數(shù)據(jù)不斷增多，截至2011年底，中國網(wǎng)民規(guī)模達(dá)到4.85億，位居世界首位，網(wǎng)頁數(shù)量達(dá)到600億以上[1]。這些網(wǎng)頁都處在不斷的變化更新中，近乎40%的網(wǎng)頁一周內(nèi)會更新，而以.com為域名的網(wǎng)頁則有23%每天都在變化[2]。因此，從浩瀚信息海洋中獲取最需、最新內(nèi)容，成為研究熱點。搜索引擎和RSS訂閱的發(fā)明，在一定程度上解決了獲取信息的難題，但二者的弊端也隨著用戶需求的擴(kuò)大而愈加凸顯：搜索引擎需要手動輸入，準(zhǔn)確度不夠；RSS訂閱則由于訂閱源的限制，而影響了其訂閱范圍[3]。因此，面向任意網(wǎng)站的通用訂閱方法及相關(guān)技術(shù)應(yīng)運而生。

RSS訂閱在本世紀(jì)初被廣泛關(guān)注，不僅在新聞、博客、論壇等網(wǎng)站得到實施，也有在化學(xué)[4]、開源項目[5]、管理系統(tǒng)等領(lǐng)域得到應(yīng)用，產(chǎn)生了多種試圖給任意網(wǎng)站產(chǎn)生RSS Feed的系統(tǒng)和網(wǎng)站。如日本的Nanno等[6]開發(fā)的系統(tǒng)，在分析HTML文檔特征的基礎(chǔ)上實現(xiàn)為含有時間序列項的網(wǎng)站自動生成RSS Feed。不過，該系統(tǒng)所分析的網(wǎng)站必須要有日期描述，由時間序列項構(gòu)成。此外，業(yè)界其他網(wǎng)站提供了生成RSS Feed的功能，如page2rss.com/、feed43.com、feedity.com、feedyes.com、www.ponyfish.com 等，但它們都有各自的局限和缺點：page2rsss解析的目標(biāo)網(wǎng)站內(nèi)容不能太多，有些網(wǎng)站難以得到更新內(nèi)容，即使生成了RSS 種子，格式也不適用于大部分RSS 閱讀器；feed43僅能滿足大部分一般布局的網(wǎng)站；feedity和feedyes收費；ponyfish已經(jīng)關(guān)閉服務(wù)。可實現(xiàn)大規(guī)模網(wǎng)站訂閱的Google Reader，也隨著2013年7月1日Google Reader的關(guān)閉而不復(fù)存在。

為解決以上問題，人們從爬蟲入手，試圖利用網(wǎng)站更新檢測的技術(shù)，獲取網(wǎng)站最新內(nèi)容，并推送給相關(guān)用戶(訂閱用戶)。文獻(xiàn)[7]試圖優(yōu)化RSS閱讀器的信息重復(fù)和面向用戶個性化不足等缺陷；文獻(xiàn)[8]利用網(wǎng)絡(luò)爬蟲和TF-IDF算法對抓取的網(wǎng)頁分類，得到高校網(wǎng)站中某一類別的信息，再以RSS訂閱的形式推送給用戶，它的局限性在于只是針對某個類別的信息獲取，未能推廣到各類網(wǎng)站的全面內(nèi)容更新監(jiān)測及推送。市場上的許多RSS訂閱的替代品，如國內(nèi)的鮮果、抓蝦、今日頭條以及國外的ZAKER等。這些產(chǎn)品利用網(wǎng)絡(luò)爬蟲抓取目標(biāo)網(wǎng)頁的內(nèi)容，如果整合起來，供用戶訂閱，就比較方便，但是這些產(chǎn)品的一個共同缺點，即用戶無法自主添加訂閱網(wǎng)站。

本文為解決以上問題，找到一個通用的網(wǎng)站訂閱方案，提出了一個基于網(wǎng)絡(luò)爬蟲、網(wǎng)頁去噪和文本對比，用戶可自主添加訂閱的網(wǎng)站更新監(jiān)測和訂閱系統(tǒng)。主要采取去除所有網(wǎng)頁標(biāo)簽和鏈接，提取所有文本值作為字符串對比輸入的方案。該方法解決了RSS訂閱受訂閱源限制的缺點，實現(xiàn)了用戶任意添加網(wǎng)站，在高校、企業(yè)、新聞、電影、博客、論壇等網(wǎng)站的監(jiān)測方面具有較好的效果。

1 系統(tǒng)框架與關(guān)鍵技術(shù)

1.1 系統(tǒng)框架

本系統(tǒng)設(shè)計有3個模塊，分別為訂閱模塊、更新模塊和查看模塊。訂閱模塊是處理用戶添加的訂閱網(wǎng)站，流程圖如圖1所示。爬蟲訪問用戶添加的網(wǎng)址，獲取網(wǎng)頁內(nèi)容，存入數(shù)據(jù)庫；同時根據(jù)需要與否從中提取二級超鏈接(即頁面上的超鏈接，這由用戶選擇的更新深度決定)，若需要，再訪問二級超鏈接獲取網(wǎng)頁內(nèi)容，存入數(shù)據(jù)庫；同樣根據(jù)需要與否提取其中的三級超鏈接，訪問三級超鏈接獲取網(wǎng)頁內(nèi)容，只需存入數(shù)據(jù)庫，不用再提取超鏈接。因為系統(tǒng)設(shè)置的可選更新深度最大是3，便于訂閱目錄型網(wǎng)站[9]。

圖1 訂閱模塊流程圖

更新模塊是整個系統(tǒng)的核心，流程圖如圖2所示。該模塊獨立于系統(tǒng)，后臺運行，不受用戶干預(yù)。為有效地利用資源，及時獲得更新，采用一種新型增量式更新算法用于設(shè)置更新時間。通過爬蟲獲取網(wǎng)頁內(nèi)容，經(jīng)網(wǎng)頁去噪后提取每個超鏈接的文本值，構(gòu)成新舊字符串?dāng)?shù)組進(jìn)行對比，得到新增或修改過的超鏈接，即網(wǎng)站的Item(通知、新聞、講座、視頻、音樂、帖子等，統(tǒng)稱Item)。經(jīng)過文本對比，若發(fā)現(xiàn)兩次爬取的頁面內(nèi)容有改變，則提取變化的Item，存入數(shù)據(jù)庫，并更新數(shù)據(jù)庫中存儲的頁面內(nèi)容，供下次對比使用；若無改變，只需更新數(shù)據(jù)庫中存儲的頁面內(nèi)容。由于文本值以標(biāo)題為主，重復(fù)概率很低，文本值具備唯一性和不變性，所以選擇Item的文本值作為對比。

圖2 更新模塊流程圖

查看模塊是從數(shù)據(jù)庫中提取所需數(shù)據(jù)，結(jié)構(gòu)化顯示在網(wǎng)頁上，便于用戶查看，是系統(tǒng)的主要界面。

由于網(wǎng)頁內(nèi)容的雜亂性、動態(tài)性、頁面結(jié)構(gòu)差異性，經(jīng)過文本對比，得到最新Item存入數(shù)據(jù)庫后，其實并非都是網(wǎng)站最新的、用戶需要查看的Item。本文使用選擇性提取數(shù)據(jù)，提高更新準(zhǔn)確性。從數(shù)據(jù)庫表中讀取本次更新獲得的記錄時，跟上次更新獲得的記錄進(jìn)行對比，過濾那些在上次更新中也出現(xiàn)過的重復(fù)記錄。

通過選擇性提取數(shù)據(jù)，把精簡、準(zhǔn)確的最新Item結(jié)構(gòu)化顯示在頁面上，供用戶查看。一般而言，Item包含標(biāo)題、鏈接、發(fā)布日期(若沒有，則用更新日期替代)，用戶點擊標(biāo)題即可鏈接到Item所在原網(wǎng)站的詳細(xì)頁面，類似RSS訂閱器。

1.2 爬蟲訪問被拒問題

由于系統(tǒng)需要頻繁地訪問眾多網(wǎng)址，難免會出現(xiàn)各種網(wǎng)絡(luò)錯誤，比如不斷重新連接服務(wù)器、服務(wù)器拒絕訪問、訪問頻率過高連接崩潰等。對此問題，本系統(tǒng)首先完善訪問機(jī)制，設(shè)置合適最大鏈接數(shù)、重連次數(shù)等參數(shù)，確保一些低級問題不會發(fā)生；其次，合理訪問網(wǎng)址，不暴力地持續(xù)訪問，避免服務(wù)器采取阻止爬蟲的各類措施；可以通過設(shè)置合理的更新周期、多線程的機(jī)制和分布式爬蟲加以實現(xiàn)；在本機(jī)上做出的系統(tǒng)demo，運用了增量式更新和多線程爬取，實現(xiàn)了前兩點。

為節(jié)省系統(tǒng)的資源，提高爬蟲效率，本文采取增量式爬取算法來設(shè)置更新周期。增量式爬取算法可以簡單地分為三種[8]：(1) 定期地從URL列表中，按先后順序進(jìn)行訪問；(2) 把網(wǎng)頁根據(jù)其更新速度簡單分為更新快的一類和更新慢的一類，分別設(shè)置較短和較長的更新周期；(3) 對URL列表中每個URL所指頁面的更新速度進(jìn)行預(yù)測，根據(jù)這個預(yù)測時間來爬取網(wǎng)頁，盡可能滿足各種網(wǎng)頁的更新頻率，最大效率地利用系統(tǒng)資源。本系統(tǒng)采用第三種增量式爬取算法，其中的更新預(yù)測算法采用文獻(xiàn)[8]中改進(jìn)的算法。該算法簡單描述為：用一個參數(shù)A記錄“上次監(jiān)測到更新所用時間”，另一個參數(shù)C記錄“上次更新至今有多久”，從隊列中取出“預(yù)測更新時間”已到的網(wǎng)頁進(jìn)行訪問，若有更新，說明實際更新時間小于或等于A，根據(jù)實踐經(jīng)驗，設(shè)置為A的80%；若無更新，說明預(yù)測的更新時間太小，將預(yù)測更新時間變?yōu)槠浔旧砑由螦的一半。算法流程如圖3所示。

圖3 增量式更新，預(yù)測更新時間算法流程圖

其中A表示更新參數(shù)，記錄上一次共用多久監(jiān)測到更新；B表示預(yù)計下次過多久更新，即系統(tǒng)需要的預(yù)測更新時間；C表示累計未更新時間，即上次更新后到現(xiàn)在為止這段時間，如果更新了就清零，初始值賦為0。

1.3 過濾不合適鏈接

為了多層次監(jiān)測網(wǎng)站的更新，需要提取某些網(wǎng)站(由用戶自己選擇)的首頁及二級頁面上的超鏈接，由于有些頁面結(jié)構(gòu)雜亂、鏈接眾多，有許多非法、無用的不適用鏈接需要過濾掉，如友情鏈接、相關(guān)導(dǎo)航等。首先，友情和導(dǎo)航鏈接基本是絕對鏈接，而頁面上正常的用戶需要的鏈接是相對鏈接，對其進(jìn)行初步過濾；其次，對于一個鏈接，可嘗試訪問，并提取它所指頁面的超鏈接個數(shù)，如果超鏈接個數(shù)較多，超過某閾值，則判斷為不合用鏈接而過濾掉，形成二次過濾。另外，一個較大網(wǎng)站難免會有一些相同Item和一些相互指向的鏈接，對此，把所有鏈接存入HashMap里面，過濾掉重復(fù)值。

1.4 文本對比算法

本系統(tǒng)采用改進(jìn)的LCS(Longest Common Sequence)算法[10]進(jìn)行文本對比，LCS指兩個字符串的最長公共子序列(不要求連續(xù)出現(xiàn)，只要出現(xiàn)順序一致)。計算LCS(A,B)的方法很多，運用動態(tài)規(guī)劃思想的Needleman-Wunsch算法[11]是較早較基礎(chǔ)的，它最早在1970年由Needleman和Wunsch二人提出，用于生物信息學(xué)領(lǐng)域的蛋白質(zhì)序列對比，后來發(fā)展為全局最優(yōu)匹配(Optimal Global Alignment)的常用手段。

算法1 假設(shè)待比較的字符串A和B，長度分別是m、n，Needleman-Wunsch算法求兩個字符串的LCS分為四步：

Step1 初始化矩陣。構(gòu)建一個(m+1)×(n+1)的空矩陣F。

Step2 選擇計分系統(tǒng)。字符串匹配時每對字符存在三種情況：

(1) 匹配(Math)：兩個字符相同；

(2) 不匹配(Mismatch)：兩個字符不同；

(3) 缺口(Gap)：一個字符跟缺口相對。

計分系統(tǒng)就是對上述三種情形賦值，賦值規(guī)則不同，計分系統(tǒng)就不同。Needleman和Wunsch采取最簡單的方式，設(shè)定Math計1分，Mismatch計-1分，Gap計-1分。

Step3 填充矩陣。根據(jù)計分系統(tǒng)填充矩陣。主要的規(guī)則由式(1)決定：

F(i,j)= Max(F(i-1,j-1)+S(Ai,Bj),F(i,j-1)+d,

F(i-1,j)+d) (1≤i≤m,1≤j≤n)

(1)

Step4 回溯路徑。根據(jù)Step3中的計算，用箭頭表示F(i,j)(1≤i≤m,1≤j≤n)的來源，即上單元、左單元和左上角單元。然后根據(jù)箭頭從矩陣的最右下角一個單元開始，回溯得到最長公共子序列的路徑。

實際上，每個單元格的得分表示該單元格的列所代表的字符變?yōu)樵搯卧竦男兴淼淖址碾y易程度，換言之，分?jǐn)?shù)代表字符之間的編輯距離。算法1采用Math=1，Mismatch=-1，Gap=-1的計分系統(tǒng)，得分越高，編輯距離越小，所以式(1)中F(i,j)選取三個方向的最大值。于是計分完成之后，根據(jù)得分來源從右下角單元格開始回溯得到路徑，是得分最高的路徑，也是編輯距離最小的路徑，即我們需要的最長公共子序列。這是算法1的核心思想。

由于矩陣是(m+1)×(n+1)，計算每個單元的值在常數(shù)時間內(nèi)完成，整個過程中需要存儲每個單元格的值，算法1的時間和空間復(fù)雜度都為O(mn)。

然而，該時間和空間復(fù)雜度跟被比較的兩個字符串長度乘積成正比，當(dāng)比較的字符串長度很大時，耗費的時間和空間巨大。不少學(xué)者對LCS算法進(jìn)行了改進(jìn)。已經(jīng)證明，LCS問題算法的時間復(fù)雜度不可能小于O(mlogn)[12],目前幾種比較有效的是Hirschberg[13]提出的時間復(fù)雜度為O(tn),Nakatsu[10]提出的時間復(fù)雜度為O(n(m-t))，以及李欣等人改進(jìn)的快速算法[14]，時間復(fù)雜度為O(t(m-t))，其中m、n、t分別為字符串A的長度、字符串B的長度，二者的LCS長度。

本文采用的算法：Nakatsu提出的時間復(fù)雜度為O(n(m-t))，這里稱之為算法2。

算法2Nakatsu提出的快速LCS算法，基于下面幾個基本定理[14]：

字符串A=A[1]A[2]…A[m]和字符串B=B[1]B[2]…B[n]，A(1:i)表示A的連續(xù)子序列A[1]A[2]…A[i]，同樣B(1:j)表示B的連續(xù)子序列B[1]B[2]…B[j]。Li(k)表示所有與字符串A(1：i)有長度為k的LCS的字符串B(1：j)中j的最小值。公式化表示就是Li(k)=Minj(LCS(A(1:i),B(1:j))=k)。

定理1 ?i∈[1,m]，有Li(1)

定理2 ?i∈[1,m-1],(t∈[1,m])，有Li+1(k)

定理3 ?i∈[1,m-1],(t∈[1,m-1])，有Li(k)

以上三個定理都不考慮Li(k)無定義的情況。

定理4Li+1(k)如果存在，那么它的取值必為：

Li+1(k)=Min(j,Li(k))

這里j是滿足以下條件的最小整數(shù)：A[i+1]=B[j]且j>Li(k-1)。

以上定理的證明請參閱文獻(xiàn)[10，13]。定理4遞推得到Li(k)。利用此遞推關(guān)系構(gòu)建矩陣如圖4所示。

圖4 求解LCS的矩陣L(p,m)

以上矩陣中的元素L(k,i)=Li(k)，這里(1

設(shè)t=Maxk(L(k,m)≠null)，容易證明L矩陣中L(t,m)所在對角線L(1,m-t+1)L(2,m-t+2)…L(t-1,m-1)L(t,m)所對應(yīng)的子序列B[L(1，m-t+l)]B[L(2，m-t+2)]…B[L(t，m)]即為A和B的LCS(也可能存在特殊情況，對角線所對應(yīng)的子字符串并非完全是LCS，后文會討論)，t為該LCS的長度。于是，LCS問題的求解就轉(zhuǎn)化為對Lm(k)矩陣的求解。

舉例說明：給定字符串A和B，A=bcdabab，B=cbacbaaba，(m=|A|=7，n=|B|=9)，根據(jù)定理4給的推理公式，L矩陣如圖5所示。

圖5 Nakatsu的快速LCS算法舉例

如圖5所示，A和B的LCS為B[1][3][5][6][8]=cabab，LCS的長度t=5。

矩陣第一行元素L(1,i)可用L(1,i) =Minj([A]=B[j])得到，其余行元素用定理4遞推而出。然而實際上并不需要這么做，無需計算矩陣中每個元素的值，只需按對角線順序計算L矩陣。先求第一條對角線上的元素L(1,1)L(2,2)…，直至L(i,i)=null,i≤m為止；再求第二條對角線L(1,2)L(2,3)…L(i,i+1)=null,i

算法2的時間復(fù)雜度曲線是一條隨t增大而減小的直線，如圖6所示?？梢钥闯?，當(dāng)t接近m時，它的時間復(fù)雜度非常低。算法2適合比較兩個文本文件，能夠把一行文本作為一個比較單位，從而大大加快計算速度，提升效率。本文正好需要比較兩段長文本，二者相異部分很小，LCS長度接近被比較的字符串長度，非常適合采用算法2。

圖6 算法2的性能

1.5 文本對比算法改進(jìn)

本文在利用算法2的基礎(chǔ)上，進(jìn)行如下改進(jìn)：

算法2的目的在于找出一個LCS(不是所有)，降低計算LCS的時間與空間復(fù)雜度，而本文需要找出所有的LCS，排除不符合的LCS，提取變化的內(nèi)容，保證更新的準(zhǔn)確性。

在圖5的例子中除了B[1][3][5][6][8]=cabab這個明顯的LCS外，還存在其他LCS，如B[2][4][6][8][9]=bcaba等。根據(jù)算法2：計算從第一條對角線開始，直到對角線L(1,s)L(2,s+1)…L(u,m)，且L(u,m)≠null為止。這時L(1,s)所在的對角線是最明顯直接的一個LCS；在計算的過程中，運用了定理4：Li+1(k)=Min(j,Li(k))，這里j是滿足以下條件的最小整數(shù)：A[i+1]=B[j]且j>Li(k-1)，如果不存在這樣的j滿足A[i+1]=B[j]且j>Li(k-1)，那么Li+1(k)=Li(k)，將這樣的Li+1(k)標(biāo)記圓圈以示區(qū)別。實際上，該Li+1(k)對應(yīng)的B[b](b=Li+1(k))是不可能成為LCS一部分，因為B中不存在A[i+l]字符，Li+1(k)的值是由Li(k)替代的，它是個虛假的匹配點，可稱之為虛點。如圖7所示，路徑Ⅰ、Ⅱ、Ⅲ、Ⅲ所在的單元構(gòu)成四個真實的LCS。

圖7 存在多個LCS

因此圖5中箭頭所在的對角線只能表明LCS的長度為5，而真的LCS是箭頭Ⅰ所對應(yīng)的子字符串B[1][3][5][6][8]=cabab，這就是前文提到的特殊情況。箭頭Ⅱ、Ⅲ、Ⅲ也都是LCS，分別對應(yīng)B[2][3][5][6][8]=babab、B[2][4][5][6][8]=bcbab和B[2][4][6][8][9]=bcaba，四個LCS的匹配情形如圖8所示。

圖8 四種匹配情形

總結(jié)可以發(fā)現(xiàn)，所有的LCS是以最后一條對角線(稱之為基準(zhǔn)線)為基礎(chǔ)擴(kuò)展而來，它只可能位于基準(zhǔn)線的左下方，并且遵循如下規(guī)則：

(1) 對于L(1,s)(s≤m-t+1)所在的每條對角線，若所包含的不為null的元素個數(shù)等于LCS長度t，轉(zhuǎn)(2)；

(2) 對于對角線上元素L(k,i)(k>1,i>1)，若L(k-1,i-1)不為null和虛點，且L(k-1,i-1)

利用上述規(guī)則很容易得到所有的LCS，但不同的LCS對應(yīng)著明顯不同的匹配情形，這對于網(wǎng)站更新系統(tǒng)而言，意味著變化的Item不同。而一個網(wǎng)站實際的更新變化只有一種，所以只有一個匹配情形符合網(wǎng)站的真實更新情況，需要排除其余的匹配。

利用算法，獲得兩個字符串的LCS后，根據(jù)匹配情形即可得知差異部分，對應(yīng)本文網(wǎng)站更新系統(tǒng)的字符串?dāng)?shù)組匹配，就是變化的字符串。比如圖8中，匹配IV的B字符串的B[1]=c、B[3]=a是插入部分，B[5]=b就是修改部分，A[7]=b是被刪除的。由于網(wǎng)站新聞標(biāo)題具有獨特性和功能性，標(biāo)題相同而內(nèi)容不同的情況是極少的；換言之，經(jīng)過文本對比匹配之后，得到的插入部分，在被比較網(wǎng)頁(稱之為舊網(wǎng)頁)中是不存在的(跟字符串匹配不同：插入的字符也可能存在被匹配字符串中)。所以，本文采用字符串?dāng)?shù)組對比，當(dāng)遇到多個LCS時，只需驗證每種匹配情形下插入部分的字符串是否存在被比較的字符串?dāng)?shù)組中，即可判斷該匹配情形是否符合真實情況；若存在，則不是真實情況，排除。

本文利用網(wǎng)絡(luò)爬蟲和文本對比實現(xiàn)網(wǎng)站更新監(jiān)測與訂閱。首先將爬蟲獲取的新舊HTML內(nèi)容利用MD5算法判別是否不同；其次，若有不同，將新舊HTML內(nèi)容進(jìn)行網(wǎng)頁去噪，再進(jìn)行文本對比。采用Nakatsu等人的LCS算法[10]進(jìn)行文本對比，并考慮多個LCS存在的情況，進(jìn)行了改進(jìn)。

網(wǎng)頁去噪的含義廣泛，主要指去除與應(yīng)用目的不相符的干擾因素，毛先領(lǐng)等人[15]對眾多的去噪方法進(jìn)行歸納分類，分為單模型網(wǎng)頁去噪和多模型網(wǎng)頁去噪，重點有Shingle方法[16]，Cai等人的VIPS算法[17-20]。本系統(tǒng)采用的網(wǎng)頁去噪方法簡單而實用，提取每個超鏈接的文本值，構(gòu)成新舊字符串?dāng)?shù)組進(jìn)行對比，滿足算法要求的數(shù)據(jù)輸入格式。經(jīng)過MD5判別和網(wǎng)頁去噪，再進(jìn)行文本對比，降低了對比誤差出現(xiàn)的概率，提高了更新檢測的準(zhǔn)確性。

2 實驗結(jié)果與分析

2.1 實驗設(shè)置

為驗證本文所提方法的性能。在聯(lián)想個人PC機(jī)上進(jìn)行實驗，配置：CPU:Intel(R) Pentium(R)@2.80 GHz，內(nèi)存:4.0 GB，操作系統(tǒng):Win 8.1專業(yè)版，32位。

實驗以7個不同類型、規(guī)模、結(jié)構(gòu)的網(wǎng)站自然情況下的更新作為測試，采用增量式更新和LCS算法獲取更新，統(tǒng)計其查準(zhǔn)率和查全率。由于大型網(wǎng)站如鳳凰網(wǎng)、天涯論壇，一天內(nèi)更新的內(nèi)容多而散亂，難以統(tǒng)計某段時間內(nèi)網(wǎng)站更新的具體新聞數(shù)目，不便計算查全率，只能計算出查準(zhǔn)率。測試網(wǎng)站的名稱、URL、編號如表1所示，與表2中編號相對應(yīng)。

表1 測試網(wǎng)站編號表

表2 采用改進(jìn)的LCS算法統(tǒng)計網(wǎng)站更新數(shù)據(jù)表

續(xù)表2

2.2 實驗結(jié)果

采用本文改進(jìn)的LCS算法，分別統(tǒng)計7個網(wǎng)站每次更新的查準(zhǔn)率、查全率以及5次試驗的平均查準(zhǔn)率、查全率，如表2所示?？梢缘弥?，1、2號網(wǎng)站，是高校內(nèi)部網(wǎng)站，它們的查準(zhǔn)率和查全率非常高接近100%，因為高校內(nèi)部網(wǎng)站結(jié)構(gòu)簡單、更新數(shù)量較少，容易全部捕獲到。不過，由于更新數(shù)量少，若有1～2條更新沒有獲取，對查準(zhǔn)率、查全率影響較大，2號網(wǎng)站正是因此在第4次測試中查準(zhǔn)率和查全率較低。3-7號網(wǎng)站，分別是鳳凰網(wǎng)、天涯論壇、CSDN博客、中國建設(shè)銀行、電影天堂，其中6號中國建設(shè)銀行，監(jiān)測了3層頁面，其表現(xiàn)跟1、2號網(wǎng)站類似，準(zhǔn)確率高但易被少量未捕獲的更新內(nèi)容影響；3號鳳凰網(wǎng)，其結(jié)構(gòu)嚴(yán)謹(jǐn)、內(nèi)容單一有規(guī)律，每次查準(zhǔn)率都在97%以上；其余的3個網(wǎng)站，分別是論壇、博客、電影網(wǎng)站，類型不同，共同點在于網(wǎng)頁結(jié)構(gòu)復(fù)雜、內(nèi)容繁多雜亂、變化頻繁而不規(guī)律、有防爬蟲設(shè)計，故查準(zhǔn)率相對偏低，3個網(wǎng)站的平均查準(zhǔn)率是85.9%，比較穩(wěn)定，受未捕獲的少量更新內(nèi)容影響較??；查全率雖無法統(tǒng)計，但從局部范圍內(nèi)的統(tǒng)計發(fā)現(xiàn)，查全率不低于查準(zhǔn)率，使得更新內(nèi)容遺漏很少，保證了更新的覆蓋范圍。

另外，對同樣的上述7個網(wǎng)站，分別采取改進(jìn)和原始的Nakatsu的LCS算法，進(jìn)行3次更新監(jiān)測，統(tǒng)計其平均查準(zhǔn)率。具體數(shù)據(jù)如表3所示，對應(yīng)的對比如圖9所示。

表3 網(wǎng)站更新對比統(tǒng)計表

續(xù)表3

圖9 網(wǎng)站更新對比圖

通過對比可以發(fā)現(xiàn)，改進(jìn)后的LCS算法用于網(wǎng)站更新監(jiān)測，雖然個別網(wǎng)站的查準(zhǔn)率并未提高，但總體上有更高的查準(zhǔn)率。因為網(wǎng)站上的Item重復(fù)較少，采用LCS算法獲取最長公共子序列時不會經(jīng)常得到多個最長公共子序列，所以改進(jìn)后的一些網(wǎng)站，其查準(zhǔn)率是相同的。但對于4號“天涯論壇”這種大規(guī)模大數(shù)據(jù)網(wǎng)站而言，有許多帖子由于評論內(nèi)容的增加而導(dǎo)致其在頁面上的位置變化，但I(xiàn)tem標(biāo)題其實未變。這導(dǎo)致了后期更新時LCS算法會得到多個最長公共子序列，需要排除。于是本文改進(jìn)的LCS算法就取得了效果，提高了查準(zhǔn)率。查準(zhǔn)率對網(wǎng)站更新而言，非常重要，影響到用戶查看信息的準(zhǔn)確性、全面性，避免遺漏重要通知、信息。

3 結(jié) 語

本文提出一種基于網(wǎng)絡(luò)爬蟲和改進(jìn)的文本對比的網(wǎng)站更新監(jiān)測新方案，實現(xiàn)了幾乎任意網(wǎng)站的更新監(jiān)測與訂閱。實驗結(jié)果表明，對于結(jié)構(gòu)簡單、內(nèi)容規(guī)律的高校、新聞等網(wǎng)站，該方法表現(xiàn)優(yōu)秀；對于結(jié)構(gòu)復(fù)雜、內(nèi)容繁雜、變化頻繁無規(guī)律的論壇、博客、視頻等網(wǎng)站，該方法表現(xiàn)稍有欠缺?？偟膩碚f，所提方法對大規(guī)模網(wǎng)站的更新監(jiān)測，具有一定可行性，為網(wǎng)站更新監(jiān)測領(lǐng)域提供了一個新的方案。本文提出的改進(jìn)LCS算法，一定程度上提高了網(wǎng)站更新的查準(zhǔn)率，保證了網(wǎng)站更新的準(zhǔn)確性、全面性，提高了用戶的使用體驗和效率。但本實驗的測試網(wǎng)站數(shù)量較少、實驗環(huán)境和配置簡單、未采取分布式爬蟲，對實驗結(jié)果有一定的影響，這將是進(jìn)一步的研究方向。

[1] 曹建勛, 劉奕群, 岑榮偉, 等. 基于用戶行為的色情網(wǎng)站識別[J]. 計算機(jī)研究與發(fā)展, 2013, 50(2): 430-436.

[2] Fetterly D, Manasse M, Najork M, et al. A large-scale study of the evolution of Web pages[J]. Software-Practice and Experience, 2004, 34(2): 213-237.

[3] Ma D. Use of RSS feeds to push online content to users[J]. Decision Support Systems, 2012, 54(1):740-749.

[4] Vawter E. Rss explosion in chemistry and science[J]. Searcher, 2006, 14(4): 33-36.

[5] Nagy P, Daly M, Warnock M, et al. Using RSS feeds to track open source radiology informatics projects[C]//Medical Imaging. The International Society for Optics and Photonics, 2005: 282-285.

[6] Nanno T, Okumura M. HTML2RSS: automatic generation of RSS feed based on structure analysis of HTML document[C]//Proceedings of the 15th International Conference on World Wide Web. ACM, 2006: 1075-1076.

[7] 荊明明. 基于Android的個性化RSS訂閱系統(tǒng)的設(shè)計與實現(xiàn)[D]. 哈爾濱：哈爾濱工業(yè)大學(xué), 2011.

[8] 張睿涵. 基于RSS的聚焦網(wǎng)絡(luò)爬蟲在高校網(wǎng)站群中的研究[D]. 南昌：南昌大學(xué), 2012.

[9] 王大偉, 張巖, 曾皓, 等. 一個預(yù)測網(wǎng)頁變化的增量式更新模型[J]. 微計算機(jī)信息, 2009(6): 153-154,130.

[10] Nakatsu N, Kambayashi Y, Yajima S. A longest common subsequence algorithm suitable for similar text strings[J]. Acta Informatica, 1982, 18(2): 171-179.

[11] Needleman S B, Wunsch C D. A general method applicable to the search for similarities in the amino acid sequences of two proteins[J]. Journal of Molecular Biology, 1970, 48: 444-453.

[12] Ullman J D, Aho A V, Hirschberg D S. Bounds on the complexity of the longest common subsequence problem[J]. Journal of the ACM (JACM), 1976, 23(1): 1-12.

[13] Hirschberg D S. Algorithms for the longest common subsequence problem[J]. Journal of the ACM (JACM), 1977, 24(4): 664-675.

[14] 李欣, 舒風(fēng)笛. 最長公共子序列問題的改進(jìn)快速算法[J]. 計算機(jī)應(yīng)用研究, 2000, 17(2): 28-30.

[15] 毛先領(lǐng), 何靖, 閆宏飛, 等. 網(wǎng)頁去噪: 研究綜述[J]. 計算機(jī)研究與發(fā)展, 2010, 47(12): 2025-2036.

[16] Gibson D, Punera K, Tomkins A. The volume revolution of Web page templates[C]//Proceedings of the 14th International Conference on World Wide Web. New York: ACM, 2005: 830-839.

[17] Cai D, Yu S, Wen J R, et al. Extracting content structure for web pages based on visual representation[C]//Proceedings of the 5th Asia-Pacific Web Conference on Web Technologies and Applications. Springer, 2003: 406-417.

[18] Song R, Liu H, Wen J R, et al. Learning block importance models for web pages[C]//Proceedings of the 13th International Conference on World Wide Web. ACM, 2004: 203-211.

[19] Cai D, Yu S, Wen J R, et al. VIPS: A vision-based page segmentation algorithm[R]. MSR-TR-2003-79, Microsoft Technical Report, 2003.

[20] Yu S, Cai D, Wen J R, et al. Improving pseudo-relevance feedback in web information retrieval using web page segmentation[C]//Proceedings of the 12th International Conference on World Wide Web. ACM, 2003: 11-18.

WEBSITE UPDATE MONITOR BASED ON WEB CRAWLER AND IMPROVED LCS ALGORITHMS

Zhou Xiaoke1Guo Kehua1,2

1(SchoolofInformationScienceandEngineering,CentralSouthUniversity,Changsha410000,Hunan,China)2(HighDimensionalInformationIntellisenseandSystemKeyLaboratoryoftheMinistryofEducation,Nanjing210094,Jiangsu,China)

With the explosive growth of information in Internet era, customers need to get the required information conveniently and timely. Traditional search engine and website subscription represented by RSS couldn’t satisfy the users’ high equality demand due to their disadvantages. Based on this, a new universal method of website update detection and subscription based on web crawler and text contrast is proposed. After analyzing and processing the successive webpage content, the proposed method would contrast the text, update contents and return the structured results to users. Experiment results show that this method conquers the difficult of RSS subscription’s feed limit, and makes it possible to add subscription on one’s own. It also got good performance upon university,enterprise,news,video,blog,forum websites etc.

Web crawler Noise reduction in web pages Website subscription Text contrast Update detection

2015-11-12。國家自然科學(xué)基金項目(61202341);高維信息智能感知與系統(tǒng)教育部重點實驗室創(chuàng)新基金項目(JYB201502);科技部國家國際科技合作專項項目(2013DFB10070);湖南省創(chuàng)新平臺專項項目(2012GK4106);中南大學(xué)創(chuàng)新驅(qū)動計劃；中南大學(xué)升華育英計劃。周孝錁，碩士生，主研領(lǐng)域：Web推薦，透明計算。郭克華，副教授。

TP391

A

10.3969/j.issn.1000-386x.2017.01.041