楊鳳

【摘 要】本文給出一種Web頁面的數(shù)據(jù)結(jié)構(gòu)描述方式，比對所需信息的字符串序列，對通用型框架結(jié)構(gòu)和數(shù)據(jù)域進行劃分，經(jīng)規(guī)則化處理后可以對web網(wǎng)頁自動地生成模板，從而達到抽取信息的目的。

【關(guān)鍵詞】信息抽取；通用框架；算法設(shè)計

1.引言

計算機和計算機網(wǎng)絡(luò)的發(fā)展和普及，使得網(wǎng)絡(luò)逐漸成為信息交流的關(guān)鍵平臺。為了人們在海量的網(wǎng)絡(luò)信息中更加便捷地獲取所需信息，有必要對同領(lǐng)域信息的抽取、匯總、集成，可以建立對應領(lǐng)域的信息庫。

Web動態(tài)網(wǎng)頁由服務器根據(jù)請求從數(shù)據(jù)庫中選取數(shù)據(jù)并嵌入到通用模板而生成，缺乏結(jié)構(gòu)和語義信息的描述，其中包含的信息不易被一般應用程序直接獲取。因此，如何將網(wǎng)頁中的數(shù)據(jù)抽取出來就變得非常迫切。Web頁面的信息抽取技術(shù)為實現(xiàn)這一目標提供了新的途徑[1]。

2.Web信息抽取的過程設(shè)計

2.1信息抽取

信息抽取（Information Extraction）是從文本包含中識別出用戶所需的部分信息，并將其轉(zhuǎn)換為結(jié)構(gòu)化、有特定組織形式的數(shù)據(jù)集合的過程。

2.2 Web 頁面信息的數(shù)據(jù)結(jié)構(gòu)的定義

Web網(wǎng)頁的基本元素用三類標簽來描述，分別是開始標簽、結(jié)束標簽以及文本內(nèi)容。Web網(wǎng)頁的數(shù)據(jù)結(jié)構(gòu)是用字符串序列、標簽樹兩種結(jié)構(gòu)來描述。字符串序列是用開始標簽、結(jié)束標簽以及文本內(nèi)容構(gòu)成的一種線性數(shù)據(jù)結(jié)構(gòu)；標簽樹用開始標簽和文本內(nèi)容表示網(wǎng)頁層次結(jié)構(gòu)。

2.3 Web 信息抽取過程的設(shè)計

Web 信息抽取方法關(guān)鍵環(huán)節(jié)為通用框架結(jié)構(gòu)檢測、模板抽取。圖 1 是Web 信息抽取的過程圖。

Web 信息抽取是將包含用戶所需信息的 Web 網(wǎng)頁中的數(shù)據(jù)自動提取到一個結(jié)構(gòu)化的數(shù)據(jù)集內(nèi)的信息處理過程。Web 信息抽取針對有價值的文本進行結(jié)構(gòu)分析，其效率和質(zhì)量較高，更注重工程性和可操作性，也更容易面向?qū)嶋H應用[2]。

3.實現(xiàn)WEB信息抽取的關(guān)鍵技術(shù)

3.1 抽取規(guī)則——構(gòu)建通用型框架

通用型框架的建構(gòu)以比對字符串序列異同的方式進行，對通用型框架結(jié)構(gòu)和數(shù)據(jù)域進行劃分。其中，通用型框架是指與web網(wǎng)頁呈現(xiàn)的主要內(nèi)容無關(guān)的部分，如導航條、頭尾信息、廣告信息和 flash特效等。數(shù)據(jù)域是指web網(wǎng)頁中除了通用型框架以外的內(nèi)容，將數(shù)據(jù)域的字符串序列進一步轉(zhuǎn)換成標簽樹結(jié)構(gòu)，就得到數(shù)據(jù)的樣本集合。

