李 颖，张晓贤，孙佳慧

（1.吉林师范大学计算机学院，吉林四平136000;2.长春工程学院软件学院，长春130012;3.空军航空大学基础部，长春 130022）

0 引 言

数据挖掘最早出现在20世纪80年代后期，是多学科领域的范畴，有很多独有的特征[1]。频繁模式的挖掘[2]，在数据挖掘领域中占有重要的地位，频繁模式挖掘的过程是搜索给定的数据集中多次出现的联系。笔者提出一种基于这种模式的OEM（Object Exchange Model）模型，并实现了半结构化数据的模式抽取。

1 OEM模型

OEM模型[3]是用来描述半结构化数据[4]的模型，他是一种自描述性模型。为了让数据交换在异构的数据源之间顺利进行，必须找到一个高度灵活并且同时能表达大多数不同类型数据的高速模型，因而OEM模型受到了研究人员的关注。

OEM模型由表示对象的节点以及表示层次关系的带标签（label）的有向边构成，即可看成一个图。通常每个对象用四元组表示（id，label，type，value），对特殊情况也可以特殊处理。其中id是对象的唯一标识。label是对象的标签描述。type是对象类型，有两类：原子的和复杂的。原子代表不可分割，也是这类数据的特点;复杂对象是引用（object references）的集合，每个对象引用指向另一个子对象。value是该对象的值域。

OEM模型可用一个有向图表示（见图1）。

图1 OEM例子Fig.1 OEM example

为描述算法，给出必要的特殊定义：每条边记作〈oi.ln.om〉，该表示从对象oi通过标签为ln的边指向对象 om。如果图1中存在〈o1.l1.o1〉，〈o2.l2.o2〉，〈o3.l3.o3〉，…，〈on.ln.on〉，则称 OEM 模型图中存在环路。

简单路径Psp（simple path），是标签l的序列，用“·”隔开，记做Psp=l1.l2.l3.…ln，其中n为路径长度。

Psp=club.name.official是长度为3的简单路径。

为方便算法的描述，特给予以下定义。……