基于LCS的特征樹最大相似性匹配網頁去噪算法

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

（1.上海交通大學 電子工程系圖像通信與信息處理研究所，上海 200240；2.上海交通大學 上海市數字媒體處理與傳輸重點實驗室，上海 200240；3.上海文廣互動電視有限公司，上海 200072）

責任編輯:史麗麗

0 引言

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

1 相關研究

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

針對以上方法的不足，本文提出了基于LCS的特征樹最大相似性匹配算法，將網頁特征樹轉化為節點序列來實現全局最大匹配，同樣也是利用樹的相似性匹配來實現網頁去噪，不同的是采用了特征樹，保留了DOM樹中必要的特征屬性以及由這些屬性轉換而來的新特征，另外對節點的匹配采用了相似度的概念，用一個介于0到1之間的數來表征節點之間的相似程度，且對內容節點和結構節點區別對待。

2 網頁去噪算法與系統實現

2.1 整體系統概述

本文利用LCS的特征樹最大相似性匹配算法來實現網頁去噪。分為以下幾個步驟:網頁修復與初步清理、目標網頁的相似網頁獲取、由網頁DOM生成特征樹、特征樹的LCS最大相似性匹配、網頁內容塊候選集聚集、尋找最可能的內容塊聚集。系統流程圖如圖1所示。

2.2 網頁的預處理

Internet上的網頁往往有很多與網頁信息無關的標簽，同時也有很多不符合W3C標準的錯誤，這些錯誤得不到修正會影響接下來的算法分析，有必要在這之前進行一些預處理工作。

去除掉一些與網頁內容無關項（如JavaScript腳本、注釋等），JavaScript是動態客戶端腳本，一般用于網頁與用戶的互動，與網頁內容無關；注釋是網頁設計者為了方便設計而添加的網頁頁面不可見的內容，因此也可以直接刪除。

同時修正相對路徑問題，由于網頁是下載到本地后進行處理，處理完后無法放到原網站環境下去顯示，因此需要把相對URI地址轉化為絕對URI地址，這包括鏈接、圖片、CSS文件、iframe、frame的URI地址。

修正不符合W3C標準的網頁錯誤，這包括標簽的錯誤嵌套，標簽不成對出現等。

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

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

2.3.1 特征樹

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

特征樹由特征節點（CNode）構成，以網頁body節點為根節點。CNode去除了DOM樹節點中不利于做相似性匹配的屬性，加入了一些由DOM樹種的屬性進行變換融合的屬性，這包括深度、上邊距、左邊距和文本率，CNode的定義如下:

定義1:CNode，一個特征節點對應網頁中的一個標簽，它表征了一個標簽的內容特征、結構特征和空間特征。內容特征是節點本身的屬性，結構特征是該節點與其他節點之間的關系，空間特征是網頁布局特征，即網頁塊的位置、大小等。每個節點包含以下屬性:

1）標簽名（tagName）:如body，div，span等；

2）節點ID（id）:唯一表征一個節點的ID，不一定每個標簽都有；

3）樣式表類名（className）:表示該節點所應用的樣式表的類；

4）父節點（parentNode）:表示該節點的父親節點；

5）子節點（children）:表示該節點所有的子節點；

6）深度（Depth）:表示該節點在特征樹中的層次深度；

7）寬度（Width）:節點所代表的網頁塊的寬度；

8）高度（Height）:節點所代表的網頁塊的高度；

9）上邊距（Top）:節點所代表的網頁塊距頁面頂部的距離；

10）左邊距（Left）:節點所代表的網頁塊距頁面左邊的距離；

11）外部HTML（outerHTML）:包含該節點的所有網頁代碼；

12）內部HTML（innerHTML）:該節點內部的所有網頁代碼；

13）內部文本（innerText）:該節點內部的所有文本；

14）文本率（textRate）:表征該節點文本含量。

其中，1），2），3），11），12），13），14）是內容特征；4），5），6）是結構特征；7），8），9），10）是空間特征。

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

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