通用型框架處理過程中檢測網(wǎng)頁間共有的且與網(wǎng)頁實質(zhì)內(nèi)容無關(guān)的信息，對去除通用型框架后得到的數(shù)據(jù)域信息進行信息抽取時，準確率會有所提高。具體操作是，首先進行頁面分區(qū)，將網(wǎng)頁劃分成不相交的區(qū)域的過程。然后定義區(qū)域樹用樹狀結(jié)構(gòu)對頁面分區(qū)的結(jié)果進行表示。樹的根結(jié)點對應于整個網(wǎng)頁，父結(jié)點的區(qū)域由各子結(jié)點區(qū)域組成。接下來，確定結(jié)點的分區(qū)級別，得到該結(jié)點對應的區(qū)域時進行的頁面分區(qū)次數(shù)。區(qū)域樹的分區(qū)級別指樹的深度。為區(qū)域樹選定合適的分區(qū)級別將有利于檢測到更佳的通用型框架結(jié)構(gòu)。再定義通用型框架結(jié)構(gòu)。將網(wǎng)頁間共有的、與網(wǎng)頁實質(zhì)內(nèi)容無關(guān)的頭信息、尾信息、廣告、瀏覽導向條以及 flash 等內(nèi)容信息稱為通用型框架結(jié)構(gòu)。用雙序列比對算法對網(wǎng)頁字符串序列進行比對，將最佳的相似字符串作為通用型框架結(jié)構(gòu)。算法流程如下[3，4]：

（1） 對變量max、x和y進行初始化。max 表示局部最大值，y 和x 分別表示矩陣當前行及其前一行。

（2） 計算得分矩陣。該過程由以下三步迭代完成。

（2.1）

其中p（i+1，j+1）為字符串匹配函數(shù)，當字符串匹配時取值c，否則，可取值d（d<0）；g為間隔罰分。

（2.2）當p（i+1， j+1）<0時，如果max

（2.3）令x=y。

（3）計算最佳相似字符串的長度 ，其中， 為調(diào)節(jié)參數(shù)。

（4）得到通用框架。位于Pm- 與Pm范圍中的最佳相似字符串就是通用框架。算法中，在找到最長的匹配字符串后，需要對參數(shù)進行調(diào)節(jié)，從而得到最佳的相似字符串作為通用型框架結(jié)構(gòu)。

3.2模板抽取

Web 上的動態(tài)頁面有兩種來源，一類是超鏈接方式，另外一類需要填寫 Web 頁面上的表單（Form），然后提交給網(wǎng)站服務器后動態(tài)生成，這類頁面無法直接獲取，也就是深網(wǎng)頁。根據(jù)動態(tài) Web 頁面的構(gòu)成模板可以將其分為A、B兩大類。A 類：整個頁面內(nèi)容包括很多項數(shù)據(jù)，這些數(shù)據(jù)對應于一個實體的各項屬性，組成了一條完整的記錄。B類：頁面中包含了多條記錄，每條記錄又包含多個數(shù)據(jù)項，即該條記錄的屬性項各條記錄的屬性項基本相同。

模板抽取是對樣本間各種匹配與不匹配的部分進行搜索和劃分，經(jīng)規(guī)則化處理后可以得到模板。模板抽取過程如圖2所示：

本文給出的抽取算法是：輸入一個樣本集合，每一次比較包裝器樹和一個樣本網(wǎng)頁樹并產(chǎn)生一棵新的包裝器樹，然后再利用該包裝器樹和另一個樣本網(wǎng)頁樹進行比較直至所有的樣本網(wǎng)頁比較完畢后生成最終的包裝器樹。其流程描述如下：

（1）設(shè)定任一基準Pjz∈V集合；

（2）對P∈V-{Pjz}，從根結(jié)點開始進行深度遍歷，設(shè)Rjz=Root（Pjz），Rb=Root（P）。

（2.1）Rjz和Rb為葉結(jié)點，若Rjz.Name≠Rb.Name，令Rjz。Name待提取信息；

（2.2）Rjz和Rb均不為葉結(jié)點：

（2.2.1） Rb！=NULL，且Rjz.Name≠Rb.Name，令Rb為其第一右兄弟節(jié)點，重復（2.2.1），否則轉(zhuǎn)（2.2.2）；

（2.2.2）若Rjz.Name≠Rb.Name，Rjz，Rb為其第一左子結(jié)點，轉(zhuǎn)（2.1），否則轉(zhuǎn)（2.2.3）；

（2.2.3）若Rb==NULL，令Rjz.Name為設(shè)定值；

（2.3）當Rjz 和Rb 中有且只有一個是葉結(jié)點時，

（2.3.1） 若Rb 非空，令Rb 為其第一右兄弟結(jié)點，重復（2.3.1），否則轉(zhuǎn)（2.3.2）；

（2.3.2） 若Rb 為空，令Rjz. Name =，否則，轉(zhuǎn)（2.1）；

（2.4）若Rjz 非空，令Rjz 為其第一右兄弟結(jié)點，重復（2.1），否則，轉(zhuǎn)（3）；

（3）重新遍歷Pjz ，對相同的子樹進行合并。

