基于樹比較的Web頁面主題信息抽取＊

朱夢麟，李光耀，周毅敏

(同濟大學 電子與信息工程學院，上海 201804)

隨著Internet的飛速發(fā)展，Web已經(jīng)發(fā)展成為一個共享的數(shù)據(jù)空間，互聯(lián)網(wǎng)已成為人們獲取信息的重要渠道。而在Web數(shù)據(jù)呈幾何級數(shù)增長的同時，用戶查找、定位自己所需的信息變得越來越困難，如何快捷、有效地搜索信息成為亟待解決的問題，Web信息抽取技術正是在這種背景下應運而生。Web信息抽取技術的核心是能夠從頁面所包含的無結構或半結構的信息中識別用戶感興趣的數(shù)據(jù)，使其更為結構化、語義更為清晰的格式。比如從新聞報道中抽取出新聞的時間、地點、主要內(nèi)容等；從介紹商品的網(wǎng)站上抽取出商品的價格、參數(shù)、評價等。通常，被抽取出來的信息以結構化的形式描述，可以直接存入數(shù)據(jù)庫中，供用戶查詢以及進一步分析利用。當今，Internet已經(jīng)成為發(fā)布和傳播信息的最重要手段，網(wǎng)絡上的信息和活動對人們的影響越來越明顯。一個良好的Web信息抽取系統(tǒng)可以高效地收集所需的網(wǎng)絡信息，并加以分析利用，如應用于專業(yè)數(shù)據(jù)獲取、股票預測、用戶行為愛好分析等。目前，像 Newsbot、Shopbot等一些針對特定領域的信息抽取/集成軟件已經(jīng)投入了商業(yè)應用，幫助人們隨時獲得最新的新聞消息或收集同一商品的不同價格信息以決定合理的購買方式。

Web的數(shù)據(jù)大部分都是以HTML形式出現(xiàn)的，這是一種半結構化的數(shù)據(jù)，缺乏對數(shù)據(jù)本身的描述，不含清晰的語義信息，模式也不太明確，這使得應用程序無法直接解析并利用頁面上的信息；并且由于人們審美和商業(yè)的需求，充斥著大量與主題無關的修飾信息，如圖片、廣告、各種腳本語言等。如何排除干擾，有效地確定Web頁面中的主要數(shù)據(jù)區(qū)域并從中抽取出大家所關注的主題信息是本文的主要工作。

Web信息抽取技術發(fā)展至今，已經(jīng)有了很多比較成熟的方法，如基于文本統(tǒng)計的信息抽取技術[1]、基于HTML結構的信息抽取技術[2]、基于隱馬爾科夫模型的信息抽取技術[3]等。這些方法各有利弊，但有一個需要共同面對的問題是對于目標頁面的不定期改版，原有的抽取規(guī)則可能會失效。本文提出的基于樹比較的Web主題信息抽取技術是一種基于HTML結構的信息抽取方法。通過目標頁面與其相似頁面的比較訓練，簡化目標頁面并生成抽取規(guī)則，以此規(guī)則來完成目標頁面主題信息的抽取。當頁面改版，抽取規(guī)則失效時，會自動進行重新學習而生成新的抽取規(guī)則。經(jīng)驗證，本抽取系統(tǒng)具有良好的健壯性，能很好地解決這個問題。

1 相關概念

1.1 DOM樹

DOM(Document Object Model)是由W3C制定的一種與平臺和語言無關的標準接口規(guī)范，它允許程序和腳本動態(tài)訪問、修改文檔的內(nèi)容、結構和類型。它定義了一系列的對象和方法對DOM樹的節(jié)點進行各種隨機操作。DOM樹中的節(jié)點可分為4種不同的對象：(1)Document對象。作為樹的最高節(jié)點，Document對象是對整個文檔進行操作的入口；(2)Element和Attr對象。這些節(jié)點對象都是文檔某一部分的映射，節(jié)點的定級層次恰好反映了文檔的結構；(3)Text對象。作為Element和Attr對象的子節(jié)點，Text對象表達了元素或?qū)傩缘奈谋緝?nèi)容。Text節(jié)點不再包含任何子節(jié)點；(4)集合索引。DOM提供了幾種集合索引方式，可以對節(jié)點按指定方式進行遍歷，索引參數(shù)都是從0開始記數(shù)的。DOM樹中的所有節(jié)點都是從Node對象繼承而來，Node對象定義了一些最基本的屬性和方法，利用這些方法可以實現(xiàn)對樹的遍歷，同時，根據(jù)屬性還可以得知節(jié)點的名稱、取值并判斷其類型。

