一种基于树型结构的包装器生成算法研究

李丹

（沈阳城市建设学院，辽宁沈阳，110167）

0 引言

大数据时代的到来，网络数据激增，Web信息抽取技术成为新兴热点，作为信息抽取技术核心的包装器也迎来了春天。所谓包装器（Wrapper），就是一个能够将数据从HTML网页中抽取出来并且将它们还原为结构化的数据（例如XML数据）的软件程序。[1]

Web信息抽取技术的分类方式有多种，根据所用的原理和方式，将这些原型系统所使用的包装器分为三类：手工构造的包装器，如 TSIMMIS[2]；机器学习方式的包装器，如RoadRunner[3]；可视化交互式的包装器，如W4F[4]等。

1 传统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规范的页面；（2）将训练样本转化为树型结构；（3）在遍历和比较过程中采用先序遍历。遍历和匹配过程中存在两种类型的不匹配：字符串不匹配，是由于一个数据库字段的不同数值造成的，标记为#PCDATA；标识符不匹配：包括标识符不匹配和标识符与字符串不匹配两种，出现这种情况的原因是出现了迭代项（+）或可选项（？）。设树的高度为h，树中每层的最大结点数为n，则算法的时间复杂度为O（h*n*n）。

举例，图1为张三同学的树型信息页面，作为包装器；图2为李四同学的树型信息页面，作为训练样本；图3为通过算法比较后得到符合UFRE规则的包装器树。

基于树型结构的包装器生成算法流程如下：

输入：页面样本集合Q

输出：最优包装器树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），否则执行（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.