通過對網(wǎng)頁的通用型框架結(jié)構(gòu)進行定義，在信息抽取算法中引入了通用型框架結(jié)構(gòu)檢測階段，采用序列比對算法對同類網(wǎng)頁所共有的、與網(wǎng)頁表達的實質(zhì)內(nèi)容無關(guān)的信息進行檢測，除掉了通用型框架結(jié)構(gòu)的網(wǎng)頁信息，對信息抽取更加有利。該算法可以對數(shù)據(jù)密集的真實網(wǎng)頁自動地生成模板、抽取信息，既不局限于人為定制的測試網(wǎng)頁也不依賴于網(wǎng)頁內(nèi)容的先驗知識[5]。

4.實驗結(jié)果與分析

4.1 評價標準

實驗中，我們采用召回率和查準率作為評價的指標對信息抽取系統(tǒng)進行評價。從直觀上說，召回率可以理解為，從網(wǎng)頁中正確抽取出來的數(shù)據(jù)項的比例，查準率可以理解為，被抽取出來的數(shù)據(jù)項中正確的比重。

當我們評價一個信息抽取系統(tǒng)時，為了綜合評價系統(tǒng)的性能，應同時考慮這兩個指標。為了能夠直接地同時比較召回率和查準率，設(shè)定β為權(quán)重參數(shù)，其值反應在評測時側(cè)重召回率還是查準率，由系統(tǒng)預設(shè)。若需要設(shè)定表明查準率更重要，就設(shè)定 β> 1，反之，召回率更重要則設(shè)定β< 1。在信息抽取系統(tǒng)中，通常設(shè)定β==1，以反應召回率和查準率的重要性是等同的。

4.2 實驗設(shè)計與分析

本文實驗采用的網(wǎng)頁來自于真實的站點中的動態(tài) Web 網(wǎng)頁，其中包含的信息紛繁復雜，包括 HTML 頁面的頭信息、尾信息、廣告、瀏覽導向條、flash 等，實驗中，我們預先對網(wǎng)頁中標簽缺失的情況進行修正以便建立標簽樹。

在數(shù)據(jù)集合上應用帶序列比對的信息抽取算法，對參數(shù)θ進行調(diào)節(jié)，根據(jù)抽取結(jié)果為算法選擇合理的參數(shù)值。表 1 結(jié)果顯示的是θ取不同值時的召回率和查準率。

對參數(shù)θ取不同的值分別進行實驗，根據(jù)實驗結(jié)果為算法選擇合理的參數(shù)值，為后緒模板抽取實驗做好準備。圖3為表1對應的曲線圖。

在實驗召回率與查準率對照圖即圖3 中，縱坐標表示召回率和查準率，橫坐標表示參數(shù)θ，如圖所示，當θ的取值為 1.2時抽取信息的效果最優(yōu)。實驗證明了本文上述抽取算法的有效性。

5.結(jié)論

web網(wǎng)頁的信息抽取過程中采用序列比對的方式進行通用型框架結(jié)構(gòu)檢測，剝離網(wǎng)頁中的冗余信息，有利于模板抽取的精確度的提高。實驗中把真實網(wǎng)站的數(shù)據(jù)密集型網(wǎng)頁作為樣本，對抽取算法在數(shù)據(jù)量和抽取準確率等方面進行了測試和比較，結(jié)果充分證明了算法的有效性。

參考文獻：

[1]張鵬程，李必信，李雯睿. 時間屬性序列圖： 語法和語義.軟件學報，2010，Vol.21（11）： 2752-2767.

[2]劉凱鵬，方濱興.一種基于社會性標注的網(wǎng)頁排序算法.計算機學報，2010，Vol.33（6）： 1014-1023.

[3]陳傳夫，唐瓊，于媛，吳志強等.網(wǎng)絡(luò)上科學信息的時效性測量.情報學報，2009， Vol.28（4）： 610-617.

[4]劉冬寧，湯庸.時態(tài)數(shù)據(jù)庫時間軸的動態(tài)邏輯模型.軟件學報， 2010， Vol.21（4）：694-701.

[5]寇月，李冬，申德榮，于戈，聶鐵錚.D-EEM： 一種基于DOM 樹的Deep Web 實體抽取機制. 計算機發(fā)展與研究，2010，Vol.47（5）： 858-865.

基金項目：

廣西教育廳科研課題（201106LX606）。

作者簡介：

楊 鳳（1981-），女，湖南常德漢壽縣人，碩士，講師，主要研究方向為：數(shù)據(jù)挖掘。