宋 鰲，支 琤 ，周 軍，羅傳飛 ，安 然

（1.上海交通大學(xué) 電子工程系圖像通信與信息處理研究所，上海 200240；2.上海交通大學(xué) 上海市數(shù)字媒體處理與傳輸重點(diǎn)實(shí)驗(yàn)室，上海 200240；3.上海文廣互動(dòng)電視有限公司，上海 200072）

責(zé)任編輯:史麗麗

0 引言

一個(gè)網(wǎng)頁(yè)一般包含一些內(nèi)容塊，但除了這些內(nèi)容塊，文獻(xiàn)[1]中往往包含導(dǎo)航欄、版權(quán)信息、公告消息以及各種各樣形式的廣告，它們的存在是為了商業(yè)目的或者便于用戶使用，這些與主題無(wú)關(guān)的信息稱之為網(wǎng)頁(yè)噪聲塊。如何降低網(wǎng)頁(yè)中的噪聲，對(duì)于網(wǎng)頁(yè)分類、特征提取、內(nèi)容聚合具有重要意義，已成為在三網(wǎng)融合的大背景中，基于多媒體內(nèi)容融合[2]的研究熱點(diǎn)。筆者提出了一種基于LCS的特征樹(shù)結(jié)構(gòu)最大相似性匹配算法，對(duì)目標(biāo)網(wǎng)頁(yè)及其相似網(wǎng)頁(yè)生成的特征樹(shù)進(jìn)行相似性匹配，然后根據(jù)匹配結(jié)果的不同之處生成內(nèi)容塊候選集，并對(duì)候選集根據(jù)內(nèi)容塊的相似程度和樹(shù)結(jié)構(gòu)進(jìn)行聚集，對(duì)聚集結(jié)果的特征進(jìn)行分析評(píng)分得到最后的內(nèi)容塊，達(dá)到網(wǎng)頁(yè)去噪的目的。

1 相關(guān)研究

目前已有很多種網(wǎng)頁(yè)去噪算法，有基于網(wǎng)頁(yè)視覺(jué)特性的，利用一個(gè)網(wǎng)頁(yè)布局來(lái)建立視覺(jué)結(jié)構(gòu)，同時(shí)利用這個(gè)視覺(jué)結(jié)構(gòu)將網(wǎng)頁(yè)分塊[3-4]；在對(duì)網(wǎng)頁(yè)分塊之后，利用人工標(biāo)注并通過(guò)神經(jīng)網(wǎng)絡(luò)和支持向量機(jī)來(lái)對(duì)網(wǎng)頁(yè)塊特性到塊重要性的映射函數(shù)進(jìn)行學(xué)習(xí)，最后得到通用的映射方法[5]。也有基于規(guī)則的，通過(guò)定義一些映射規(guī)則，將網(wǎng)頁(yè)的一些特征轉(zhuǎn)化為權(quán)值，通過(guò)權(quán)值比較來(lái)實(shí)現(xiàn)內(nèi)容塊和噪聲塊的區(qū)分[6-9]。其中文獻(xiàn)[6]中提出了一種利用文本塊大小和位置得到一個(gè)閾值，再利用鏈接數(shù)和非鏈接文字長(zhǎng)度的比值來(lái)和該閾值進(jìn)行比較，得出內(nèi)容塊。文獻(xiàn)[7]中提出對(duì)來(lái)自同一個(gè)站點(diǎn)的多個(gè)網(wǎng)頁(yè)實(shí)現(xiàn)主要內(nèi)容塊的尋找，通過(guò)一些塊特性，如文本長(zhǎng)度、圖片數(shù)目、鏈接數(shù)目、詞匯矩陣、位置等來(lái)判斷網(wǎng)頁(yè)塊的相似性，在同一網(wǎng)站中獲取到的頁(yè)面中，在多個(gè)網(wǎng)頁(yè)中出現(xiàn)的相似的網(wǎng)頁(yè)塊是非內(nèi)容塊。文獻(xiàn)[8]中提出將網(wǎng)頁(yè)當(dāng)成內(nèi)容單元序列，且每個(gè)內(nèi)容單元有其權(quán)值的山峰模型，并利用SVM對(duì)塊特征進(jìn)行分類找出主要內(nèi)容塊。文獻(xiàn)[9]中提出將DOM樹(shù)的節(jié)點(diǎn)分為HTMLItem和Content兩種節(jié)點(diǎn)，將Content按種類（圖片、文字、鏈接）和數(shù)量計(jì)算權(quán)值，加在其所屬HTMLItem節(jié)點(diǎn)上作為其重要性的度量，同時(shí)HTMLItem自己也有權(quán)值，且隨著其深度遞減。最后按權(quán)值的大小去除噪聲塊。這些方法各有各的特點(diǎn)，但也各有各的局限性，如基于視覺(jué)特性的算法，忽略了內(nèi)容的重要性；機(jī)器學(xué)習(xí)太復(fù)雜，效率不高；基于規(guī)則的算法只適用于某些類型的網(wǎng)頁(yè)等。文獻(xiàn)[10]中提出一種使用限制從上到下映射的樹(shù)編輯距離來(lái)自動(dòng)獲取網(wǎng)頁(yè)新聞的算法，他們的算法在對(duì)節(jié)點(diǎn)比較時(shí)只有相同和不相同兩種絕對(duì)狀態(tài)，而實(shí)際網(wǎng)頁(yè)節(jié)點(diǎn)之間可能有部分特征是相同的。