1.2 XPath

XPath即為 XML路徑語言 (XML Path Language)，它是一種用來確定XML文檔中某部分位置的語言。XPath基于XML的樹狀結構，提供在數(shù)據(jù)結構樹中找尋節(jié)點的能力。最常見的XPath表達式是路徑表達式(XPath名稱的另一來源)。路徑表達式是從一個XML節(jié)點(當前的上下文節(jié)點)到另一個節(jié)點、或一組節(jié)點的書面步驟順序。這些步驟以“／”字符分開，每一步有三個成分：軸描述(用最直接的方式接近目標節(jié)點)；節(jié)點測試(用于篩選節(jié)點位置和名稱)；節(jié)點描述(用于篩選節(jié)點的屬性和子節(jié)點特征)。本文的抽取規(guī)則就是以XPath的形式給出，使用XPath定位所要抽取的信息在DOM樹中的節(jié)點。

用Xpath來定義抽取規(guī)則，雖然簡單明確，但從抽取系統(tǒng)的健壯性來考慮，卻存在著一定的隱患。假設要從圖1這樣一棵DOM樹上抽取商品iPhone4的價格，則可以定義XPath/html/body/div[2]/table/td[2]/text()為抽取規(guī)則。但是，當目標頁面的布局稍有改變時，該抽取規(guī)則可能就不再適用，而需要重新訓練學習[4]。比如，第一個div被刪除，第二個div的table下新加了一些節(jié)點等。本文提出的信息抽取算法在當前的抽取規(guī)則失效后，會自動獲取改版后的頁面重新進行再學習、訓練以生成新的抽取規(guī)則，確保了信息抽取系統(tǒng)的有效性。

1.3 DSE算法

對于Web主題信息抽取來說，很重要的一步就是簡化待抽取的Web頁面，確定主題信息所在的數(shù)據(jù)區(qū)域，刪減與主題無關的干擾信息。DSE[5](Data-rich Section Extraction)算法能很有效地完成這個工作。DSE的提出是基于這樣一個事實：在同一個網(wǎng)站下，往往有大量使用同一設計模板的Web頁面，這些頁面具有相同或相似的HTML結構。同時，廣告、導航信息等與主題無關的內(nèi)容在這些頁面的相同位置不斷重復出現(xiàn)。這時，通過對由這些頁面構建的DOM樹進行兩兩比較，就可以盡可能地排除這些干擾信息，縮小下一步處理的數(shù)據(jù)集合，提高信息抽取的效率和精度。DSE算法的基本過程如下：

圖1 一個Web頁面的DOM樹

(1)深度優(yōu)先遍歷兩棵待比較的樹A、B。其中樹A、B是由兩個相似的Web頁面構建所得。

(2)在遍歷的同時，不斷比較兩棵樹上相同位置的兩個節(jié)點，對于相同的兩個內(nèi)部節(jié)點，則繼續(xù)比較它們的子節(jié)點。對于葉子節(jié)點，如果比較結果相同，則把它們從該樹上刪除；如果不同，則繼續(xù)比較下一個葉子節(jié)點。只有當一個節(jié)點的所有子節(jié)點都被刪除后，才會刪除該節(jié)點。

(3)當遍歷整棵樹后，樹 A、B中重復出現(xiàn)的與主題無關節(jié)點均已被刪除。

圖2顯示了一個簡單的DSE算法的DOM樹比較過程。可以看到，樹A經(jīng)一次DSE算法比較后，一部分與主題信息無關的重復內(nèi)容已被刪除，頁面A對應的DOM樹已得到了很大程度的簡化。

圖2 簡單的DSE算法例子[5]

2 抽取算法及實現(xiàn)

2.1 抽取算法

本文進行的信息抽取算法具體步驟如下：

(1)構建目標頁面的DOM樹。由網(wǎng)上獲得的目標頁面的HTML源文件并構建其對應的DOM樹。