1）LCS算法是針對序列結構的全局最大匹配算法，因此需要將特征樹轉化為特征節點隊列，然后再做匹配。本文中使用的是逐層遍歷。

2）與平常文本或DNA匹配不同，樹節點之間的比較不能用相等和不相等來描述，例如，圖2中特征樹CT1的B節點和CT2中B’節點，它們在樹的位置上一致，同時假設其id、標簽名、位置、大小等特征屬性是相同的，顯然應該認為它們是相似的，但B節點有三個子節點，而B’只有兩個子節點，它們不是完全相同的。所以應該用相似性來描述，通過比較節點的各個特征來得到節點之間的相似度，相似度是一個介于0到1之間的數值，0表示完全不同，1表示完全相同，而在0和1之間則表示有部分相同。

3）在將特征樹轉化為節點隊列時，已經沒有了樹的結構，這可能出現以下的情況:

特征樹CT1轉換為序列為ABCDEFG，特征樹CT2轉換為序列為A’B’C’D’E’F’G’，假設A與A’相似，B與B’相似……，按LCS算法它們是完全相同的，但對樹來說，F節點的父節點是B，F’節點是C’，它們屬于不同的樹枝，顯然這兩棵樹是不同的，在比較兩個節點相似性時還需要考慮其父親節點是否相似。

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

定義2:文本率（textRate），是指該節點的文本（不包含子節點的）與該節點內的所有文本（包含子節點的）之間的比值，它表征了該節點在以該節點為根節點的子樹中的文本含量。

定義3:內容標簽（contentTag），是指網頁中常用于顯示內容的標簽，這包括 P，SPAN，B，STRONG，H1，H2，H3，H4，H5，H6等。

定義4:內容節點（contentNode），如果一個特征節點的標簽是內容標簽，那么它是內容節點；否則如果它的文本率大于75%，那么也是內容節點。

定義5:結構節點（structureNode），所有特征節點中除了是內容節點以外的那些節點。

定義6:相似度閾值（Ts），是一個介于0到1之間的值，大于該值，認為兩個特征節點是相似的，否則是不相似的。

定義7:目標網頁內容塊候選集，指目標網頁特征樹不同于相似網頁特征樹的節點的集合。

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

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

1）初始化兩個二維數組

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

2）循環計算子問題的相似度累和以及回溯方向

從scoreTable第二行第二列開始逐行計算單元格值和pointerTable對應單元格的方向值。

其中，CompareTwoCNode是計算兩個特征節點相似性的函數，輸入為兩個節點，輸出是一個介于0～1之間的值，即相似度。CompareTwoCNode的實現方法如下:

（1）如果兩個節點標簽名不同，返回0。

（2）如果兩個節點都是BODY節點，返回1，BODY節點是一個特殊的節點，它是每棵特征樹的根節點，對于BODY節點，不管它們是否有特征不相同，都認為它們是相似的，而且相似度為1。

（3）如果一個是BODY節點，一個不是，返回0。

（4）如果兩個節點的父節點不相似，返回0。

（5）如果兩個節點都是內容節點，則比較它們的in?nerHTML，相同返回1，否則返回0，對于內容節點，在比較時要求比較苛刻，除了在特征上要求相似，還要求其在內容上相同。

（6）如果兩個節點一個是內容節點，一個是結構節點，返回0。

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

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

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

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

3）算法回溯

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

2.4 目標網頁內容塊聚集

聚集的目的是消除內容塊候選集中的祖先和子孫關系，并將在特征樹位置上比較接近的節點匯聚在一個集合里面，有利于將內容塊和孤立的噪聲塊分開，以便進行下一步的評分。在前面算法的處理中基本消除了導航欄、固定位置或固定內容的廣告，但一些頁面獨有的廣告或其他噪聲塊還是混雜在候選集里，但它們在布局上和結構上與內容信息塊是孤立的，很容易通過聚集將它們區別開來。在本文實驗中首先檢查候選集類是否有某個節點的子孫節點，有則將子孫節點從候選集中去除；然后隨機選取一個候選集中的節點，在候選集其他節點中尋找與其有相同父親節點的節點或那些爺爺節點是其父親節點的節點，將它們置于同一個集合中，繼續對剩下的節點做同樣的操作，直到候選集中所有節點都處理完畢。最后得到多個集合，被稱之為網頁內容塊聚集簇。

