基于樹先剪枝的網頁正文抽取方法研究

摘 要：本文提出了基于樹先剪枝技術和信息熵的抽取網頁正文新方法。該方法通過對網頁上的各種模板和正文進行分析，提取按照信息熵定位的正文網頁，把該正文網頁轉化成DOM樹，再刪除噪音節點，生成抽取公共路徑，抽取相關網頁。經過試驗驗證，該方法降低了搜索的復雜度，提高了搜索的準確度，提高了搜索效率。

關鍵詞：剪枝技術；信息熵；DOM樹；網頁

1 引言

許多新聞網站使用模板來自動生成新聞網頁，但是很多噪音嚴重影響網頁新聞正文的抽取，如：導航欄、廣告等等。文章把一個網頁轉化為一個簡單樹，使用簡單樹匹配算法來對網頁進行聚類分析，從而解決了大規模數據效率低下問題。本文使用信息熵來判定樣本樹的公共抽取路徑。在文獻[1]中Reis只用RTDM（Restricted Top-Down Mapping）算法來計算兩個樹之間的相似度，這個算法是基于樹編輯距離。它不但可以抽取給定網頁的相關的文本，而且可以判斷出噪音。文獻[2]使用簡單樹匹配算法來計算兩個樹之間的相似度，簡單樹匹配算法是通過計算兩個樹最大的匹配值。通過研究發現來自同一網站的網頁有很多相同之處，計算相似度沒有必要匹配兩個樹的所有節點，因此不需要使用RTDM來計算兩個樹的相似度，這篇文章對STM算法進行了修改來解決計算兩個簡單樹相似度的問題，由于這里只構建了一個包含標簽孩子節點的簡單樹，因此復雜度遠遠小于RTDM。從實驗結果來看，精確度也很理想。Reis對網頁進行聚類后，把每個類生成一個ne-pattern，這里需要比較每個類中的所有網頁，因此代價比較大。我們發現在同一個類中的網頁分享一個相同的抽取路徑，這個路徑開始于標簽。我們設計了一個高效的算法來找出每個類的抽取路徑。

文章的主要貢獻是：（1）構建了簡單樹并修改了簡單樹匹配算法。（2）使用信息熵來判定公共抽取路徑。

2 相關工作

目前有很多研究是關于如何生成模板和抽取正文。Yang.SH[3] 使用統計學、結構化和可視區域的特征來檢測模板。 Shuyi·z[4]模擬人類行為依靠模板提出了一個抽取方法。Lan·Y[5]構造了一個稱作SST（Site Style Tree）新的樹，來獲取內容和格式， 一般的噪音也可以被發現[6]。使用信息值來為每個節點賦權重。Donglin·C[7]有信息值來界定提交內容和評價內容的邊界。他使用了可視信息和有效文本來定位正文.試驗中我們發現因為空白區域和一些其它標記，有效文本的計算可能失真。Deng·C[8]， 提出 VIPS（VIsion-based Page Segmentation） 算法來抽取網頁的語義結構。這里的語義結構是一個層級結構，每個節點對應一個塊。[9]使用相同塊出現的的次數來判斷非文本區域。[10]根據標簽的開始和結束，使用堆來幫助分塊。Lin [11]對網頁進行分塊，然后構建數據向量。使用熵來判定塊是否包含信息。

3 構建簡單樹和聚類

每個網頁都可以轉化為一棵DOM樹，并且可以獲得每個節點的屬性。RTDM 算法包含了替換、刪除和插入等操作，我們認為一棵樹一旦被編輯后，樹的結構也就發生了變化，這會影響到抽取的效果。我們實驗發現來自同一網站的新聞網頁結構基本相同。比如， Yahoo 許多新聞網頁有

定義簡單樹匹配算法：

相似度的計算公式如下：

這里使用80%作為閥值。

4 判定公共抽取路徑

