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

周孝錁 郭克華，2

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

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

周孝錁1郭克華1，2

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

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

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

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

0 引 言

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

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

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

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

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

1.1 系統(tǒng)框架

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

圖1 訂閱模塊流程圖

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

圖2 更新模塊流程圖

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

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

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

1.2 爬蟲(chóng)訪(fǎng)問(wèn)被拒問(wèn)題

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

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

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

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

1.3 過(guò)濾不合適鏈接

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

1.4 文本對(duì)比算法

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

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

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

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

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

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

(3) 缺口(Gap)：一個(gè)字符跟缺口相對(duì)。

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

Step3 填充矩陣。根據(jù)計(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中的計(jì)算，用箭頭表示F(i,j)(1≤i≤m,1≤j≤n)的來(lái)源，即上單元、左單元和左上角單元。然后根據(jù)箭頭從矩陣的最右下角一個(gè)單元開(kāi)始，回溯得到最長(zhǎng)公共子序列的路徑。

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

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

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

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

算法2Nakatsu提出的快速LCS算法，基于下面幾個(gè)基本定理[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)有長(zhǎng)度為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)

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

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

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

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

以上定理的證明請(qǐng)參閱文獻(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)所在對(duì)角線(xiàn)L(1,m-t+1)L(2,m-t+2)…L(t-1,m-1)L(t,m)所對(duì)應(yīng)的子序列B[L(1，m-t+l)]B[L(2，m-t+2)]…B[L(t，m)]即為A和B的LCS(也可能存在特殊情況，對(duì)角線(xiàn)所對(duì)應(yīng)的子字符串并非完全是LCS，后文會(huì)討論)，t為該LCS的長(zhǎng)度。于是，LCS問(wèn)題的求解就轉(zhuǎn)化為對(duì)Lm(k)矩陣的求解。

舉例說(shuō)明：給定字符串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的長(zhǎng)度t=5。

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

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

圖6 算法2的性能

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

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

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

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

圖7 存在多個(gè)LCS

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

圖8 四種匹配情形

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

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

(2) 對(duì)于對(duì)角線(xiàn)上元素L(k,i)(k>1,i>1)，若L(k-1,i-1)不為null和虛點(diǎn)，且L(k-1,i-1)

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

利用算法，獲得兩個(gè)字符串的LCS后，根據(jù)匹配情形即可得知差異部分，對(duì)應(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)題具有獨(dú)特性和功能性，標(biāo)題相同而內(nèi)容不同的情況是極少的；換言之，經(jīng)過(guò)文本對(duì)比匹配之后，得到的插入部分，在被比較網(wǎng)頁(yè)(稱(chēng)之為舊網(wǎng)頁(yè))中是不存在的(跟字符串匹配不同：插入的字符也可能存在被匹配字符串中)。所以，本文采用字符串?dāng)?shù)組對(duì)比，當(dāng)遇到多個(gè)LCS時(shí)，只需驗(yàn)證每種匹配情形下插入部分的字符串是否存在被比較的字符串?dāng)?shù)組中，即可判斷該匹配情形是否符合真實(shí)情況；若存在，則不是真實(shí)情況，排除。

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

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

2 實(shí)驗(yàn)結(jié)果與分析

2.1 實(shí)驗(yàn)設(shè)置

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

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

表1 測(cè)試網(wǎng)站編號(hào)表

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

續(xù)表2

2.2 實(shí)驗(yàn)結(jié)果

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

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

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

續(xù)表3

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

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

3 結(jié) 語(yǔ)

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

[1] 曹建勛, 劉奕群, 岑榮偉, 等. 基于用戶(hù)行為的色情網(wǎng)站識(shí)別[J]. 計(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] 荊明明. 基于A(yíng)ndroid的個(gè)性化RSS訂閱系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D]. 哈爾濱：哈爾濱工業(yè)大學(xué), 2011.

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

[9] 王大偉, 張巖, 曾皓, 等. 一個(gè)預(yù)測(cè)網(wǎng)頁(yè)變化的增量式更新模型[J]. 微計(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)笛. 最長(zhǎng)公共子序列問(wèn)題的改進(jìn)快速算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2000, 17(2): 28-30.

[15] 毛先領(lǐng), 何靖, 閆宏飛, 等. 網(wǎng)頁(yè)去噪: 研究綜述[J]. 計(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。國(guó)家自然科學(xué)基金項(xiàng)目(61202341);高維信息智能感知與系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室創(chuàng)新基金項(xiàng)目(JYB201502);科技部國(guó)家國(guó)際科技合作專(zhuān)項(xiàng)項(xiàng)目(2013DFB10070);湖南省創(chuàng)新平臺(tái)專(zhuān)項(xiàng)項(xiàng)目(2012GK4106);中南大學(xué)創(chuàng)新驅(qū)動(dòng)計(jì)劃；中南大學(xué)升華育英計(jì)劃。周孝錁，碩士生，主研領(lǐng)域：Web推薦，透明計(jì)算。郭克華，副教授。

TP391

A

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