針對(duì)以上方法的不足，本文提出了基于LCS的特征樹(shù)最大相似性匹配算法，將網(wǎng)頁(yè)特征樹(shù)轉(zhuǎn)化為節(jié)點(diǎn)序列來(lái)實(shí)現(xiàn)全局最大匹配，同樣也是利用樹(shù)的相似性匹配來(lái)實(shí)現(xiàn)網(wǎng)頁(yè)去噪，不同的是采用了特征樹(shù)，保留了DOM樹(shù)中必要的特征屬性以及由這些屬性轉(zhuǎn)換而來(lái)的新特征，另外對(duì)節(jié)點(diǎn)的匹配采用了相似度的概念，用一個(gè)介于0到1之間的數(shù)來(lái)表征節(jié)點(diǎn)之間的相似程度，且對(duì)內(nèi)容節(jié)點(diǎn)和結(jié)構(gòu)節(jié)點(diǎn)區(qū)別對(duì)待。

2 網(wǎng)頁(yè)去噪算法與系統(tǒng)實(shí)現(xiàn)

2.1 整體系統(tǒng)概述

本文利用LCS的特征樹(shù)最大相似性匹配算法來(lái)實(shí)現(xiàn)網(wǎng)頁(yè)去噪。分為以下幾個(gè)步驟:網(wǎng)頁(yè)修復(fù)與初步清理、目標(biāo)網(wǎng)頁(yè)的相似網(wǎng)頁(yè)獲取、由網(wǎng)頁(yè)DOM生成特征樹(shù)、特征樹(shù)的LCS最大相似性匹配、網(wǎng)頁(yè)內(nèi)容塊候選集聚集、尋找最可能的內(nèi)容塊聚集。系統(tǒng)流程圖如圖1所示。

2.2 網(wǎng)頁(yè)的預(yù)處理

Internet上的網(wǎng)頁(yè)往往有很多與網(wǎng)頁(yè)信息無(wú)關(guān)的標(biāo)簽，同時(shí)也有很多不符合W3C標(biāo)準(zhǔn)的錯(cuò)誤，這些錯(cuò)誤得不到修正會(huì)影響接下來(lái)的算法分析，有必要在這之前進(jìn)行一些預(yù)處理工作。

去除掉一些與網(wǎng)頁(yè)內(nèi)容無(wú)關(guān)項(xiàng)（如JavaScript腳本、注釋等），JavaScript是動(dòng)態(tài)客戶端腳本，一般用于網(wǎng)頁(yè)與用戶的互動(dòng)，與網(wǎng)頁(yè)內(nèi)容無(wú)關(guān)；注釋是網(wǎng)頁(yè)設(shè)計(jì)者為了方便設(shè)計(jì)而添加的網(wǎng)頁(yè)頁(yè)面不可見(jiàn)的內(nèi)容，因此也可以直接刪除。

同時(shí)修正相對(duì)路徑問(wèn)題，由于網(wǎng)頁(yè)是下載到本地后進(jìn)行處理，處理完后無(wú)法放到原網(wǎng)站環(huán)境下去顯示，因此需要把相對(duì)URI地址轉(zhuǎn)化為絕對(duì)URI地址，這包括鏈接、圖片、CSS文件、iframe、frame的URI地址。

