李丹

（沈陽城市建設(shè)學(xué)院，遼寧沈陽，110167）

0 引言

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

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

1 傳統(tǒng)RoadRunner算法

1.1 UFRE表達(dá)式

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

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

給定符號的字母表∑，和不在∑中的特殊符號PCDATA，一個(gè)在∑上的union-free正則表達(dá)式是在字母表∑∪{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]。算法思想：輸入兩個(gè)符號化的頁面，指定一個(gè)作為包裝器，一個(gè)作為樣本，通過樣本與包裝器之間的比較，尋找不匹配，得到一個(gè)能同時(shí)適用兩個(gè)頁面的正則表達(dá)式。逐步修正求精，得到最終的包裝器（符合UFRE表達(dá)式）。

2 一種基于樹型結(jié)構(gòu)的包裝器生成算法

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

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

基于樹型結(jié)構(gòu)的包裝器生成算法流程如下：

輸入：頁面樣本集合Q

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

（1）從樣本集合Q中任選一個(gè)作為基準(zhǔn)，記為baset 。

圖1 張三同學(xué)的樹型信息頁面

圖2 李四同學(xué)的樹型信息頁面

圖3 包裝器樹

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

（2.3）當(dāng) Pbase和 Pm中僅有一個(gè)為葉結(jié)點(diǎn)時(shí)，

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

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

（2.4）若baseP 非空，令baseP 指向其第一右兄弟結(jié)點(diǎn)，重復(fù)（2.1），否則，轉(zhuǎn)（3）。

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

3 結(jié)論

本文提出一種基于樹型結(jié)構(gòu)的包裝器生成算法，該算法不需要特殊指定訓(xùn)練樣本，不需要目標(biāo)樣本的先驗(yàn)知識，包裝器生成是自動(dòng)的。在對輸入的兩個(gè)訓(xùn)練樣本進(jìn)行匹配過程中引入樹型結(jié)構(gòu)，有效降低了算法的時(shí)間復(fù)雜度，對迭代項(xiàng)和可選項(xiàng)的識別也更加準(zhǔn)確、高效。

[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òng)生成方法的研究[D].吉林大學(xué), 2005.