一種基于DOM的Web信息提取方法
鄧超1 熊選東2
(解放軍信息工程大學(xué)電子技術(shù)學(xué)院研究所,,鄭州 450004)
摘 要 文章提出一種基于DOM的Web信息提取方法,通過歸納學(xué)習(xí)獲得被提取信息的定位路徑,,利用XPath和XSLT在數(shù)據(jù)定位和數(shù)據(jù)轉(zhuǎn)換方面的特點(diǎn)編寫提取模式,,根據(jù)網(wǎng)頁元素與DOM節(jié)點(diǎn)對(duì)應(yīng)關(guān)系,判斷所獲得信息源是否適用于已有提取模式,。
關(guān)鍵詞 Web信息提?。籇OM,;XPath,;XSLT;基于DOM的網(wǎng)頁結(jié)構(gòu)判斷
1 引言
Web信息的爆炸性增長,,給我們帶來了獲取更多信息的機(jī)會(huì),,同時(shí),,也增加了在紛繁復(fù)雜的Web信息庫中準(zhǔn)確地獲取信息的困難,。例如,,使用搜索引擎搜
索信息時(shí),返回信息成千上萬,,其中包含大量無用甚至是錯(cuò)誤的信息,,進(jìn)行人工挑選要耗費(fèi)時(shí)間和精力。另外,,由于網(wǎng)頁的編寫方式,,編寫風(fēng)格各種各樣,使得所搜集的信息也不適于結(jié)構(gòu)化存儲(chǔ),。本文提出了一種基于DOM[1]的Web信息提取方法,,利用DOM提取信息,并進(jìn)行相關(guān)信息源的搜索,,實(shí)現(xiàn)信息的精確定位,。
2 基本思想
本文的基本思想是:將不夠規(guī)范的HTML文檔整理成格式良好的XHTML[2]文檔,再將XHTML文檔解析成一個(gè)樹模型——DOM樹,,然后圍繞DOM樹進(jìn)行信息的提取以及相似結(jié)構(gòu)網(wǎng)頁的搜索,,提取的結(jié)果以XML文檔表示,并進(jìn)行結(jié)構(gòu)化存儲(chǔ),。如圖1所示:
圖1 設(shè)計(jì)思想
以下是對(duì)各個(gè)處理步驟的分析說明:
2.1 整理
HTML用一對(duì)預(yù)定義的標(biāo)記來描述包含在其間文本的表現(xiàn)方式,,要求標(biāo)記成對(duì)出現(xiàn)。事實(shí)上,,有許多HTML文檔中的標(biāo)記不符合HTML語法要求,,比如缺乏結(jié)束標(biāo)記等。這些錯(cuò)誤影響對(duì)HTML文檔的正確解析,因此,,為便于解析,,首先要對(duì)HTML文檔進(jìn)行整理,將其轉(zhuǎn)換成XHTML文檔,,XHTML嚴(yán)格建立在XML基礎(chǔ)之上,并且明確定義了格式良好的文檔規(guī)則,。這樣就可以像對(duì)待一般XML文檔一樣對(duì)待XHTML文檔,,可以利用各種XML標(biāo)準(zhǔn)技術(shù)來操縱XHTML文檔。
對(duì)HTML文檔的整理主要是以下三個(gè)方面:
(1)為不成對(duì)的標(biāo)記加上結(jié)束符“/”,,例如<br>加上結(jié)束符為<br />,;
(2)為所有屬性值加上引號(hào),例如,,<a href=http://www.>加上引號(hào)變?yōu)?lt;a href=”http://www.”>,;
(3)將URL中所有的“\”換成“/”。
2.2 解析
解析,,就是將經(jīng)過轉(zhuǎn)換得到的XHTML文檔構(gòu)造成DOM樹,,將文檔中的元素映射成DOM樹中的節(jié)點(diǎn)。
DOM全稱是文檔對(duì)象模型(Document Object Model, DOM),,它根據(jù)文檔中標(biāo)記之間的嵌套關(guān)系,,將文檔表示為一個(gè)樹形結(jié)構(gòu),文檔中的元素,、屬性,、以分析的字符數(shù)據(jù)、注釋以及處理指令等都是節(jié)點(diǎn),。Document是文檔根,,是操作整個(gè)DOM樹的句柄。
DOM樹是面向?qū)ο蟮奈臋n模型,,樹中的節(jié)點(diǎn)都是接口,,它們派生于Node接口,每個(gè)節(jié)點(diǎn)都有各自的特性和操作,,處理節(jié)點(diǎn)比較方便,。
當(dāng)解析生成DOM樹之后,對(duì)HTML文檔中信息的提取,,就轉(zhuǎn)換成為對(duì)DOM樹中相應(yīng)節(jié)點(diǎn)的查找,,節(jié)點(diǎn)位置由定位規(guī)則指出,提取模式中的模板按照定位規(guī)則的指示提取出相應(yīng)位置的信息,。
解析的處理過程如下,,首先找出網(wǎng)頁中所有的開始標(biāo)記,將其名稱存入標(biāo)記表。接著逐次找出網(wǎng)頁中每個(gè)標(biāo)記,,并檢查其是不是一個(gè)有開始標(biāo)記與其對(duì)應(yīng)的結(jié)束標(biāo)記或者是注釋標(biāo)記,,如果是沒有對(duì)應(yīng)開始標(biāo)記的結(jié)束標(biāo)記或者是注釋標(biāo)記,就刪除該標(biāo)記,;否則,,如果是有對(duì)應(yīng)開始標(biāo)記的結(jié)束標(biāo)記,就將這個(gè)結(jié)束標(biāo)記與其開始標(biāo)記之間的內(nèi)容存儲(chǔ)到標(biāo)記表中,,這個(gè)內(nèi)容就是葉節(jié)點(diǎn),,重復(fù)操作,直到網(wǎng)頁中每個(gè)標(biāo)記都處理完之后,,就建立了一個(gè)由標(biāo)記及其所包含內(nèi)容構(gòu)成的表,,整棵樹被分解成n棵子樹存入表中。然后,,將<html>標(biāo)記設(shè)置為根節(jié)點(diǎn),,將表中n棵子樹順次添加到根節(jié)點(diǎn)下,形成一棵n叉樹,。
2.3 信息提取
提取信息分兩步,,現(xiàn)生成提取模式,然后利用提取模式提取信息,。
2.3.1 提取模式生成
生成提取模式分三個(gè)步驟,,歸納單個(gè)樣本網(wǎng)頁信息塊定位路徑,歸納樣本網(wǎng)頁集合信息塊定位路徑,,定位信息塊內(nèi)信息點(diǎn)路徑,。
(1) 歸納單個(gè)樣本網(wǎng)頁信息塊定位路徑
根據(jù)用戶提供的樣本網(wǎng)頁的結(jié)構(gòu)特點(diǎn),將樣本網(wǎng)頁按相似結(jié)構(gòu)分塊,,本文所感興趣的信息就位于這些相似結(jié)構(gòu)的信息塊中,,這也是本文學(xué)習(xí)提取算法的一個(gè)限制條件,即,,被提取信息點(diǎn)位于結(jié)構(gòu)相似的信息塊內(nèi),,各信息點(diǎn)之間沒有其他信息。
單個(gè)樣本學(xué)習(xí)算法如下:
IBPATHi=NULL,;
先序遍歷解析樹DOMi,;
得到的路徑表達(dá)式記入treePath;
依次掃描treePath,;
while(treePath未結(jié)束){
比較兩條路徑中的相應(yīng)路徑結(jié)點(diǎn),;
if(兩路徑結(jié)點(diǎn)的索引值和孩子結(jié)點(diǎn)的索引值相同){
將該路徑寫入IBPATHi;
比較下一組路徑表達(dá)式,;
}
else(結(jié)點(diǎn)的索引值相同,,而孩子結(jié)點(diǎn)的索引值不同){
截取該路徑表達(dá)式中該節(jié)點(diǎn)及該節(jié)點(diǎn)之前的路徑,將該路徑寫入IBPATHi;
進(jìn)入下一組路徑比較,;
}
}
return IBPATHi,;
(2) 歸納樣本網(wǎng)頁集合信息塊定位路徑
算法描述如下:
LocationIBs=null;
for(i=1,;i<=m,;i++){
Path[i]=null;
LocationIB[i]=null,;
}
for(i=1,;i<=m;i++)
for(j=1,;j<=n;j++){
掃描第j個(gè)樣本頁面的DOM樹,;
把第j個(gè)樣本頁面中的第i項(xiàng)內(nèi)容的路徑表達(dá)式寫入path[i]中,,即path[i]=path[i]+{path[i][j]};
}
for(i=1,;i<=m,;i++){
while(path[i]!=null){
隨機(jī)提取一條path[i][j]令其等于apath;
apath與path[i]中其它路徑表達(dá)式與其它進(jìn)行比較,,獲得被apath覆蓋的正例集合S,;
path[i]=path[i]-S;//刪除被覆蓋的正例
LocationIB [i]= LocationIB [i]+apath,;
}
}
LocationIBs={ LocationIB [1], LocationIB [2],……, LocationIB [m]},;
return LocationIBs;
}
(3) 信息塊內(nèi)信息點(diǎn)定位
確定了樣本集合中信息塊的定位路徑之后,,可以通過在信息塊內(nèi)先序遍歷得到具體信息點(diǎn)的定位路徑,,這個(gè)定位路徑用XPath[3]表示。
2.3.2 提取信息
利用歸納學(xué)習(xí)得到的XPath,,編寫XSLT[4]文檔,,就可以根據(jù)該文檔轉(zhuǎn)換DOM中的節(jié)點(diǎn),生成一個(gè)XML文檔,,這個(gè)XML文檔中只保留XPath指定的節(jié)點(diǎn),,從而完成信息提取。
2.4 相似網(wǎng)頁搜索
生成的提取模式可以重用于結(jié)構(gòu)相似的網(wǎng)頁,,因此,,需要判斷所搜集的網(wǎng)頁是否適用于已有提取模式。本文提出利用DOM判斷所搜集網(wǎng)頁是否與樣本結(jié)構(gòu)相似,,進(jìn)而確定是否可利用已有模式提取所搜集網(wǎng)頁中的信息,。
2.4.1 判斷相似網(wǎng)頁
從一個(gè)網(wǎng)頁到DOM的轉(zhuǎn)換來看,網(wǎng)頁中的元素都是以嵌套關(guān)系轉(zhuǎn)換成為DOM樹中的節(jié)點(diǎn),每個(gè)元素在DOM樹中都有固定位置的節(jié)點(diǎn)對(duì)應(yīng),,可以將這個(gè)轉(zhuǎn)換過程抽象成一個(gè)函數(shù):
設(shè)網(wǎng)頁標(biāo)記E和DOM樹節(jié)點(diǎn)N是兩個(gè)集合,,一個(gè)從E到N的函數(shù)f記為:E—>N,是一個(gè)滿足以下條件的關(guān)系:
對(duì)每一個(gè)e E,,都存在唯一的n N,,使<e,n> f,,記作f(e)=n,,E是函數(shù)f的前域,N是函數(shù)f的陪域,。在表達(dá)式f(e)=n中,,e是函數(shù)的自變?cè)琻是對(duì)應(yīng)于自變?cè)猠的函數(shù)值,。
從函數(shù)的定義可以看出,,如果f(e)=n1,f(e)=n2,,那么n1=n2,。也就是說,一個(gè)自變?cè)谝粋€(gè)特定函數(shù)下,,有唯一的函數(shù)值與之對(duì)應(yīng),。利用這種關(guān)系可以推斷出一個(gè)網(wǎng)頁標(biāo)記集合按照嵌套關(guān)系只能影射為一個(gè)DOM樹,這樣,,判斷兩個(gè)網(wǎng)頁結(jié)構(gòu)是否相似可以轉(zhuǎn)換為判斷兩個(gè)網(wǎng)頁解析得到的DOM樹是否相似,。
算法描述如下:
先序遍歷測(cè)試網(wǎng)頁的節(jié)點(diǎn)列表NodeList1;
獲得NodeList1的長度Length1,;
先序遍歷樣本網(wǎng)頁的節(jié)點(diǎn)列表NodeList2,;
獲得NodeList2的長度Length2;
if(Length1=Length2){
for(i=1,;i<=Length1,;i++){
取得NodeList1的第i個(gè)節(jié)點(diǎn)Node1i;
取得Node1i的節(jié)點(diǎn)名NodeName1i,;
取得NodeList2的第i個(gè)節(jié)點(diǎn)Node2i,;
取得Node2i的節(jié)點(diǎn)名NodeName2i;
if(NodeName1i不同于NodeName2i){
return false,;
break,;
}
}
retuen true;
}
else{
return false,;
}
2.4.2 搜集相似網(wǎng)頁
本文設(shè)計(jì)了結(jié)合判斷網(wǎng)頁結(jié)構(gòu)的爬蟲算法,,來完成相關(guān)信息源的搜集,。
算法描述如下:
/*****初始化****/
設(shè)定搜索深度Depath;
設(shè)定當(dāng)前搜索深度currentDepath,;
從初始URL取回種子網(wǎng)頁,;
從種子網(wǎng)頁中取出所有URL,存入U(xiǎn)RL列表urlList,;
取得樣本網(wǎng)頁DOM樹的結(jié)點(diǎn)列表nodeList1,;
/*****搜索網(wǎng)頁*****/
for(currentDepath<=Depath;currentDepath++){
if(urlList!=NULL){
以先進(jìn)先出方法從URL列表中取出一個(gè)URL,;
從該URL取回測(cè)試網(wǎng)頁存入網(wǎng)頁庫,;
解析該網(wǎng)頁生成測(cè)試DOM樹;
獲得該DOM樹的節(jié)點(diǎn)列表nodeList2,;
if(nodeList1 與nodeList2相同){
從該測(cè)試網(wǎng)頁取出所有URL存入urlList,;
}
else{
從該測(cè)試網(wǎng)頁取出所有URL存入urlList;
將該測(cè)試網(wǎng)頁URL從URL列表清除,;
將測(cè)試網(wǎng)頁從網(wǎng)頁庫中刪除,;
}
}
2.5 格式輸出
提取結(jié)果最終要結(jié)構(gòu)化存儲(chǔ),本文采用XML作為提取結(jié)果,,它具有以下兩個(gè)便于進(jìn)行結(jié)構(gòu)化存儲(chǔ)的特點(diǎn):
(1) XML數(shù)據(jù)容易被其他應(yīng)用程序訪問和使用,方便與其它系統(tǒng)整合,。
XML數(shù)據(jù)結(jié)構(gòu)性強(qiáng),,可以直接被其它應(yīng)用程序訪問,或者通過XML的查詢語言來訪問也比較方便,。這樣,,信息提取系統(tǒng)可以方便地為信息集成、信息過濾等其它需要信息提取結(jié)果的系統(tǒng)服務(wù),。
(2) 提取結(jié)果可以容易地表示和轉(zhuǎn)換為不同格式,,滿足不同用戶的需要。
通過使用不同的XSLT文件,,同一內(nèi)容的提取結(jié)果可以用不同風(fēng)格展示,,應(yīng)用在不同的場(chǎng)合,使數(shù)據(jù)能夠更合理地,、有針對(duì)性地表現(xiàn)出來,。這在推動(dòng)信息數(shù)據(jù)表現(xiàn)個(gè)人化、風(fēng)格化的同時(shí),,也提高了數(shù)據(jù)的可重用性,。另外通過使用XSLT處理器和XSL樣式表,可以容易地將XML的提取結(jié)果轉(zhuǎn)換為另一種格式,,滿足不同需要,。
3 方法評(píng)價(jià)與結(jié)論
信息提取技術(shù)主要采用以下三個(gè)評(píng)價(jià)指標(biāo),,即查全率(Recall)和查準(zhǔn)率(Precision) 以及F值。查全率是測(cè)量被正確提取的信息的比例,,而查準(zhǔn)率用來測(cè)量提取出的信息中有多少是正確的,。計(jì)算公式如下(P是查準(zhǔn)率,R是查全率):
兩者取值在0和1之間,,數(shù)值越接近1,,查全率或查準(zhǔn)率就越高。
下面是查全率和查準(zhǔn)率的加權(quán)幾何平均值,,F(xiàn)值評(píng)價(jià)方法:
其中b 是一個(gè)預(yù)設(shè)值,,是P和R的相對(duì)權(quán)重,b大于1時(shí)表示 P更重要,,b小于1時(shí)表示R更重要,。通常設(shè)定為1,表示二者同等重要,。這樣用F一個(gè)數(shù)值就可看出系統(tǒng)的好壞,,F(xiàn)值也是越接近1越好。
本文對(duì)www.網(wǎng)站的10張網(wǎng)頁樣本和www.amazon.com網(wǎng)站的13張網(wǎng)頁樣本進(jìn)行測(cè)試,,測(cè)試結(jié)果如表1所示:
表1 系統(tǒng)測(cè)試效果表
從表1.1看出,,對(duì)于結(jié)構(gòu)比較規(guī)范的網(wǎng)站,該方法不用太多的學(xué)習(xí)樣本,,就能獲得比較高的查全率和查準(zhǔn)率,。
參考文獻(xiàn):
[1] Document Object Model,W3C Recommendation October,,1998.http://www.w3.org/TR/REC-DOM-Level-1/.[DB/OL]
[2] XHTML:The Extensible HyperText Markup Language,,W3C Recommendation,January 2000.http://www.w3.org./TR/xhtml1.[DB/OL]
[3] XML Path Language(XPath),,W3C Recommendation,, November 1999.http://www.w3.org/TR/xpath.html.[DB/OL]
[4] XSL Transformations(XSLT), W3C Recommendation,, November 1999.http://www.w3.org/TR/xslt.html.[DB/OL]
收稿日期:5月8日
修改日期“5月10日
作者簡(jiǎn)介:
1鄧超,,男,1973年生,,江西萍鄉(xiāng)人,,碩士研究生,主要研究方向Web信息提取
2熊選東,,男,,1964年生,湖北黃岡人,,副研究員,,碩士生導(dǎo)師,,主要研究方向Web信息安全,Web信息處理,。
|
|