修正不符合W3C標(biāo)準(zhǔn)的網(wǎng)頁(yè)錯(cuò)誤，這包括標(biāo)簽的錯(cuò)誤嵌套，標(biāo)簽不成對(duì)出現(xiàn)等。

2.3 特征樹(shù)與基于LCS的特征樹(shù)最大相似性匹配算法

算法的核心思想是將樹(shù)形結(jié)構(gòu)轉(zhuǎn)化為等價(jià)的序列結(jié)構(gòu)，并對(duì)序列進(jìn)行最長(zhǎng)子序列匹配，找出兩個(gè)序列不同之處，再映射到樹(shù)上找出不同的樹(shù)枝。匹配的序列越長(zhǎng)，得出的不同樹(shù)枝越少，得到的內(nèi)容塊候選集就越少，因此序列的全局最長(zhǎng)匹配有利于尋找最重要內(nèi)容塊。下面首先定義特征樹(shù)，然后簡(jiǎn)要分析了要將LCS算法應(yīng)用于樹(shù)形結(jié)構(gòu)的匹配，其需要修改的地方，最后給出了LCS的特征樹(shù)最大相似性匹配算法的步驟。

2.3.1 特征樹(shù)

網(wǎng)頁(yè)DOM樹(shù)是一種能充分表示布局和樣式的模型，但很難根據(jù)它去研究一個(gè)HTML所有的樣式和內(nèi)容，而且DOM樹(shù)的有些屬性特征是最原始的沒(méi)有經(jīng)過(guò)處理的信息，無(wú)法用于樹(shù)的相似性比較。使用DOM樹(shù)來(lái)作為兩個(gè)網(wǎng)頁(yè)的相似性最大匹配是不適合的，因此需要構(gòu)造一個(gè)新的樹(shù)形結(jié)構(gòu)來(lái)表示網(wǎng)頁(yè)，需要既簡(jiǎn)潔又能充分表示網(wǎng)頁(yè)信息。筆者引入了特征樹(shù)（CTree）。

特征樹(shù)由特征節(jié)點(diǎn)（CNode）構(gòu)成，以網(wǎng)頁(yè)body節(jié)點(diǎn)為根節(jié)點(diǎn)。CNode去除了DOM樹(shù)節(jié)點(diǎn)中不利于做相似性匹配的屬性，加入了一些由DOM樹(shù)種的屬性進(jìn)行變換融合的屬性，這包括深度、上邊距、左邊距和文本率，CNode的定義如下:

定義1:CNode，一個(gè)特征節(jié)點(diǎn)對(duì)應(yīng)網(wǎng)頁(yè)中的一個(gè)標(biāo)簽，它表征了一個(gè)標(biāo)簽的內(nèi)容特征、結(jié)構(gòu)特征和空間特征。內(nèi)容特征是節(jié)點(diǎn)本身的屬性，結(jié)構(gòu)特征是該節(jié)點(diǎn)與其他節(jié)點(diǎn)之間的關(guān)系，空間特征是網(wǎng)頁(yè)布局特征，即網(wǎng)頁(yè)塊的位置、大小等。每個(gè)節(jié)點(diǎn)包含以下屬性:

1）標(biāo)簽名（tagName）:如body，div，span等；

2）節(jié)點(diǎn)ID（id）:唯一表征一個(gè)節(jié)點(diǎn)的ID，不一定每個(gè)標(biāo)簽都有；

3）樣式表類名（className）:表示該節(jié)點(diǎn)所應(yīng)用的樣式表的類；

4）父節(jié)點(diǎn)（parentNode）:表示該節(jié)點(diǎn)的父親節(jié)點(diǎn)；

5）子節(jié)點(diǎn)（children）:表示該節(jié)點(diǎn)所有的子節(jié)點(diǎn)；

6）深度（Depth）:表示該節(jié)點(diǎn)在特征樹(shù)中的層次深度；

7）寬度（Width）:節(jié)點(diǎn)所代表的網(wǎng)頁(yè)塊的寬度；

8）高度（Height）:節(jié)點(diǎn)所代表的網(wǎng)頁(yè)塊的高度；

9）上邊距（Top）:節(jié)點(diǎn)所代表的網(wǎng)頁(yè)塊距頁(yè)面頂部的距離；

