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