(2)獲取目標頁面的幾個相似頁面。可利用正則表達式匹配等方法判斷是否屬于目標頁面的相似頁面。

(3)用DSE算法對目標頁面與其相似頁面進行比較匹配，簡化待抽取的目標頁面，具體的比較次數(shù)需要看頁面的復雜程度，一般為1～3次。只有盡可能地簡化目標頁面的DOM樹，縮小下一步處理的數(shù)據(jù)集合，才能有效提高抽取算法的速度和效率。

(4)在簡化后的DOM樹上進行遍歷，尋找信息量最大的節(jié)點，并生成從根到該節(jié)點的XPath。

(5)由XPath生成抽取規(guī)則和模板，并儲存相關模板信息，用于今后該類頁面的信息抽取。

(6)用生成的規(guī)則完成信息抽取，并把數(shù)據(jù)保存到數(shù)據(jù)庫中。

2.2 系統(tǒng)的實現(xiàn)

如圖3所示，根據(jù)設計目標，將系統(tǒng)分為以下模塊：

(1)頁面瀏覽模塊：實現(xiàn)用戶對Web頁面的瀏覽和標記功能。用戶可以在內(nèi)置的瀏覽器中訪問該頁面，也可以在頁面中進行標記。同時，在界面上方構建生成的DOM樹中，也可以對各節(jié)點進行選擇查看和標記。

(2)相似頁面獲得模塊：獲得與目標頁面模板相同、結構一致的頁面，用于后續(xù)的抽取規(guī)則訓練算法。

(3)抽取規(guī)則生成模塊：用DSE算法進行相似頁面的比較訓練，尋找待抽取信息所在的節(jié)點，生成XPath，形成抽取規(guī)則。

(4)信息抽取模塊：由抽取規(guī)則進行抽取，顯示結果，并存入數(shù)據(jù)庫。

圖3 系統(tǒng)功能模塊圖

本信息抽取系統(tǒng)具體實現(xiàn)使用Java編程，以Java Swing制作界面。運行程序后，可以輸入任意網(wǎng)址打開頁面，并生成該頁面的DOM樹于界面左上方。比如，輸入http：//www.sina.com.cn后，信息系統(tǒng)抽取主界面如圖4所示。

2.3 實驗結果及分析

為了驗證本算法的有效性，運用本系統(tǒng)對新浪、搜狐等網(wǎng)站的近千個新聞頁面進行了試抽取，并人工檢驗了抽取的有效性。實驗結果表明，大約98.2%的頁面都能正確抽取頁面的主題信息，只有極少數(shù)的頁面抽取失敗或無法抽取。可見，本抽取算法具有一定的推廣應用價值。

圖4 Web信息抽取系統(tǒng)主界面圖

本文提出了一種基于樹比較的Web頁面主題信息抽取算法，該算法能快速、準確、有效地抽取目標頁面的主題信息。如何將該算法更好地應用于信息檢索、數(shù)據(jù)挖掘的各方面是今后的主要工作。如應用于搜索引擎的搜索算法中，提高搜索引擎的檢索速度和精度；或?qū)σ勋@得的頁面信息進行進一步的數(shù)據(jù)挖掘，以發(fā)現(xiàn)其中有用的信息和知識。

[1]孫承杰，關毅.基于統(tǒng)計的網(wǎng)頁正文信息抽取方法的研究[J].中文信息學報，2004，18(5)：17-22.

[2]張彥超，劉云，李勇，等.基于自動生成模板的 Web信息抽取技術[J].北京交通大學學報，2009，33(5)：40-45.

[3]祝偉華，盧熠，劉斌斌.基于 HMM的 Web信息抽取算法的研究與應用[J].計算機科學，2010，37(2)：203-206.

[4]DALVI N， BOHANNON P， SHA F.An approach based on a probabilistic tree-Edit model[A].Proceedings of the 35th SIGMOD International Conference on Management of Data(SIGMOD’09)[C].New York：ACM Press，2009：335-348.

[5]Wang Jiying， FRED H.LOCHOVSKY.Data-rich section extraction from HTML pages[A].Proc 3rd International Conference on Web Information System Engineering(WISE’02)[C].Singapore：IEEE Computer Society Press，2002：1-10.