2.5 評分篩選

實驗的最終目的是要找出網頁中的內容塊，對網頁內容塊聚集簇中的每個集合進行特征分析并評分，找出最重要的內容塊。

定義8:主要視覺區域（mainVisualArea），是指網頁設計中常將主要內容置于靠中間的區域，這個區域是用戶打開網頁后目光集中的區域。

特征分析將從以下幾個指標入手:文本長度、面積、有效面積、內容標簽數目、鏈接率、文本代碼比率。文本長度是一個聚集簇中所有節點的內部文本長度的總和，噪聲往往文字較少，因此文本越長其越有可能是內容塊。面積是一個聚集簇中所有節點對應的網頁塊其所占區域面積的總和，占有面積越大越有可能是內容塊。有效面積是指一個聚集簇中所有節點對應的網頁塊與主要視覺區域重合的面積的總和，在網頁中的有效面積是區分內容塊和噪聲塊的一個重要指標。內容標簽數目是指一個聚集簇中包含定義3中定義的內容標簽的個數總和，顯然內容標簽數目越多，越有可能是內容塊。鏈接率是指一個聚集簇中所有節點中（包括子孫節點中的）鏈接節點的代碼長度總和與所有節點代碼長度總和的比值，這是抑制噪聲的一個重要指標，噪聲往往含有大量鏈接，通過計算這個比值，很容易區分內容塊和噪聲塊。文本代碼比率是表征文本占總HTML代碼的百分比，內容塊有較大的文本代碼比率。

在計算了上述指標之后，接下來對每個聚集簇進行評分，對于有助于尋找內容塊的指標（如文本長度），給排名靠前的聚集簇加分，對于有利于尋找噪聲塊的指標（如鏈接率），對排名靠前的減分懲罰。對于每個指標對聚集簇按從大到小排序，對前三個進行打分。對于鏈接率，按-5，-3，-1分值打分；對其他指標按5，3，1分值打分。最后每個聚集簇都有一個評分，對其進行排名，選取靠前的幾個分值比較接近的聚集簇作為最后的結果，即目標網頁的內容塊。

3 實驗結果和分析

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

表1 網頁測試集

經過對系統輸出的網頁內容塊與原目標網頁進行對比，通過人工判斷對每一個網頁比較正確性。最后計算網頁去噪正確率[9]，其計算方法為

測試結果見表2和表3，表2中按每個網站每個類別分別計算，從中可以看出對各類別都有很好的去噪效果，尤其對內容型網頁。搜狐軍事結果較差的原因是較多頁面是flash視頻播放頁面，包含文字較少，難于找出內容塊。表3是對各個網站的綜合統計結果，可以看出對不同網站都能有很好的去噪效果。

4 結論與未來展望

本文描述了一種基于LCS的特征樹最大相似性匹配的網頁去噪算法，同時具有高準確率和高覆蓋率的優點，尤其對于內容型網頁。通過分析目標網頁的鏈接找到相似網頁，再將目標網頁和相似網頁轉化為特征樹，并將特征樹映射為一個特征節點序列，利用LCS算法能獲得最長子序列全局最優解的特點，找出兩棵特征樹之間的不同節點作為目標網頁內容塊候選集，并對候選集進行聚集評分找出網頁重要內容塊。實驗表明本文的算法在正確率方面表現得很好。

表2 各網站分類表測試結果

表3 各網站總測試結果

[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].電視技術，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]劉晨曦，吳揚揚.一種基于塊分析的網頁去噪音方法[J].廣西師范大學:自然科學版，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.