一種基于樹型結構的包裝器生成算法研究

李丹

（沈陽城市建設學院，遼寧沈陽，110167）

0 引言

大數(shù)據時代的到來，網絡數(shù)據激增，Web信息抽取技術成為新興熱點，作為信息抽取技術核心的包裝器也迎來了春天。所謂包裝器（Wrapper），就是一個能夠將數(shù)據從HTML網頁中抽取出來并且將它們還原為結構化的數(shù)據（例如XML數(shù)據）的軟件程序。[1]

Web信息抽取技術的分類方式有多種，根據所用的原理和方式，將這些原型系統(tǒng)所使用的包裝器分為三類：手工構造的包裝器，如 TSIMMIS[2]；機器學習方式的包裝器，如RoadRunner[3]；可視化交互式的包裝器，如W4F[4]等。

1 傳統(tǒng)RoadRunner算法

1.1 UFRE表達式

RoadRunner 使用 UFRE（Union-Free Regular Expression）表達式來描述HTML頁面包裝器。

定義1.1 union-free正則表達式（UFRE）[5]

給定符號的字母表∑，和不在∑中的特殊符號PCDATA，一個在∑上的union-free正則表達式是在字母表∑∪{PCDATA，.，+，?，(，)}上的字符串，定義如下：

（1）空串ε及所有∑∪{PCDATA}中的元素是UFRE；

（2）如果 A 和 B 是 UFRE，那么 A·B，（A）？是 UFRE，（A）？表示（A|ε）（表示選擇）；

（3）如 果 A是 UFRE，(A)+也 是 UFRE，(A)+表 示 A、AA、……，+閉包（表示迭代）。

1.2 RoadRunner算法

RoadRunner的匹配算法稱為ACME（Align，Collapse under Mismatch，and Extract）[3]。算法思想：輸入兩個符號化的頁面，指定一個作為包裝器，一個作為樣本，通過樣本與包裝器之間的比較，尋找不匹配，得到一個能同時適用兩個頁面的正則表達式。逐步修正求精，得到最終的包裝器（符合UFRE表達式）。

2 一種基于樹型結構的包裝器生成算法

算法改進之處：（1）使用軟件工具將樣本集中的頁面處理為符合XHTML規(guī)范的頁面；（2）將訓練樣本轉化為樹型結構；（3）在遍歷和比較過程中采用先序遍歷。遍歷和匹配過程中存在兩種類型的不匹配：字符串不匹配，是由于一個數(shù)據庫字段的不同數(shù)值造成的，標記為#PCDATA；標識符不匹配：包括標識符不匹配和標識符與字符串不匹配兩種，出現(xiàn)這種情況的原因是出現(xiàn)了迭代項（+）或可選項（？）。設樹的高度為h，樹中每層的最大結點數(shù)為n，則算法的時間復雜度為O（h*n*n）。

舉例，圖1為張三同學的樹型信息頁面，作為包裝器；圖2為李四同學的樹型信息頁面，作為訓練樣本；圖3為通過算法比較后得到符合UFRE規(guī)則的包裝器樹。

基于樹型結構的包裝器生成算法流程如下：

輸入：頁面樣本集合Q

輸出：最優(yōu)包裝器樹baseP

（1）從樣本集合Q中任選一個作為基準，記為baset 。

圖1 張三同學的樹型信息頁面

圖2 李四同學的樹型信息頁面

圖3 包裝器樹

（2.2.3）若 Pm為空，則令 Pbase.N ame=“”? 。

（2.3）當 Pbase和 Pm中僅有一個為葉結點時，

（2.3.1）若 Pm非空，則令 Pm指向其第一右兄弟結點，重復（2.3.1），否則執(zhí)行（2.3.2）；

（2.3.2）若 Pm為空，則令 Pbase.N ame=“”? ，否則轉（2.1）；

（2.4）若baseP 非空，令baseP 指向其第一右兄弟結點，重復（2.1），否則，轉（3）。

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

3 結論

本文提出一種基于樹型結構的包裝器生成算法，該算法不需要特殊指定訓練樣本，不需要目標樣本的先驗知識，包裝器生成是自動的。在對輸入的兩個訓練樣本進行匹配過程中引入樹型結構，有效降低了算法的時間復雜度，對迭代項和可選項的識別也更加準確、高效。

[1]Kushmerick N. Wrapper induction: Efficiency and expressiveness[J].Artificial Intelligence, 2000, 118(1–2):15-68.

[2]Hammer J, Nestorov S, Yerneni R, et al. Template-based wrappers in the TSIMMIS system[C].ACM, 1997:532-535.

[3]Crescenzi V, Mecca G, Merialdo P. RoadRunner: Towards Automatic Data Extraction from Large Web Sites[J].Vldb Issn –3455 Sistedes, 2001:109--118.

[4]Sahuguet A, Azavant F. Building intelligent Web applications using lightweight wrappers[J].Data &Knowledge Engineering, 2001, 36(3):283-316.

[5]張玉良.一種基于后綴樹的包裝器自動生成方法的研究[D].吉林大學, 2005.