基于XML的網(wǎng)頁信息提取系統(tǒng)的研究與設計

摘要:該文提出了一種面向由XML描述的Web文檔的基于用戶主題信息的模式和數(shù)據(jù)抽取方法，它利用學習算法從樣本文檔中提取規(guī)則，然后使用匹配算法從目標文檔中抽取出數(shù)據(jù)。該文使用一種改進的解析方法對XML文檔進行解析，在模式抽取時使用了順序覆蓋算法從樣本XML文檔集中訓練出模式。在數(shù)據(jù)抽取算法中，數(shù)據(jù)抽取算法從解析后的XML文檔樹中尋找用戶所需的信息，它可以高效、準確地找到用戶所需數(shù)據(jù)。

關鍵詞:XML;數(shù)據(jù)抽取;文檔解析

中圖分類號:TP391文獻標識碼:A文章編號:1009-3044(2009)26-7327-03

Study and Design of Network Page Information Extraction System Based on XML

YANG Cheng

(Shanghai Jiaotong University， Shanghai 200240， China)

Abstract: In this paper， a kind of model and data extraction method based on user theme-oriented information facing Web document described by XML was brought forward， it extracted the rule from the sample document using learning algorithm， then extracted data from the target document using matching algorithm. In this paper， an improved resolution method was used to resolve XML document， at mode extraction the sequence covering algorithm was used to train out mode from sample XML document collections. In data extraction algorithm， data extraction algorithm search for information required by user from resolved xml document tree， it could find the data required by user with high efficacy and accurately.

Key words: XML; data extract; document parase

XML是WWW上信息交換的新標準，它支持用戶自定義文檔標一記，用有序的、嵌套的元素組織成有一定結構的數(shù)

據(jù)，是面向數(shù)據(jù)的，程序可讀解這些標記并依據(jù)標一記的語義處理數(shù)據(jù)。雖然目前由于HTML簡單易用和表現(xiàn)力強等特點，在Web上仍然占據(jù)主流，但是以XML文檔為主體的WWW將成為新一代以數(shù)據(jù)為中心的WWW計算環(huán)境。本文研究了從XML描述的特定主題的Web文檔中抽取模式和數(shù)據(jù)的方法。

1 體系結構

本系統(tǒng)以XML網(wǎng)頁為研究對象，根據(jù)用戶的主題信息從樣本XML文檔中抽取出模式信息，然后根據(jù)模式信息從目標XML文檔中抽取出數(shù)據(jù)。整個抽取系統(tǒng)由兩部分組成，如圖1所示。

模式抽取部分:它包括一個XML分析器和一個模式抽取器。XML分析器用來解析樣本文檔，模式抽取器從解析后的

樣本文檔集中根據(jù)主題信息抽取出關于該類主題文檔的一般模式信息;

數(shù)據(jù)抽取部分:由一個數(shù)據(jù)抽取器組成，它根據(jù)已得到的模式信息從大量目標文檔中抽取出符合用戶需求的數(shù)據(jù)。

本系統(tǒng)的研究基于如下假設:每一個所生成的模式只針對某Web數(shù)據(jù)源中的一類XML頁面，每個目標XML文檔上應該有用戶感興趣的數(shù)據(jù)區(qū)域，且每個文檔上的對應區(qū)域具有基本的相同的結構，為每一個主題服務。

2 模式抽取

2.1 解析樣本XML文檔

關于XML解析技術，目前的爭論非常之多，與許多其它技術問題一樣，XML文檔的處理需求有著很大的區(qū)別，不同的技術實現(xiàn)方案會適合不同的問題域。

基于樹結構的XML解析技術是將結構完整的XML文檔定義為一棵樹，樹是廣泛應用的一種數(shù)據(jù)結構，將XML文檔解析成樹結構以后，許多成熟的算法都可以用來遍歷、搜索、編輯XML文檔樹。

基于事件驅(qū)動的解析技術主要是圍繞著事件源以及事件處理器來工作的。當事件源產(chǎn)生事件后，驅(qū)動事件處理器相應的處理方法，一個事件就獲得了處理。當然在事件源調(diào)用事件處理器中特定方法的時候，會傳遞給事件處理器相應事件的狀態(tài)信息，這樣事件處理器才能夠根據(jù)事件信息來決定自己的行為。這種方式需要的內(nèi)存小，運行速度快。

本文使用的是Java中包JAXP帶有的XML解析方法，它是基于SAX接口的，在這里對它的輸出方式作了一點修改，解析后的XML文檔每一條路徑都是一個用字符串表示的標簽集，不同標簽用”.”分割，并且上一個標簽是下一個標簽的父節(jié)點，路徑結束標志是#pcdata[0]，它后面就是這條路徑的葉子節(jié)點，即具體的數(shù)據(jù)值或?qū)傩灾怠１硎境蛇@種結構而不是真正樹結構的優(yōu)點是它具有節(jié)約空間，產(chǎn)生較少麻煩的GUI以及方便以后的模式抽取及數(shù)據(jù)抽取等優(yōu)點。

2.2 樣本集模式的抽取方法

2.2.1 主題信息

