（计算机科学与技术专业论文）xml数据集公共模式获取技术研究.pdf

国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 摘要 x m l ( e x t e n s i b l e ma r k u p l a n g u a g e)是 w3 c ( w o r l d wi d e w e b c o n s o rt i u m)于 1 9 9 8 年2 月推出的一种标记语言，很快就成为we b上数据表示 和数据交换的标准。由于越来越多的数据使用 x ml进行描述，应用数据的模 式对 x ml数据的查询和管理是目前研究和开发的一个热点。在实际建立 x ml 应用时第一步是设计 x ml模式或 d t d ，但是使用信息获取工具从半结构化数 据中抽取的x ml数据和从无结构数据转换的x ml数据则难于预先定义适当的 模式。因而把这些x ml纳入有效的管理前必须建立x ml的模式。本文重点研 究了x m l 数据集公共模式获取技术。 首先，改进了单文档模式获取技术。单文档模式获取是公共模式获取的基 础，但是不能满足公共模式获取技术要求，对单数据获取过程进行了分解，增 加了对多数据处理的功能。 第二， 提出了基于模式合并的公共模式获取技术。 模式相关的x ml数据存 在公共模式，基于模式合并的思路是独立获取单 x ml文档的模式，再采用模 式合并技术，将单个模式合并为满足精确性和简洁性要求的公共模式。基于模 式合并的方法相对于增量式方法和数据合并式方法更关注于获取模式的质量， 分阶段实现模式的精确性和简洁性。 第三，基于规则技术。基于模式合并的公共模式获取过程主要采用基于规 则的技术。具体地由单个模式生成规则、模式合并规则和模式优化规则组成， 分别实现单个模式的生成、多个模式的合并和模式的优化，提出了最小模式集 选取方法从而避免了设计复杂的模式选取代价函数。 第四，部分实现了原型系统 s c h e m a g r a b b e r 。实现了x ml数据集的解析、 表示，以及标签路径一正则式描述的模式到x ml s c h e m a 转换方法，全部实现 了单个模式生成规则和模式合并规则，原型系统支持自 动和手工生成。 关键字: x ml , x ml s c h e m a , d t d ，模式相关性，模式合并，正则表达式 i 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 abs tract x ml ( e x t e n s i b l e ma r k u p l a n g u a g e ) i s a m a r k u p l a n g u a g e p r o p o s e d b y w3 c ( t h e w o r l d w i d e w e b c o n s o r ti u m ) i n f e b ru a ry 1 9 9 8 . q u i c k l y , x m l b e c o m e s a s t a n d a r d f o r d a t a r e p r e s e n t a t i o n a n d e x c h a n g e o n t h e w o r l d - wi d e we b . b u t t h e r e i s a r e m a r k a b l e p r o b l e m a m o n g r e s e a r c h e s a n d a p p l i c a t i o n s o n x ml , ( 1 ) m u c h r e s e a r c h w o r k f o c u s e s o n s t o r a g e a n d q u e ry t e c h n o l o g y o f x ml d a t a a p p l y i n g d t d o r x ml s c h e m a . ( 2 ) i n c o m m o n , d t d o r x ml s c h e m a i s d e s i g n e d b e f o r e s t a rt i n g a x ml a p p l i c a t i o n , b u t x m l d a t a , w h i c h i s p r o d u c e d fr o m u n s t ru c t u r e d o r s e m i - s t r u c t u r e d d a t a b y g e n e r a t e t o o l s w i l l e n o r m o u s e m e r g e w i t h o u t d t d o r x ml s c h e m a . t h u s t h e c r i t i c a l p r o b l e m i s t h e d i s c o v e ry o f t h e s t r u c t u r e i n f o r m a t i o n b e f o r e t h e p r o c e s s a n d m a n a g e m e n t o n t h e x ml d a t a . t h i s p a p e r p r o p o s e s a t e c h n o l o g y o f e x t r a c t i n g s c h e ma f r o m xml d o c u me n t s . t h e c o n t r i b u t i o n s o f t h e t h e s i s a r e s h o wn b e l o w. i t i s e a s y t o e x t r a c t s c h e m a f o r s i n g l e x ml d o c u m e n t . t h e s c h e m a c a n b e i n f e r r e d w h e n t h e x m l d o c u m e n t i s p a r s e d s i m u l t a n e o u s l y . t h e p r o p o s e d t e c h n o l o g y e x t r a c t s a c o m m o n s c h e m a o n a n x m l d o c u m e n t c o l l e c t i o n . a s t h e r e i s a b u n d a n t x ml d a t a o n i n t e rne t , i t i s u n r e a s o n a b l e t o e x t r a c t a s c h e m a f o r e a c h x ml d o c u m e n t . m o r e o v e r , s o m e i n h e r e n t r e l a t i v i ty l i e s in a g r o u p o f x ml d o c u m e n t s , t h u s t h e s e d o c u m e n t s a r e d e f i n e d 场 a s c h e m a , t h a t i s , a c o m m o n s c h e ma c a n b e e x t r a c t e d fr o m t h e m. a n e w m e t h o d , s c h e m a - m e r g i n g f o r c o m m o n s c h e m a e x t r a c t i n g i s e m p l o y e d . t h e d e s i r a b l e s c h e m a i s c h a r a c t e r i z e d b y t w o q u a l i t a t i v e r e s t r i c t i o n s , ( 1 ) t h e s c h e m a s h o u l d b e c o n c i s e , ( 2 ) t h e s c h e m a s h o u l d b e p r e c i s e . r e s t ri c t i o n ( 1 ) e n s u r e t h a t t h e i n f e r r e d s c h e m a i s e a s y t o u n d e r s t a n d a n d s u c c i n c t , r e s t r i c t i o n ( 2 ) e n s u r e t h a t t h e i n f e r r e d s c h e m a i s n o t t o o g e n e r a l a n d c a p t u r e t h e s t r u c t u r e . s c h e m a - m e r g i n g m e t h o d c r e a t e s t h e i n f e r r e d s c h e m a i n t w o s t e p s , o n e s t e p i n f e r s p r e c i s e s c h e m a s , t h e o t h e r c o m b i n e s s c h e m a s i n t o c o n c i s e g e n e r a l s c h e m a . t h e p r o c e s s o f t h e e x t r a c t i n g s c h e m a c o m p ri s e s t h r e e k i n d s o f h e u r i s t i c ru l e s . s c h e m a - c r e a t in g ru l e s f in d t h e p a tt e rn s i n i n p u t t a g s e q u e n c e s , s c h e m a - m e r g i n g ru l e s b a s e d o n c o m m o n s u b e x p r e s s i o n c o m b i n e s e v e r a l s c h e m a s i n t o o n e , s c h e m a - o p t i m i z a t i o n ru l e s e l i m i n a t e r e p e a t e d a n d r e d u n d a n t e x p r e s s i o n s . a p r o t o t y p e i s i m p l e m e n t e d b a s e o n t h e d i s c u s s e d t e c h n o l o g y . t h e x ml d o c u m e n t a n a l y s i s a l g o ri t h m a n d s c h e m a o u t p u t a l g o ri t h m a r e m e n d e d . t h e r e v i s i o n o f t h e a n a l y s i s a l g o r i t h m i s p e r f o r m e d t o m a t c h t h e r e q u i r e m e n t o f a c o l l e c t i o n o f x ml d o c u m e n t . t h e s c h e m a o u t p u t a l g o r i t h m c o m p l e t e s t h e t r a n s f o r m a t i o n fr o m r e g u l a r e x p r e s s i o n s i n t o x ml s c h e ma . k e y wo r d x ml , x ml s c h e m a , d t d , s c h e m a - r e l a t i v i t y , s c h e m a m e r g e , r e g u l a r e x p r e s s i o n 1 1 独创性声明 本人声明 所呈交的学位论文 是我本人在导师 指导下进行的 研究工作及取得 的 研究 成果. 尽我 所知， 除了 文中 特别加以 标注和致谢的 地方外， 论文中 不 包含 其他人已 经发表和撰写过的 研究 成果， 也 不包含为获 得国 防 科学技术大学或其它 教育机构的 学 位或证书而 使用过的 材料. 与我一同 工作的同 志对本研究 所 做的 任 何贡献均已 在论文中 作了 明 确的 说明 并 表示 谢意. 学 位 论文 题目 :x m l 数 据 集 公 共 模式 获 取 技 术 研究 、 、 二 华、 ，*拙， 可 金* ， _ 一，、 、， _ _ _ 学 位 论 文 作 者 签 名 : 旦i w _ 一 一 一鱼 - 一日 期 : 2 - - 3年，月 ， 乡 日 学位论文版权使用授权书 本人完 全了 解国防 科学 技术大学 有关 保留、 使用学 位论文的规 定. 本人授权 国防 科学技术大学可以 保留 并向国 家有关部门 或机构送交论文的复印 件和电 子 文档， 允许 论文被查阅 和 借阅 ; 可以 将学 位论文的 全部或部 分内 容编入有关数 据 库进行 检索， 可以 采用影印 、 缩印 或扫描等复制手段保存、汇 编学 位论文。 ( 保密 学 位论文在 解密 后适 用本授权书. ) 学 位 论文 题目 :w i. 数 据 集 公 共 拱式 获 取 技 术 研究 学 位论文 作者签 名: 作者指导 教师签名: 74 4 1 , - 廊改 日 期 :z 0 叼 年 2月: ， 日 日 期: 夕 四; 年 i s月d j 日 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 图 目 录 图 2 . 1 o e m模型二 . . . . . . . . ， . . . ， . . . ， . . . ， . ， ， . . . . . . . . . 7 图 2 .2一个x ml 文档实例. ， . . . ， . ， . - . . . . . . . . . ， . . . . . . . . 9 图 2 .3 x ml 文档的d o m树表示. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 0 图 2 . 4一个实例d t d说明. ， . ， ， 二 ， ， . . ， ， ， . ， . ， . ， . . . . . . . . . . . . . . . . . . . 1 2 图 2 .5 x ml文档1 二 . ， . . . . . . . . . . . . . . . . . . . . . . ， . . . . . . . . ， ， . ， . ， ， . . . . . . ， 二 1 4 图 2 6 x ml文档2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 4 图 2 .7 x ml文档 1 的模式. . . . . . . . . . . . . . . . . . . . . . . . . . . . “ 二 卜 二 ， 卜 ，. . . 1 4 图 2 .8 x ml文档1 和2 的公共模式. . . . . . . . . . . . . . . . ， . . . . . . . . . . . . . . . . . . . 二1 5 图 3 . 1 x ml s c h e m a 定义的模式x s d 1 ， ， ， . ， . ， ， ， . . . . . . ， . . . . . . . . . . 2 1 图 3 .2模式 x s d 1 的内部表示 ， . . . . . . . . . . . . . . ，. . ， . . . . . . . . . . . . . . 2 1 图 3 .3对应于d t d的x ml数据解析结果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 图 3 .4对应于x ml s c h e m a 的x ml 数据解析结果 . . . . . . . . . . . . . . . . . . .二 ， 2 2 图 3 .5对应于x ml s c h e m a 的实际解析结果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 图3 .6 x m l 文 档x , . . . . . ，. . . . . . . . . . . . . 2 4 图3 .7 x m l 文 档x 2 . . . . . . . . . . . . . . . . . . . .2 5 图 3 . 8 x ml 数据集x s 解析结果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ， ， . ， ，二 ， . . 2 6 图3 .9 x m l 数 据 集 解 析 过 程 . . .，一 2 6 图3 .1 0 公 共 模 式 生 成 过 程 . . . . . . . . . 3 2 图3 .1 1 模 式 转 换 与 输 出 . ，. ，. .3 4 图 4 . 1 s c h e m a g r a b b e r 系统结构图. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 5 图4 .2系统用 例图. . . . . . ， . ， . . . . . ， 二 ， ， . ， ， ， 二，. ， ， .， . . . . . . . . . . . . 3 6 图 4 .3解析模块的类结构图. . 二 ，. . . . . . ， 二， . . . . . . ， ， ， . . . . . . . . . . . . . . . . . . . 3 6 图 4 .4公共模式生成模块类结构图 二 ，. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 9 图 4 . 5重复描述生成规则算法二 ，.， ， ， . . . . . . . 卜 . ， . ， ， 二 4 0 图 4 . 6随机出 现描述生成规则算法. . . . . . . . . . . ， . ， . . ，. ， . ， . . . ， 二 ， . ， . . . . . 4 0 图4 .7 优 化 规 则 算 法. 二 . . 二 . . . . ，.，. ， ，二 ，. . . . . . 4 1 图4 .8 模 式 与 实 例 映 射 关 系 . . .4 2 图 4 .9选取最小完全模式算法 . “ . .， 二 卜二 “ . . 二 . . . . . . . . . . . . . . 4 2 图4 .1 0 模 式 合 并 算 法 二 ，. .4 3 图 4 . 1 1 模式转换输出模块类结构图. ，. . . . 卜. . . . . . . . . . . . . 4 3 一 一一一 - 一-一一一，一一.一一， -一目 一-一 l v 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 表 目 录 3 . 4. d t d与x ml s c h e m a 描述转换 生成模式对比 . . . . . . . . ， . . . . . . . . . . . 3 3 . . . . . . . . . . . 4 4 表表 一一，一. 一-一一一-. 妇 一一一一一-. 一一 v 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 第一章 绪论 1 . ， 课题背景 1 . 1 . 1 i n t e r n e t 上信息特点 x m l ( e x t e n s i b l e m a r k u p l a n g u a g e ) 1 标 准公 布以 来， x m l正以 其灵 活 性 和 易处理性成为 www 上数据表示和交换的标准，大量的半结构化数据被描述为 x ml形式。其影响几乎涉及很多领域，支持几乎所有的语义相关的互操作环节 ( 例如 we b站点表示、无线访问以及移动语言访问等等) 。目前的 x ml规范已经 全面支持基于 i n t e rn e t 的x ml信息查询，就像现有的搜索引擎能够查询基于 w e b 的h t m l文档一样， x ml的最终目 标是使i n t e rn e t 成为一个巨大的分布式x m l 数 据库。 x m l数据可以通过包括数据库系统、文件系统、应用系统在内的任何形式 存储在i n t e rn e t 的任何地方 2 . 总的说来，当前i n t e rn e t 信息的特点有:a ) i n t e rn e t 上接受x ml为数据表示和 数据交换的标准，由于 x ml的灵活性和可扩展性逐渐成为数据表示和交换的主流 标准; b ) i n t e rn e t 上的信息总量持续膨胀，以x ml作为标准表示的数据不断增长 而且分布在i n t e rn e t 各个角落; c ) 有模式约束和无模式约束的x m l数据都大量存 在，当x ml被用作数据交换标准时， x m l具有严格定义的模式 ( d t d或 x m l s c h e m a ) ,当 x ml用于无结构或半结构数据表示时常常难于预先定义 x m l的模 式。 通过以上分析可以看出，面对不断增长的 x ml数据，需要对数据进行有效的 访问和管理。目前研究热点之一是利用 x ml模式把数据纳入传统数据库中以及利 用 模式进行x m l数 据的查询 优化 2 3 ， 那么 对于无模式的x m l数据进行有效的 访问 和管理前必先获取x m l数据的模式 4 . 1 . 1 .2半结构化数据 x ml 数据是一种半结构化数据。 半结构化的数据通常没有严格的类型定义， 描述数据结构的信息包含在数据当 中。为此， 在很多研究中 采用了 基于有向图的半结构化数据模型如 o e m, e d g e l a b e le d g r a p h 和la b e le d m u lt ig r a p h s 5 6 7 等 等。 按 照 这 样的 模 型， 半 结 构 化 数 据 可以用标注的有向图表示，图中结点表示对象，边表示对象之间的联系。 借鉴传统 数据库系统中模式的概念可以定义并建立半结构数据的模式。 第 t 页 一 一 一 一 一 一 一 旦 竺 垫尝拉 土述查 一 竺.色年殡赏ty. 竺 . 王 _ 二 _， . _ 采用半结构化的数据模型处理w e b 数据时，首先要从文本格式的数据中 抽取结 构信息。由于目 前在 w e b上普遍使用的 h t m l是面向 显示的 ( p r e s e n t a t i o n - o r i e n t e d ) ，主要用于描述数据的格式、显示样式以及数据的位置等，无法直接定义 数据的结构，因此从基于 h t ml的 w e b数据中抽取结构信息的难度很大，通常只 能根据数据的格式 ( 段落、字体、缩进距离等)并结合启发式规则来进行推测。 1 . 1 . 3 x ml数据 随着越来越多的数据变成 x ml的形式，而 x m l的设计思想简单: 用嵌套的 标识表示数据。 这就要求能够根据应用的需要定义标识。 事实上， x m l是 s g m l 的一个子集，但是x ml比s g m l更简洁、更易于实现。而且x ml延续了h t ml 的易用性，但与 h t m l不同的是，x ml是面向内容的 ( c o n t e n t - o r i e n t e d ) . x m l 中的标识主要用于描述数据之间各种类型的关系，而不是显示形式。 1 . 1 . 4 d o m 与 s a x x ml数据表现为纯文本，在创建、访问和操作 x ml数据时需要一个处理 x m l数据的规范接口。于是 w3 c制定了一套书写 x m l分析器的标准接口 规 范一 一 d o m 。 除此 之外， x m l d e v邮 件列 表中的 成员 根据 应用的 需 求也自 发 地 定义了一套对 x ml文档进行操作的接口规范一一s a x。这两种接口规范各有侧 重，互有长短，应用都比较广泛。 d o m ( d o c u m e n t o b j e c t m o d e l ) 8 ， 即 文 档对象模型。 基于d o m的x m l 分 析器将一个x ml文档转换成一个对象模型的集合 ( 通常称d o m树) ，应用程序正 是通过对这个对象模型的操作， 来实现对x m l 文档数据的操作。 s a x ( s im p l e a p i s f o r x m l ) ， 即x m l 简单 应用 程 序 接口 。 与d o m不同 ， s a x提供的访问 模式是一种顺序模式，是一种快速读写x ml数据的方式。当 使用 s a x分析器对x ml文档进行分析时，会触发一系列事件，并激活相应的事件处理 函数，应用程序通过这些事件处理函数实现对 x ml文档的访问，因而 s a x接口 也被称作事件驱动接口。 1 . 1 . 5 x ml模式 x m l 1 .0提供了一种机制一一文档类型定义 ( d o c u m e n t t y p e d e f i n i t io n , d t d ) ， 并将其作为规范的一部分。 符合d t d定义的x m l文档才是有效的。 d t d 实际上是“ 元标记”的概念， 它定义了 文档的整体结构以 及文档的语法。 但是d t d存在一些缺陷，如d t d使用不同于x ml的语法:d t d是封闭的， 第2页 一一一一一一竖巡壁一 兰 丝 生 色 ti3 1 立 生1 4 论3 c _ 二_ 二 _ 不 可以 在 d t d定义中 引 用其他已 定义的d t d ; d t d中 支持的 数据类型少。 所以 w 3 c 提出 了 解决d t d 缺陷的 方案一 x m l s c h e m a 9 1 0 . x m l s c h e m a 是通常带有. x s d 文件扩展名的x m l文档， 使用 x m l语法描述 x m l文档模式，为此 x m l s c h e m a定义了 一组专门的词汇:元素和属性使用 e le m e n t 和a t tr ib u t e 元素 声明 ， 结 构 使 用s im p l e t y p e 和c o m p l e x t y p e 元 素 创建。 马 1 . 2研究现状 随着半结构化数据的兴起，一些主要面向结构化数据以及非结构化数据的研究 成果不能很好地适用于半结构化数据。例如，近几十年中，研究人员对信息获取领 域进行了全面、深入的研究，取得了大量的研究成果。然而，由于传统信息获取领 域的研究主要集中于非结构化数据的信息处理，因而对于当前流行的半结构化数 据，很多研究成果不能适用。 对于半结构化数据 ( 主要是 x ml )的研究主要集中于数据的存储和查询，也 有基 于o e m ( o b j e c t e x c h a n g e m o d e l ) 的结 构信息 挖掘的 讨论 1 1 1 2 . 目 前，在 x ml数据模式自 动获取方面已经开展了一些研究工作，起初对于 s g m l数据的模式获取研究主要是基于d t d的 描述 1 3 1 4 ，当x m l的 标准被发 布， 并 广泛应用时， 讨论的 重点 转移到x m l的 模式获取， 如i b m a lp h a w o r k s d d b e 1 5 ; n a n y a n g t e c h n o lo g i c a l u n iv e r s it y( 新加坡) 研究的 d t d - m in e r 1 6 ; b e l l l a b o r a t o r i e s的 x t r a c t 6 系统和 m ic r o s o ft的 x s d i n f e r e n c e 1 7 ，其中 x s d i n f e r e n c e 和d t d - m i n e r 支持多文档公共模式的获取， 而且分别代表了 增量式 公共模式获取方法和数据合并式公共模式获取方法。总的说来，这些研究的特点 是: 基于 d t d描述。d d b e , d t d -m i n e r和 x t r 人 c t都是基于获取 d t d的讨 论。但是当前 x ml s c h e m a被广泛应用为 x ml数据模式描述语言，d t d正在被 x m l s c h e m a 取代，需要建立新的基于x m l s c h e m a 的模式获取技术。 1 .处理单 x m l数据文档。在 x m l模式获取研究中大部分是针对单文档处 理，对于多文档模式获取技术研究还不充分。但是 x m l数据大量存在于 i n t e rn e t 上， 逐一 获取每个x m l数据的 模式显 然不 合理， 更何况很多的x m l数据 之间 存 在某种形式的相关性，所以应该提供获取一组x ml数据公共模式的能力。 2 .效率与质量难于兼顾。面对大量无模式的 x m l数据，在顾及模式获取效 率时缺乏对模式质量的保证，事实上模式的质量也不能忽略。本文提出的基于规则 的模式获取方法不仅包含生成规则还包括合并规则和优化规则，使用简单的规则获 取高质量的模式。 第 3 页 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 号1 . 3研究目 标 基于以上的问题背景，研究的目标是如何有效地获取模式相关的 x m l数据集 公共模式。具体目标包含以下几点: 1 .新的获取x ml 数据集公共模式技术路径。 2 .给出获取公共模式的启发式规则及实现算法。 3 .设计及实现旨 在获取x m l 公共模式的原型系统。 1 .4研究内 容 针对研究目标提出合适的公共模式获取技术、给出模式生成规则、模式合并规 则、模式优化规则及算法实现的研究，最后能够基于讨论的技术实现原型系统。 1 . 4 , 1新的模式获取策略 本文的总体目 标是研究如何有效地获取 x m l数据集公共模式，生成的模式应 该符合w3 c的x m l s c h e m a规范描述，且精确、简洁、易阅读。新的方法应该具 有以 下能 力: 1 ) 处理多 个x m l数 据的 能 力。 2 ) 生 成的 模式具 有一 般 性， 表 现为 易于阅读。 3 ) 生成的模式具有准确性， 表现为对于x m l数据的足够的约束力。 4 ) 兼顾获取效率的要求，要求生成规则、合并规则和优化规则实现简单有效。 1 . 4 . 2模式生成规则 x m l数据解析后得到元素标签序列，它们是模式的实例。如果把序列看成标 签组成的字符串，应用上下文无关文法描述的生成规则，可以获取描述元素出现规 律的正则表达式，生成元素的模式。生成规则需要发现元素出现的规律有:重复出 现描述，组出现描述和随机出现描述。 1 . 4 .3模式合并规则 即使是模式相关的 x m l文档，它们独自 生成的模式也不是完全相同的，所以 需要 经过差异消除和 模式 合并处理 得到x m l数 据集的 公 共模式， 相应地就 存在 模 式合并规则，它是生成公共模式的关键之一 设计模式合并规则的基础是模式之间 存在的公共因子表达式。 第4 页 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 1 . 4 .4模式优化规则 模式相关的 x m l数据，独自 生成的模式之间存在重复描述、结构重叠和包含 关系等冗余描述，优化规则消除这些冗余的 模式结构，既保证模式质量也提高了处 理效率。具体地，静态优化保证处理效率，动态优化则保证模式的简洁性。 1 . 4 . 4系统设计 设计出有效的模式获取系统结构，改进利于模式生成的 x ml数据解析和解析 结果的表示和保存方法，研究实现每个规则的算法，以及解析正则式，转换为 x m l s c h e m a 的方法，原型系统能 够支持自 动和手工两种方式工作。 1 . 5研究意义 本文研究的对象是大量存在的无模式 x m l数据，这些数据可能是从传统数据 库中导出的，可能是来自 于w e b ，可能是数据挖掘中生成的，在生成这些 x ml数 据时很难预先设计出合适的模式。通常是使用自 动工具抽取原始信息中感兴趣的信 息，生成 x ml数据，再通过合适的模式获取工具抽取 x ml数据的模式，所以模 式获取技术提供了将这些 x m l数据进行索引、存储、查询和纳入传统数据库管理 的途径，模式获取技术成为信息处理、交换的支撑技术。 在联合作战指挥系统中采用 x m l数据格式表示和保存各类作战文书，利用 x m l数据的结构化特征对各种作战文书分类，设计通用模式，以及利用数据挖掘 工具提取有用信息，提高自 动处理文书的效率。 互 ， s论文结构 论文共五章，其中第一章为绪论，介绍研究背景，研究现状及所存在的不足， 确定课题研究的目 标和研究内容，论述课题研究的重要意义。 第二章给出x m l数据模型， x m l 数据解析技术及关于模式的规范，主要是作 为本文研究的理论基础，以 及简单叙述了 增量式公共模式获取技术和数据合并式公 共模式获取技术。 第三章具体讨论基于模式合并的公共模式获取技术，按照模式获取的过程，从 数据解析到模式生成和模式输出，详细讨论了技术路线中的技术细节及原理，并与 前人的研究进行比较。 第四章依据讨论的模式获取技术，按照原型系统的需求设计和实现 x m l数据 第5页 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 集公 共 模式 获 取系 统 s c h e m a g r a b b e r o 第五章对本文的工作进行总结，并对下一步的工作进行展望。 第6 页 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 第二章x ml数据模型及相关技术 二十世纪九十年代以来，随着i n t e rn e t 及we b的蓬勃发展，在w e b 上出现了大 量的不规则、不完整和易变的数据 ( 如以 h t ml编码的网页) ，采用传统数据模型 处理这类数据较困难，为此，数据库界提出了半结构化的数据模型，并对半结构数 据的访问技术进行了广泛的研究。 x m l数据具有典型的半结构化的特征 ( 如描述 结构的标记与数据保存在一起、数据可能是不规则的以及没有完整的数据类型定义 等) ，因此对这类数据的访问和管理可以借鉴以往在半结构化数据方面的研究成 果。 互 2 . 1半结构化数据 半结构化数据还没有一个统一的定义，但根据它的特点，可以描述如下:半结 构化数据指其结构中隐含变化规则的自 描述数据。半结构化数据具有两大特征:结 构 不 规 则 和结 构隐 含。 研究中 通 常 使 用o e m 6 l 8 ( o b j e c t e x c h a n g e m o d e l ) 表 示 半结构化数据， o e m 表示为一个三元组( l a b e l , i d e n t if i e r , v a l u e ) ， 其中 l a b e l 为一 个字符串， 描述对象的意义; i d e n t if i e : 唯一 标识域中的 对象; v a l u e 可以 是一 个标 量类型的值也可以是对象的集合。 2 0 m 了ogteen 定义 2 . 1 : 1 , 1 2 1 3 . 1 那么从 定义 2 . 2 : 列。 定义2 . 3 : 1 的一个实例。 图 2 . 1 o e m模型 o e m 对象 。的一条标签路径是一个被点分割的标签序列，如 。 出 发可以 遍历一条n 个边的路径， 每个边的标签是i t . o e m 对象 0的一条数据路径是一个被点分割的标签和 o i d交替序 如果d( 数据路径)中的标签序列与标签序列1 相等则数据路径d 是 第7 页 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 2 . 2 x m l 数据描述 根据 x m l 1 .0规范， 一个x m l文档包含一个或多个元素， 其中有一个被称为 “ 根”或文档元素的元素，该元素不出现在其他元素的内容中。一个元素可以有 0 至多个子元素，可以具有字符数据，还可以具有 0至多个属性。元素以 起始标签和 结束标签定界，所有元素必需严格嵌套。因此，除了根元素外，对于每一个元素 c 文档中都有另外一个元素p , c在p的内容中，而不能出现在p的其他子元素中， p 被称为c的父元素。 在形式上， x m l 数据可以映射一个树【 1 9 1 . 定义 2 . 4 : 假定 e为有限标号集合，a 为有限属性名字集合，s指代文本信 息。定义树模型 t= ( v , l a b , e l e , a tt , v a l , : ， l e v e l , o r d e r ) ， 其中， v是结点 集合; l a b 是v到e u a u s 的函 数; e l e 为v 到v 中结点序列的部分函 数，并且 对于任意v e v ， 如果e l e ( v )有定义，则l a b ( v ) e e ; a t t为v x a到v的部分 函数，并且对于任意 v e v , 1 e a ， 如果 a t t ( v , 1 )= v 则 l a b ( v ) c e ，且 l a b ( v )二1 ; v a l为 v到字符串的部分函数，并且对于任意 v e v , v a l ( v )是 字符串当且仅当 l a b ( v ) =s或 l a b ( v ) ca ; r为 t的根，不失一般性，假定 l a b ( r ) = r : 对于任意v e v , l e v e l ( v )为结点v 在t中的深度， 这里结点的 深 度定义为从根结点到达该结点所需的步数;对于任意 v c v , o r d e r ( v )为结点 v 在其兄弟结点中的排列序号。如果v 是有限的则称t 是有限的。 定义2 . 5 : 路径p: : 二e i i i p . p i _ 一， 其中 !为空路径，结点标号i e e u a u ( s ) , “ ， ”为连接符， “ _ ”为匹配任何标号的通配符， “ 一”为匹配任何路径的 通配符。 定义t卜p ( v v , ) 表示存在一条从v ; 到v 2 的路径。 定义 2 . 5 : 定义绝对路径 p为不含 “