10）左邊距（Left）:節(jié)點(diǎn)所代表的網(wǎng)頁(yè)塊距頁(yè)面左邊的距離；

11）外部HTML（outerHTML）:包含該節(jié)點(diǎn)的所有網(wǎng)頁(yè)代碼；

12）內(nèi)部HTML（innerHTML）:該節(jié)點(diǎn)內(nèi)部的所有網(wǎng)頁(yè)代碼；

13）內(nèi)部文本（innerText）:該節(jié)點(diǎn)內(nèi)部的所有文本；

14）文本率（textRate）:表征該節(jié)點(diǎn)文本含量。

其中，1），2），3），11），12），13），14）是內(nèi)容特征；4），5），6）是結(jié)構(gòu)特征；7），8），9），10）是空間特征。

2.3.2 基于LCS的特征樹(shù)最大相似性匹配算法

LCS算法[11]常用于比較兩段文本的相似性或兩個(gè)序列的相似性，如在生物上可以比較兩個(gè)DNA序列的相似性。LCS算法不能直接運(yùn)用于樹(shù)，原因有以下3點(diǎn):

1）LCS算法是針對(duì)序列結(jié)構(gòu)的全局最大匹配算法，因此需要將特征樹(shù)轉(zhuǎn)化為特征節(jié)點(diǎn)隊(duì)列，然后再做匹配。本文中使用的是逐層遍歷。

2）與平常文本或DNA匹配不同，樹(shù)節(jié)點(diǎn)之間的比較不能用相等和不相等來(lái)描述，例如，圖2中特征樹(shù)CT1的B節(jié)點(diǎn)和CT2中B’節(jié)點(diǎn)，它們?cè)跇?shù)的位置上一致，同時(shí)假設(shè)其id、標(biāo)簽名、位置、大小等特征屬性是相同的，顯然應(yīng)該認(rèn)為它們是相似的，但B節(jié)點(diǎn)有三個(gè)子節(jié)點(diǎn)，而B(niǎo)’只有兩個(gè)子節(jié)點(diǎn)，它們不是完全相同的。所以應(yīng)該用相似性來(lái)描述，通過(guò)比較節(jié)點(diǎn)的各個(gè)特征來(lái)得到節(jié)點(diǎn)之間的相似度，相似度是一個(gè)介于0到1之間的數(shù)值，0表示完全不同，1表示完全相同，而在0和1之間則表示有部分相同。

3）在將特征樹(shù)轉(zhuǎn)化為節(jié)點(diǎn)隊(duì)列時(shí)，已經(jīng)沒(méi)有了樹(shù)的結(jié)構(gòu)，這可能出現(xiàn)以下的情況:

特征樹(shù)CT1轉(zhuǎn)換為序列為ABCDEFG，特征樹(shù)CT2轉(zhuǎn)換為序列為A’B’C’D’E’F’G’，假設(shè)A與A’相似，B與B’相似……，按LCS算法它們是完全相同的，但對(duì)樹(shù)來(lái)說(shuō)，F(xiàn)節(jié)點(diǎn)的父節(jié)點(diǎn)是B，F(xiàn)’節(jié)點(diǎn)是C’，它們屬于不同的樹(shù)枝，顯然這兩棵樹(shù)是不同的，在比較兩個(gè)節(jié)點(diǎn)相似性時(shí)還需要考慮其父親節(jié)點(diǎn)是否相似。

在介紹基于LCS的特征樹(shù)最大相似性匹配算法之前，先定義幾個(gè)算法中用到的概念如下:

定義2:文本率（textRate），是指該節(jié)點(diǎn)的文本（不包含子節(jié)點(diǎn)的）與該節(jié)點(diǎn)內(nèi)的所有文本（包含子節(jié)點(diǎn)的）之間的比值，它表征了該節(jié)點(diǎn)在以該節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹(shù)中的文本含量。

定義3:內(nèi)容標(biāo)簽（contentTag），是指網(wǎng)頁(yè)中常用于顯示內(nèi)容的標(biāo)簽，這包括 P，SPAN，B，STRONG，H1，H2，H3，H4，H5，H6等。

定義4:內(nèi)容節(jié)點(diǎn)（contentNode），如果一個(gè)特征節(jié)點(diǎn)的標(biāo)簽是內(nèi)容標(biāo)簽，那么它是內(nèi)容節(jié)點(diǎn)；否則如果它的文本率大于75%，那么也是內(nèi)容節(jié)點(diǎn)。