主題信息是由用戶給出的，它表明了用戶的需求，用戶可以通過系統(tǒng)界面來和系統(tǒng)進行交互，主題是一個topic，它可以包含許多屬性，為了抽取過程中盡可能地不遺漏信息，可以通過一個網(wǎng)上詞庫WordNet來查找主題詞的同義詞和近義詞因為關于中文的網(wǎng)上詞典大全還沒有，故而在用戶定義的主題詞及其屬性是都要用英文描述。

具體實現(xiàn)是用一個類UserElemets來描述用戶主題信息，把主題詞及其屬性包括經(jīng)WordNet查詢后得出的它們的同義詞，近義詞等信息都存放在類UserElemets中，每一個主題信息都是這個類的一個對象。

2.2.2 單個樣本頁的描述接口

對于根據(jù)用戶給出的主題信息隨機選取樣本網(wǎng)頁，每個樣本頁面都具有包含用戶感興趣的數(shù)據(jù)區(qū)域(即與用戶給出的主題信息相符合的信息)，稱這樣的區(qū)域為UID，所謂“樣本頁描述接口”實際上是對樣本頁中所包含的UID的一種結構化描述，是對樣本頁的一種標記行為，單個網(wǎng)頁描述接口的構造就是從這個樣本網(wǎng)頁中根據(jù)主題信息找出這樣的UID，它包括路徑以及相關的數(shù)據(jù)項信息，這樣把樣本網(wǎng)頁中要提取的主題信息按照UID分組，得出每一個分組路徑，以及這條路徑所包含的有用信滬息。標一記為:

UID;{TopicInfor;UIDPATH;}，(i=1，…，n)

n是所得到的UID;數(shù)量;

TopicInfor是這個UID;所包含的主題信息，它的一般方式為:

DataTapeValueFrequency

其中DataType表示該樣本頁中出現(xiàn)的主題信息的數(shù)據(jù)類型;Value表示該主題信息在樣本頁中的具體值，它可以是主題值及其屬性值，也可以是他們的近義詞或同義詞;Frequency表示該主題信息出現(xiàn)的次數(shù)。UIDPATHi表示統(tǒng)計出的該UID在樣本頁中出現(xiàn)的路徑信息。

樣本頁的描述接口(DI)獲取算法如下:

輸入:用戶給出的土題信息，解析后的樣本網(wǎng)頁d，的解析樹;