這部分討論如何找出公共抽取路徑。在文獻[1]中Reis通過文本長度來定位正文所在位置。這種方法有一定的局限性。為了解決這個問題，本文使用信息熵來定位正文位置。本文的假設條件如下：（1）節點區域越大，則該節點包含正文；（2）節點中包含的超鏈接越少，則該節點包含正文。因為每個類中的網頁有相似的網頁結構，因此只要找出類中任意一個頁面的抽取路徑，則該類的所有網頁都共享此抽取路徑。找出公共的抽取路徑，需要找出包含正文的節點。

公共抽取路徑的獲取步驟如下：

（1）從每個類中隨機的選取一個樣本頁；

（2）構造DOM樹，同時對樹進行先剪枝；

（3）生成公共抽取路徑；

下面來討論為什么要進行樹先剪枝，以及如何進行樹先剪枝和獲取公共抽取路徑。對網頁進行樹解析，我們會得到一個復雜的DOM樹，其中樹的節點包括：DOCTYPE html、head、body、style、script、div、span、comment、link、image、h2、ul、a、p等等。通過研究發現不會包含正文的標簽如：DOCTYPE html、head、style、script、comment、link 、image、h2、ul、a等標簽節點可以在構造DOM樹時直接刪除，這里這些節點可稱作噪音節點。而像body、div、p、span等節點則需要進行判定方可決定是否刪除。本文的判定算法如下：

輸入：高度n的所有標簽節點tag

輸出：重要節點

方法：

TW←初始化噪音節點集{DOCTYPE html，head，body，style，script，div，span，comment，link，image，h2，ul，a，p…}

for each 孩子節點 ∈ tag do

If（tag∈TW） {

delete tag；

}else if （width=0 or height=0 or text=0）{

delete tag；

}else{

計算important的方差判斷是否停止樹的構造；

}

這里返回max（ipt）的節點。使用遞歸方式可以得出一個抽取路徑。其中j表示孩子節點數。i，m表示三個屬性即：節點的height、width和text（不包含超鏈接的文本數）。經過試驗我們得出停止構造樹的閥值設置為0.1。下面從鳳凰網隨機獲取一個新聞網頁為例來判定公共抽取路徑。

（1）標簽的直接孩子如下所示：

style type=\"text/css\"

script type=\"text/javascript\"

div class=\"h_infoNav\" width= 693 height=54 text=0

div class=\"h_mainNav \" width=693 height =472 text=0

div class=\"pic1000\" width= 693 height =90 text=0

div class=\"space10\" width= 693 height =0 text=0

div class=\"focus\" width= 1265 height =501 text=86

div class=\"searchDiv02\" width=676 height=53 text=21

div class=\"main\" width=676 height =10986 text=1409

div class=\"space10\" width= 676 height =0 text=0

div class=\"links\" width= 676 height =2245 text=54

#comment

style type=\"text/css\"

div class=\"chaFotNav\" width= 676 height =529 text=0

div class=\"chaFotNav02\" width= 676 height =0 text=0

div class=\"chaFooter\" width=676 height=76 text=9

script type=\"text/javascript\"

div id=\"ifeng_da_le\" width= 1 height =1 text=0

#comment

#comment

#comment

#comment

#comment

#comment

#comment

#comment

#comment

#comment

script type=\"text/javascript\"

#comment

div id=\"ArpAdPro_iams1081\" width=0 height =0 text=0

script language=\"javascript\"

#comment

（2） 帶入上式判定算法，經過判定條件后，保留的節點如下：

div class=\"focus\" width= 1265 height =501 text=86

div class=\"searchDiv02\" width=676 height=53 text=21

div class=\"main\" width=676 height =10986 text=1409

div class=\"links\" width= 676 height =2245 text=54

div class=\"chaFooter\" width= 676 height =76 text=9

（3） 將上述結果代入重要度計算公式結果如下：

div class=\"focus\" important=0.040

div class=\"searchDiv02\" important=0.007