定義5:結(jié)構(gòu)節(jié)點(diǎn)（structureNode），所有特征節(jié)點(diǎn)中除了是內(nèi)容節(jié)點(diǎn)以外的那些節(jié)點(diǎn)。

定義6:相似度閾值（Ts），是一個(gè)介于0到1之間的值，大于該值，認(rèn)為兩個(gè)特征節(jié)點(diǎn)是相似的，否則是不相似的。

定義7:目標(biāo)網(wǎng)頁(yè)內(nèi)容塊候選集，指目標(biāo)網(wǎng)頁(yè)特征樹(shù)不同于相似網(wǎng)頁(yè)特征樹(shù)的節(jié)點(diǎn)的集合。

下面是基于LCS的特征樹(shù)最大相似性匹配算法步驟:

假設(shè)有兩棵特征樹(shù)CTree1和CTree2，將它們按逐層遍歷得到數(shù)組序列S1和S2。定義兩個(gè)二維數(shù)組scoreTable和pointerTable，分別保存子問(wèn)題相似度累和與回溯方向，可以將scoreTable這個(gè)二維數(shù)組看成一個(gè)表格，第一維對(duì)應(yīng)表格的行，第二維對(duì)應(yīng)列。與LCS算法不同，此處表格單元格不再代表最長(zhǎng)子序列長(zhǎng)度，而是子序列相似度累加的最大值。假設(shè)scoreTable行方向的序列是S1，列方向的序列是S2，算法步驟如下:

1）初始化兩個(gè)二維數(shù)組

scoreTable所有單元格賦值為0；pointerTable第一行除第一個(gè)單元格外全部記錄向左方向，第一列除第一個(gè)單元格外全部記錄向上方向。

2）循環(huán)計(jì)算子問(wèn)題的相似度累和以及回溯方向

從scoreTable第二行第二列開(kāi)始逐行計(jì)算單元格值和pointerTable對(duì)應(yīng)單元格的方向值。

其中，CompareTwoCNode是計(jì)算兩個(gè)特征節(jié)點(diǎn)相似性的函數(shù)，輸入為兩個(gè)節(jié)點(diǎn)，輸出是一個(gè)介于0～1之間的值，即相似度。CompareTwoCNode的實(shí)現(xiàn)方法如下:

（1）如果兩個(gè)節(jié)點(diǎn)標(biāo)簽名不同，返回0。

（2）如果兩個(gè)節(jié)點(diǎn)都是BODY節(jié)點(diǎn)，返回1，BODY節(jié)點(diǎn)是一個(gè)特殊的節(jié)點(diǎn)，它是每棵特征樹(shù)的根節(jié)點(diǎn)，對(duì)于BODY節(jié)點(diǎn)，不管它們是否有特征不相同，都認(rèn)為它們是相似的，而且相似度為1。

（3）如果一個(gè)是BODY節(jié)點(diǎn)，一個(gè)不是，返回0。

（4）如果兩個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)不相似，返回0。

（5）如果兩個(gè)節(jié)點(diǎn)都是內(nèi)容節(jié)點(diǎn)，則比較它們的in?nerHTML，相同返回1，否則返回0，對(duì)于內(nèi)容節(jié)點(diǎn)，在比較時(shí)要求比較苛刻，除了在特征上要求相似，還要求其在內(nèi)容上相同。

（6）如果兩個(gè)節(jié)點(diǎn)一個(gè)是內(nèi)容節(jié)點(diǎn)，一個(gè)是結(jié)構(gòu)節(jié)點(diǎn)，返回0。

（7）在上面所有情況都不滿足的情況下，計(jì)算兩個(gè)節(jié)點(diǎn)各特征相同的數(shù)目與特征總數(shù)目的比值，返回比值。這里的特征包括ID、樣式表類名（className）、節(jié)點(diǎn)在特征樹(shù)中的深度（Depth）、節(jié)點(diǎn)代表的網(wǎng)頁(yè)塊的寬度、高度、左邊距、上邊距等。

算法中用到的getDirection用于計(jì)算回溯方向，輸入是三個(gè)方向上的相似度累和，輸出是上、左、左上中的一個(gè)方向。其計(jì)算方法如下:

（1）在不相同的情況下，選取相似度累和最大的那個(gè)方向；

（2）在有兩個(gè)或三個(gè)方向上相似度累和相同的情況下，按優(yōu)先選取左上，然后是上，最后是左的原則。

3）算法回溯

假設(shè)CTree1是目標(biāo)網(wǎng)頁(yè)的特征樹(shù)，CTree2是相似網(wǎng)頁(yè)的特征樹(shù)。與LCS算法不同，大家感興趣的不是兩棵樹(shù)相似之處，而是希望得到CTree1上特有的，而CTree2上沒(méi)有或不同的樹(shù)枝或節(jié)點(diǎn)?；厮輳亩S數(shù)組對(duì)應(yīng)的表格的右下角開(kāi)始，pointerTable記錄了回溯方向?？紤]要將S1變換為S2，對(duì)于向上的方向，對(duì)S1來(lái)說(shuō)此處發(fā)生了添加操作，添加操作意味著該節(jié)點(diǎn)是S1沒(méi)有而S2有的節(jié)點(diǎn)，不是S1不同于S2的節(jié)點(diǎn)，忽略。對(duì)于向左的方向，S1發(fā)生了刪除操作，意味著S1有而S2沒(méi)有的節(jié)點(diǎn)，將其加入目標(biāo)網(wǎng)頁(yè)內(nèi)容塊候選集。對(duì)于左上方向，本單元格的值是左上單元格相似度累和與本單元格位置上的S1序列和S2序列的節(jié)點(diǎn)之間的相似度之和，因此可以用本單元格值減去左上單元格值得到此處兩節(jié)點(diǎn)的相似度，與相似度閾值（Ts）進(jìn)行比較，如果大于閾值，則認(rèn)為兩節(jié)點(diǎn)相似，忽略；如果小于閾值，此處發(fā)生替換操作，意味著S1有S2也有但不相似的節(jié)點(diǎn)，將其加入目標(biāo)網(wǎng)頁(yè)內(nèi)容塊候選集。

2.4 目標(biāo)網(wǎng)頁(yè)內(nèi)容塊聚集

聚集的目的是消除內(nèi)容塊候選集中的祖先和子孫關(guān)系，并將在特征樹(shù)位置上比較接近的節(jié)點(diǎn)匯聚在一個(gè)集合里面，有利于將內(nèi)容塊和孤立的噪聲塊分開(kāi)，以便進(jìn)行下一步的評(píng)分。在前面算法的處理中基本消除了導(dǎo)航欄、固定位置或固定內(nèi)容的廣告，但一些頁(yè)面獨(dú)有的廣告或其他噪聲塊還是混雜在候選集里，但它們?cè)诓季稚虾徒Y(jié)構(gòu)上與內(nèi)容信息塊是孤立的，很容易通過(guò)聚集將它們區(qū)別開(kāi)來(lái)。在本文實(shí)驗(yàn)中首先檢查候選集類是否有某個(gè)節(jié)點(diǎn)的子孫節(jié)點(diǎn)，有則將子孫節(jié)點(diǎn)從候選集中去除；然后隨機(jī)選取一個(gè)候選集中的節(jié)點(diǎn)，在候選集其他節(jié)點(diǎn)中尋找與其有相同父親節(jié)點(diǎn)的節(jié)點(diǎn)或那些爺爺節(jié)點(diǎn)是其父親節(jié)點(diǎn)的節(jié)點(diǎn)，將它們置于同一個(gè)集合中，繼續(xù)對(duì)剩下的節(jié)點(diǎn)做同樣的操作，直到候選集中所有節(jié)點(diǎn)都處理完畢。最后得到多個(gè)集合，被稱之為網(wǎng)頁(yè)內(nèi)容塊聚集簇。

2.5 評(píng)分篩選

實(shí)驗(yàn)的最終目的是要找出網(wǎng)頁(yè)中的內(nèi)容塊，對(duì)網(wǎng)頁(yè)內(nèi)容塊聚集簇中的每個(gè)集合進(jìn)行特征分析并評(píng)分，找出最重要的內(nèi)容塊。

定義8:主要視覺(jué)區(qū)域（mainVisualArea），是指網(wǎng)頁(yè)設(shè)計(jì)中常將主要內(nèi)容置于靠中間的區(qū)域，這個(gè)區(qū)域是用戶打開(kāi)網(wǎng)頁(yè)后目光集中的區(qū)域。