輸出:d，中的用戶興趣模式UID;{

Topiclnfor=1;

UIDPATHi =1:

先序遍歷解析樹;

while(遍歷未結束){

if(解析樹中某一個區(qū)域與UseElements相符){

Topiclnfor.DataType= DateTypeOf(ParseTree.Node[j]);

TopiclnforNalue=ContentOf(ParseTree.Node[j]);

Frequency++;

抽取出這個區(qū)域路徑表達式UIDPATH j;

if(該土題信息已出現(xiàn)過)

{從該UID中讀出其原有的UIDPATH;

UIDPATHi=UIDPATH 1+UIDPATHj;}

Else{

UIDPATHi=UIDPATHj:i++;

}}}

算法I樣本頁描述接口獲取算法

2.2.3 樣本網(wǎng)頁集的模式抽取

本文提出的抽取算法屬于歸納學習的范疇，它表示從例子設想出假設的過程，本系統(tǒng)中的Pattern Extractor實際上包括兩部分功能，一個就是生成訓練集合，它實際上由上節(jié)中UID中的UIDPATH;組成，而不包括TopicInfor，這樣做的原因是對于單一的TopicInfor來說不可能指定標識符來幫助對其定位，結構相似性比較對于數(shù)量大大超過UID的TopicInfor來說又難以達到理想的效果，所以對主題信息的析取也就失去了意義，所以對TopicInfo的沒有采用學習算法確定抽取規(guī);另一個功能就是根據(jù)訓練集合學習出抽取規(guī)則，然后結合主題信息，得到樣本網(wǎng)頁集的模式信息。

設隨機提取n個樣本頁，每個樣本頁按上一節(jié)算法標記出m個UID，樣本頁中的對應UID的路徑表達式組成的集合命名為UIDPATH; ( i=1，2， …，m)，則一個訓練集合表示如下:

UIDPATHi={UIDpath1i，UIDpath2i，，UIDpathni}

其中UIDPATHni表示第n個樣本頁的第i個UID.則所研究的問題域當中存在m個訓練集合。

抽取出的模式是一個二元組，表示為ExtractPatterns{ExtractRules，PatternTopicInfor}，在具體應用時被表達成UID主題信息分開的兩段式結構，而且UID的提取是在樣本路徑表達式的訓練集合上學習得到的，而主題信息的獲得只是通過得到的UIDPATH查找樣本描述接口中的TopicInfor得到的。

模式抽取算法PEA(Pattern Extraction Algorithm)由兩部分組成:第一部分是對樣本集的UIDPATH規(guī)則抽取，它是一個典型的順序覆蓋算法，算法的核心部分是學習出抽取規(guī)則，算法首先產(chǎn)生一個假設去覆蓋盡可能多的集合中的正例，然后從集合中刪除被覆蓋的正例，再在剩余元素的基礎上產(chǎn)生另一個假設去覆蓋盡可能多的集合中的正例，如此循環(huán)直至所有的元素被覆蓋，最后算法返回假設的析取作為最后的抽取規(guī)則;第二部分是根據(jù)提取的UIDPATH規(guī)則，找出相應的TopicInfo，最終形成完整的模式信息。PEA算法如下所示:

輸入:n個樣本文檔的的描述接口DI;

每個DI中包含的m個UID;

輸出:抽取模式ExtractPatterns( ExtractRules， PatternTopicInforl;

{ExtractRules=1;

PatternTopicInfor =1;

for i=1 to m

for j=1 to n

{UIDPATHi=UIDPATHi+{UIDpathji};

for i=1 to m

{ while(UIDPATHi!=1)

{aRule = LearnOnerule(UIDPATH;)

UIDPATHi=UIDPATHi=UIDpathes;

ExtractRulei=ExtractRulei+{aRule};

if(Extract Rule，c UID.UIDPATH)

PatternTopicInfor.=UID.Topiclnfor;

} }

returnExtractKules=ExtractKule1+…+ExtractRule=;

returnVatterniopicInfor=PatternLopicInfor1+…+PatternTopicInform

算法2模式抽取算法

2.2.4 抽取模式的近一步的處理

抽取模式的生成并不是問題的結束，的目的是用得到的抽取模式去抽取樣本頁以外的其它Web頁。這里將得到的抽取模式以文本文件的形式輸出到用戶界面，用戶可以對生成的模式進行編輯以加入新的抽取需求。借鑒Perl語言中的正則表達式語法，引入提取子項操作和分隔操作來支持對更小的粒度進行的數(shù)據(jù)提取.提取子項操作的一般形式為subItem(leftchar，rightchar)，其中的字符參數(shù)可以省略其一，當省略leftchar字符的時候，表示只提取數(shù)據(jù)項中rightchar字符左邊的數(shù)據(jù);當省略rightchar字符的時候，則剛好相反;當兩個字符都不省略的時候，表示提取它們之間的數(shù)據(jù)的字符。

2.3 特殊和異常處理

由于Web頁中數(shù)據(jù)類型復雜，特別是關于數(shù)值日期的表示不規(guī)范，因此在抽取時候字段屬性多為字符串，抽取主題信息時要對這些進行規(guī)范化。

3 數(shù)據(jù)抽取

3.1 目標文檔的預處理

在使用得到的抽取模式對目標文檔進行數(shù)據(jù)抽取時，假設目標文檔已經(jīng)存在，而且與樣本文檔結構類似，屬于同類網(wǎng)頁。

首先對目標文檔進行了預處理，也就是使用的XML分析器對目標XML文檔進行解析。

3.2 數(shù)據(jù)抽取算法

數(shù)據(jù)抽取算法以從樣本XML文檔中抽取出的模式信息和解析之后的目標XML文檔為輸入，對解析后的文檔輸出與抽取出的模式進行模式匹配，這里采用結構匹配算法，若相匹配則抽取出目標文檔中相關信息，提交給用戶。數(shù)據(jù)抽取算法如下(見下頁所示):

輸入:解析后的目標網(wǎng)頁TargetElements;

抽取出的模式ExtractPatterns;

輸出:目標文檔中符合用戶土題的信息;

{ fori=1 to TargetElemets.size

{從TargetElements讀入目標文檔解析樹中的一條路徑L1和這條路徑所含的數(shù)據(jù)信息DataInfo;

if(match(ExtractPatterns，L1，DataInfo))

輸出這個L1及DataInfo;

i++;

}}

算法3數(shù)據(jù)抽取算法

4 信息抽取示例

在實際應用中，一般選擇小樣本(<5)來生成模式，這樣可以降低復雜程度。通過實驗，認為系統(tǒng)在對樣本文檔進行模式信息抽取過程中，操作簡單，比較容易生成包裹器，在數(shù)據(jù)信息抽取過程中，如果目標文檔與樣本文檔結構類似，且比較規(guī)則時，抽取的成功率較高。

參考文獻:

[1] 王建麗，丁振國.一種基于XML的Web數(shù)據(jù)挖掘技術[J].西安科技學院學報，2002，22(2):337-340.

[2] 王繼成，潘金貴，張福炎.Web文本挖掘技術研究[J].計算機研究與發(fā)展，2000(5):85-87.

[3] 王繼成，鄒濤.基于Internet的信息資源發(fā)現(xiàn)挖掘技術與實現(xiàn)[J].計算機研究與發(fā)展，1999(11):1369-1374.

[4] 徐振航，劉莉芹.基于XML的Web數(shù)據(jù)挖掘技術[J].計算機系統(tǒng)應用，2001(1):39-42.

[5] 劉芳，胡和平.半結構化數(shù)據(jù)的模式發(fā)現(xiàn)[J].微型機與應用，2000(6):13-15.

[6] 姚天順，張俐，高竹. WordNet綜述[J].語言文字應用，2001(3):27-32.