div class=\"main\" important=0.612

div class=\"links\" important=0.085

div class=\"chaFooter\" important=0.008

（4） 返回節點div class=\"main\"，并計算節點的方差為0.0539，小于閥值0.1；

（5） 對節點div class=\"main\"做1-4操作；

（6） 使用遞歸算法，直到節點的方差大于于閥值0.1時停止樹的剪枝與構造；

最終得出抽取路徑為：

本文在實際試驗中是從15個不同的新聞網站上隨機抓取 2000個新聞網頁作為實驗數據。試驗結果如表1所示，RTDM[1] 算法最壞情況下的復雜度O（n1， n2）。這篇文章使用了 標簽的孩子來計算相似度，所以復雜度比RTDM 小的多。同時使用公共抽取路徑代替ne-pattern。為了給每個類生成 ne-pattern。D·Reis 必須遍歷每個網頁，比較所有節點，而文章則避免了這些復雜操作。當抽取正文的時候D.Reis 使用文本長度來決定哪個是正文和標題，但是當正文和標題字數小于閥值時，這種方法就不合適了。這文章使用信息熵來計算節點的重要度。我們的算法和RTDM[1]算法做了比較：如表2所示。

5 結束語

文章介紹了一種抽取網頁新聞正文的新方法，本方法通過信息熵確定網頁類，隨機抽取一個樣本頁，構建DOM樹，使用先剪枝方法生成抽取路徑，進行網頁正文的抽取。同時，該方法刪除了噪聲節點，降低了搜索的復雜度，提高抽取效率。經過對15個網站進行正文抽取試驗，準確率達到94%以上。與RDTM方法相比，抽取準確率得到了很大幅度的提高。然而我們的算法是基于結構化網頁，對于非結構化網頁可能會出現過多的聚類，效率變低下，因此我們會在接下來的工作中解決這個問題。

參考文獻

[1]D·Reis， P·Golgher， A·Silva， etal， \"Automatic Web News Extraction Using Tree Edit Distance\"，2004，5：17-22.

[2]W·Yang，Identifying Syntactic Differences Between Two Programs[J].Software - Practice and Experience，1991，21（7）：739-755.

[3]Yong·SH， Liu·HL， Hon·YB.Automatic Data Extraction from Template -Generated Web pages. Journal of Software.2007，2（19）：209-223.

[4]Shuyi·Z，Ruihua·S，Ji-Rong·W.Template-Independent News Extraction Based on visual Consistency[J]. American Association for Artifical Intelligence， 2007.

[5]Lan·Y，Bing·L，Xiaoli·L.Eliminating Noisy Information in Web Pages for Data Mining[Z].ACM 1-58113-737-0/03/008，2003.

[6]Yeongjung·k，Jeahyun·P，Teehuan·K，etal.Web Information Extraction By Html Tree Edit Distance Matching\". DOI10.1109/ICCIT，2007.

[7]DongLin·C，Xiangwen·L，Hongbo·X，etal.Blog Post and Comment Extraction Using Information Quantity of Web Format\". AIRS LNCS 4993，2008：298-309.

[8]Deng C， Shipeng Y， Ji-Rong W and Wei-Ying M. VIPS： \"a Vision-based Page Segmentation Algorithm Microsoft Research Microsoft Corporation One Microsoft Way Redmond\"， WA 98052 ，2003.

[9]Sandip.D， Prasenjit Mitra， C.Lee G \"Automatic Extraction of Informative Blocks from Webpages\" ，ACM 1-58113-964-0/05/0003 ，2005.

[10]Jiangtao. Q， Changjie. T， Kaikuo.X， Qian.L \"Web Contents Extracting for Web- Learning\" ， Springer，2008 ， pp.59-68.

[11]Lin，S·H，Ho，J·M.Discovering Informative Content Bolcks from Web Documents[J].Proceedings of ACM SIGKDD， 2002.