特征分析將從以下幾個(gè)指標(biāo)入手:文本長(zhǎng)度、面積、有效面積、內(nèi)容標(biāo)簽數(shù)目、鏈接率、文本代碼比率。文本長(zhǎng)度是一個(gè)聚集簇中所有節(jié)點(diǎn)的內(nèi)部文本長(zhǎng)度的總和，噪聲往往文字較少，因此文本越長(zhǎng)其越有可能是內(nèi)容塊。面積是一個(gè)聚集簇中所有節(jié)點(diǎn)對(duì)應(yīng)的網(wǎng)頁(yè)塊其所占區(qū)域面積的總和，占有面積越大越有可能是內(nèi)容塊。有效面積是指一個(gè)聚集簇中所有節(jié)點(diǎn)對(duì)應(yīng)的網(wǎng)頁(yè)塊與主要視覺(jué)區(qū)域重合的面積的總和，在網(wǎng)頁(yè)中的有效面積是區(qū)分內(nèi)容塊和噪聲塊的一個(gè)重要指標(biāo)。內(nèi)容標(biāo)簽數(shù)目是指一個(gè)聚集簇中包含定義3中定義的內(nèi)容標(biāo)簽的個(gè)數(shù)總和，顯然內(nèi)容標(biāo)簽數(shù)目越多，越有可能是內(nèi)容塊。鏈接率是指一個(gè)聚集簇中所有節(jié)點(diǎn)中（包括子孫節(jié)點(diǎn)中的）鏈接節(jié)點(diǎn)的代碼長(zhǎng)度總和與所有節(jié)點(diǎn)代碼長(zhǎng)度總和的比值，這是抑制噪聲的一個(gè)重要指標(biāo)，噪聲往往含有大量鏈接，通過(guò)計(jì)算這個(gè)比值，很容易區(qū)分內(nèi)容塊和噪聲塊。文本代碼比率是表征文本占總HTML代碼的百分比，內(nèi)容塊有較大的文本代碼比率。

在計(jì)算了上述指標(biāo)之后，接下來(lái)對(duì)每個(gè)聚集簇進(jìn)行評(píng)分，對(duì)于有助于尋找內(nèi)容塊的指標(biāo)（如文本長(zhǎng)度），給排名靠前的聚集簇加分，對(duì)于有利于尋找噪聲塊的指標(biāo)（如鏈接率），對(duì)排名靠前的減分懲罰。對(duì)于每個(gè)指標(biāo)對(duì)聚集簇按從大到小排序，對(duì)前三個(gè)進(jìn)行打分。對(duì)于鏈接率，按-5，-3，-1分值打分；對(duì)其他指標(biāo)按5，3，1分值打分。最后每個(gè)聚集簇都有一個(gè)評(píng)分，對(duì)其進(jìn)行排名，選取靠前的幾個(gè)分值比較接近的聚集簇作為最后的結(jié)果，即目標(biāo)網(wǎng)頁(yè)的內(nèi)容塊。

3 實(shí)驗(yàn)結(jié)果和分析

筆者從幾個(gè)著名中文門戶網(wǎng)站（新浪、騰訊、網(wǎng)易和搜狐）獲取共計(jì)2458個(gè)不同類別的網(wǎng)頁(yè)地址，作為輸入來(lái)測(cè)試本文提出的網(wǎng)頁(yè)去噪算法和系統(tǒng)。這些類別包括新聞、體育、娛樂(lè)和軍事，筆者的算法達(dá)到了總的平均95.1%的正確率。選取網(wǎng)頁(yè)測(cè)試集如表1所示。

表1 網(wǎng)頁(yè)測(cè)試集

經(jīng)過(guò)對(duì)系統(tǒng)輸出的網(wǎng)頁(yè)內(nèi)容塊與原目標(biāo)網(wǎng)頁(yè)進(jìn)行對(duì)比，通過(guò)人工判斷對(duì)每一個(gè)網(wǎng)頁(yè)比較正確性。最后計(jì)算網(wǎng)頁(yè)去噪正確率[9]，其計(jì)算方法為

測(cè)試結(jié)果見(jiàn)表2和表3，表2中按每個(gè)網(wǎng)站每個(gè)類別分別計(jì)算，從中可以看出對(duì)各類別都有很好的去噪效果，尤其對(duì)內(nèi)容型網(wǎng)頁(yè)。搜狐軍事結(jié)果較差的原因是較多頁(yè)面是flash視頻播放頁(yè)面，包含文字較少，難于找出內(nèi)容塊。表3是對(duì)各個(gè)網(wǎng)站的綜合統(tǒng)計(jì)結(jié)果，可以看出對(duì)不同網(wǎng)站都能有很好的去噪效果。

4 結(jié)論與未來(lái)展望

本文描述了一種基于LCS的特征樹(shù)最大相似性匹配的網(wǎng)頁(yè)去噪算法，同時(shí)具有高準(zhǔn)確率和高覆蓋率的優(yōu)點(diǎn)，尤其對(duì)于內(nèi)容型網(wǎng)頁(yè)。通過(guò)分析目標(biāo)網(wǎng)頁(yè)的鏈接找到相似網(wǎng)頁(yè)，再將目標(biāo)網(wǎng)頁(yè)和相似網(wǎng)頁(yè)轉(zhuǎn)化為特征樹(shù)，并將特征樹(shù)映射為一個(gè)特征節(jié)點(diǎn)序列，利用LCS算法能獲得最長(zhǎng)子序列全局最優(yōu)解的特點(diǎn)，找出兩棵特征樹(shù)之間的不同節(jié)點(diǎn)作為目標(biāo)網(wǎng)頁(yè)內(nèi)容塊候選集，并對(duì)候選集進(jìn)行聚集評(píng)分找出網(wǎng)頁(yè)重要內(nèi)容塊。實(shí)驗(yàn)表明本文的算法在正確率方面表現(xiàn)得很好。

表2 各網(wǎng)站分類表測(cè)試結(jié)果

表3 各網(wǎng)站總測(cè)試結(jié)果

[1]YILan，LIU Bing，LIXiaoli.Eliminating noisy information in web pages for data mining[C]//Proceedings ofthe ninth ACM SIGKDD international conference on knowledge discovery and data mining.Washington，DC:s.n.，2003:296-305.

[2]王厚芹，車士義.推進(jìn)我國(guó)三網(wǎng)融合勢(shì)在必行[J].電視技術(shù)，2010，34（6）:109-112.

[3]CAID，YU S，WEN J R，etal.Extracting contentstructure for web pages based on visualrepresentation.Asia Pacific[C]//Proceedings ofthe 5th Asia-Pacific web conference on Web technologies and applications.Xi’an:s.n.，2003:406-417.

[4]CAID，YU S，WEN J R，etal.VIPS:a vision-based page segmentation algorithm[R].MicrosoftTechnicalReport:MSR-TR-2003-79，2003.

[5]SONG Ruihua，LIU Haifeng，WEN JiRong，et al.Learning block importance models for web pages[C]//Proceedings of ACM SIGKDD Explorations Newsletter.New York:[s.n.]，2004（6）:14-23.

[6]劉晨曦，吳揚(yáng)揚(yáng).一種基于塊分析的網(wǎng)頁(yè)去噪音方法[J].廣西師范大學(xué):自然科學(xué)版，2007，25（2）:149-152.

[7]DEBNATH S，MITRA P，PAL N，etal.Automatic identification of informative sections ofweb pages[J].IEEE Transactions on Knowledge and Data Engineering，2005，17（9）:1233-1246.

[8]Lidong Bing，Yexin Wang，Yan Zhang，etal.Primary Content Extraction with Mountain Model[C]//Proceedings of 2008 IEEE 8th International Conference on Computerand Information Technology.[S.l.]:IEEE Press，2008:479-484.

[9]LI Yuancheng，YANG Jie.A novelmethod to extractinformative blocks from web pages[C]//Proceedings of the 2009 International Joint Conference on ArtificialIntelligence.2009:536-539

[10]REIS D C，GOLGHER P B，SILVA A S，et al.Automatic web news extraction using tree editdistance[C]//Proceedings ofthe 13th International Conference on World Wide Web.New York:ACM，2004:502-511.

[11]BERGROTH L，HAKONEN H，RAITA T.A survey oflongestcommon subsequence algorithms[C]//Proceedings of the Seventh International Symposium on String Processing Information Retrieval.Washington，DC:s.n.，2000:39-48.