（计算机应用技术专业论文）基于xml的web数据抽取与存储的研究.pdf

摘要 摘要 i n t e r 。n e t 的迅速发展使得网络上的信息量大大增加，再给人们提 供方便的同时也加大了人们在网络上查找有用信息的难度。为了帮助 人们从i n t e r n e t 上获得需要的信息，出现了w e b 数据挖掘，而w e b 数据挖掘很重要的一步就是w e b 数据抽取。 本文首先讨论了) 【m l 较其它半结构化模型的优势，以及现有的基 于x m l 的w e b 数据抽取技术，考虑到h t m l 页面的特点，引入了采用 基本项方式描述的页面树，给出了将h t m l 文档转换为x m l 文档的基 于基本项描述方式的多叉页面树的转换方法。该方法基于对h t m l 页 面描述方式、页面结构以及h t m l 标记和格式的分析，建立页面树。 将h t m l 到x m l 的转换转变为页面树到x m l 的转换。按照这个方法开 发的h t m i t o x m l 的原型系统对测试网页基本完成了w e b 信息提取的任 务。 另外本文还对如何将x m l 存储到关系数据库中作了一定研究， 给出了基于0 - r 算法和x m l s c h e m a 的将x m l 映射到关系数据库的 映射规则和主要算法。这样将i n t e r n e t 上的数据经过基于x m l 的数 据抽取和基于关系数据库的存储，使得w e b 挖掘转变成了传统数据 挖掘即数据库中的知识发现，以便于使用多种挖掘方法获得更多有用 信息。 【关键字】x m lh t m l 数据抽取x m l 的存储 北京交通大学硕l 学位沧文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e r a c t ，t h ea m o u n to f i n f o r m a t i o no nt h ew e bh a si n c r e a s e dg r e a t l y t h o u g hi tp r o v i d e sp e o p l e w i t hm a n yf a c i l i t i e s ，i ta l s om a k e si td i f f i c u l tt of i n du s e f u li n f o r m a t i o ni n t h e “d a t as e a ”t oh e l pp e o p l et oa c q u i r ew h a tt h e yw a n tr a p i d l ya n d a c c u r a t e l y ，w e bm i n i n gh a v ee m e r g e d a n do n eo ft h em o s ti m p o r t a n t c o m p o n e n t si sd a t ae x t r a c t i o n i nt h i sp a p e r , w ef i r s td i s c u s s e dt h ea d v a n t a g eo fx m la sas e m i s t r u c t u r e dd a t am o d e la n ds o m ee x i s t i n gx m l - b a s e dw e bd a t ae x t r a i o n t e c h n o l o g y c o n s i d e r i n gt h ec h a r a c t e r i s t i co fh t m lp a g e ，w ei n t r o d u c e d ap a g e t r e eb a s e dc a p i t a l - i t e ma n dg a v et h et r a n s f o r mm e t h o da n d a l g o r i t h m so ft h ec o n v e r s i o n i nt h ef o u n d a t i o no fa n a l y z i n gt h eh t m l p a g ed e s c r i p t i o nw a y 、t h ep a g es t r u c t u r ea n dh t m lt a g ，am u l t i - b r a n c h t r e eo ft h eh t m ld o c u m e n tc a l l e dp a g e - t r e ew a sc r e a t e d ，a n du s i n gt h i s t r e e ，h t m l p a g e sc a nb ec o n v e r t e di n t ox m l d o c u m e n t s i na d d i t i o n ，h o wt os t o r et h ex m ld a t ai n t oar d bb a s e do e x l d ls c h e m aa n do - ra l g o r i t h m sw a sa l s os t u d i e d s ot h ei n t e r n e td a t a c a nb em i n i n gw i t ht r a d i t i o n a la n dm a t u r et e c h n o l o g i e st oo b t a i nm o r e u s e f u lj n f o r m a t i o n k e yw o r d s x m lh t m ld a t ae x t r a c t i o ns t o r ex m l 独创性声明 本人声明，所呈交的学位论文是我个人在导师指导下 进行的研究工作及取得的研究成果。尽本人所知，除了文 中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得北京交通大 学或其他教学机构的学位或证书而使用过的材料。与我一 起工作的同志对本研究所做的任何贡献已在论文中作了 明确的说明并表示了谢意。 本人签名： 日期：年一月一日 关于论文使用授权的说明 本人完全了解北京交通大学有关保留、使用学位论文 的规定，即：学校有权保留送交论文的复印件，允许论文 被查阅和借阅；学校可以公布论文的全部或部分内容，可 以采用影印、缩印或其他复制手段保存论文。论文中所有 创新和成果归北京交通大学计算机与信息技术学院所有。 未经许可，任何单位和个人不得拷贝。版权所有，违者必 究。 本人签名： 日期：年月目 绪论 1 绪论 1 1 研究背景、意义 随着i n t e r n e t 的b 速发展，网e 的数据资源空前丰富。在这些 大量、异构、动态、复杂、开放的信息资源中，蕴含着具有巨大潜在 价值的知识。人们迫切需要能够从w e b 卜- 快速、有效地发现资源和知 识的工具。目前处理w e b 信息的最广泛的手段是搜索引擎。但它只能 提供信息的查找范围而且给出的查询结果大量冗余，查全率、查准率 都不尽人意，还不能发现w e b 资源中所蕴藏的知识。如何利用我们所 面对的w e b 上的大量数据，从中发现有用的知识，使它们为企业的业 务决策和战略发展服务是业界共同的课题。 w e b 挖掘可在多方面发挥作用，如搜索引擎结构的挖掘，搜索引 擎的开发和改进，确定权威页面和引导页面，改进页面排序，w e b 文 档分类，w e b 日志挖掘，智能查询，个性化的信息服务，建赢m e t a w e b 数据仓库等。 在整个w e b 挖掘的过程中非常重要的一步就是w e b 数据抽取，它 是w e b 挖掘的基础。特别是对于w e b 内容挖掘来说，对w e b 网页的内 容进行抽取其意义尤为重要，因为只有在对w e b 数据进行提取之后才 能进行诸如检索等其他工作。 1 2 研究内容 本文讨论了基于x m l 的w e b 数据抽取和x m l 文档的存储，属于w e b 内容挖掘的一个领域。采用的是多层数据库的方法。w e b 上的信息源 可以看作是一个庞大复杂的异构数据库，作为第一层数据库；第二层 j 匕京交通大学硕士学何论文 数据库为通过数据抽取器从w e b 上抽取的x m l 的半结构化数据，最上 层数据库为有一定结构分类的面向数据挖掘的关系数据库。在此之上 进行数据挖掘，即对存储在数据库里的描述网页信息的关系数据使用 传统数据挖掘算法，实现对页面信息的分类。 具体方法是对w e b 上的h t m l 数据进行提取，变换为x m l 的输出， 然后将) ( m l 文档描述与关系数据库中的属性一对应起来，在此之上 再进行w e b 页面的分类等数据挖掘工作。本文首先采用基本项描述方 法，给出了页面树的定义以及建立页面树的步骤，并以页面树为基础 给出了无用节点的去除算法、相似或相同基本项节点合并算法和页面 树的三种节点类型到x m l 的转换算法，完成了h t m l 到x m l 的转换。 其次，研究了x m ls c h e m a 到关系数据库的映射规则和算法。这些为 基于w e b 的数据挖掘做好了准备。 1 3 论文结构 本文的第二章首先介绍了w e b 挖掘的基本理论以及v e b 数据抽取 的重要性。在第三章中介绍了现有的半结构化数据模型和将x m i ，作为 半结构化数据模型的优势，以及x m l 的一些基本知识。在第四章中首 先分析了现有的基于x m l 的数据抽取技术和工具，然后详细讨论了一 种基于基本项描述方式的页面树向x m l 转换的原理、步骤和算法。第 五章讨论了基于x m ls c h e m a 如何将x m i ，文档存储到关系数据库中。 2 w e b 数据挖掘综述 2w e b 数据挖掘综述 2 ，1w e t ) 数据挖掘的定义及其分类 2 1 1 w e b 数据挖掘的定义 w e b 挖掘是一项综合技术，涉及w e b 、数据挖掘、计算机语言学、 信息学等多个领域。不同领域的研究学者对w e b 挖掘的含义有不同的 理解，研究和开发也有其各自的侧重点。例如，计算机语言学家认为 w e b 文档为自然语言理解提供了丰富的语料，可以从中自动的学习词 语的意义，以进行词义辨析或确定浏语所属的概念。一个对w e b 挖掘 的一般定义是： 定义2 1 ：w e b 挖掘是指从大量w e b 文档的集合c 中发现隐含的 模式p 。如果将c 看作是输入，将p 看作是输出，那么w e b 挖掘的过 程就是从输入到输出的一个映射e ：c d 。 一般来讲，w e b 挖掘是指从与w w w 相关的资源和行为中抽取感兴 趣的、有用的模式和隐含信息。 w e b 挖掘从数据挖掘发展而来，因此其定义与我们熟知的数据挖 掘定义类似。但是w e b 挖掘与传统的数据挖掘相比有许多独特之处。 首先，w e b 挖掘的对象是半结构化或无结构的w e b 文档。一般认为， 以w e b 作为中间件对数据库进行挖掘，以及对w e b 服务器上的日志、 用户信息等数据所开展的挖掘工作，仍属于传统的数据挖掘的范畴。 其次，w e b 在逻辑上是一个由文档节点和超链接构成的图，因此w e b 挖掘所得到的模式可能是关于w e b 内容的，也可能是关于w e b 结构的。 此外，由于w e b 文档本身是半结构或无结构的，且缺乏机器可理解的 3 北京交通人学硕十学位论文 语义，而数据挖掘的对象局限于数据库或数据仓库中的结构化数据， 并利用关系表格等存储结构束发现知识，因此有些数据挖掘技术并不 适用于w e b 挖掘，即使可用以必须先对w e b 文档进行预处理，这样开 发新的w e b 挖掘技术，以及对w e b 文档进行预处理得到关于文档的特 征表示，便成为w e b 数据挖掘研究的重点。 2 1 2w e b 数据挖掘的分类 w e b 数据有三种类型： 1 ) w e b 内容数据，如h t m l 标记的w e b 文档； 2 ) w e b 结构数据，如w e b 文档内的超链接； 3 ) 用户访问数据，如服务器l o gf t 志信息。 相应地，w e b 挖掘也分成三类：w e b 内容挖掘、w e b 结构挖掘和w e b 使用记录挖掘”0 1 。如图2 - 1 所示： 圈2 - 1w e b 挖掘的分_ 荚 ( 1 ) w e b 内容挖掘。包括w e b 页的文本信息、多媒体信息以及w e b 上数据库信息等w e b 页面内容进行挖掘，从w e b 文档的内容信息中抽 取知识。w e b 内容挖掘的重点是页面分类和聚类。w e b 内容挖掘使用 的方法通常分为两类：信息查询方法和数据库方法。就其挖掘策略的 不同又可分为：直接挖掘文档内容和在其它工具搜索的基础上进行改 进。 ( 2 ) w e b 结构挖掘。是指对w e b 页面之间的超链结构，w e b 页面 4 w e b 数据挖掘综述 内部结构和url 中的r 录路径结构进行挖掘，从中抽取知识。最常 用的是图论i 斗j 的网络分析法，典型的算法有h i t s ( h y p e r l i n ki n d u c e d t o p i c s e a r c h ) 算法、p a g e r a n k 算法和h i t s 改进算法。这些算法主要 是计算w e b 页面之间的关联程度。w e b 结构挖掘可用于提高网上搜 索引擎搜索结果的准确性，以及挖掘嘲站之间的通讯、相互参引关系 等。 ( 3 ) w e b 使用挖掘【1 3 l 。根据所分析数据的不同分为两类：静态访 问记录挖掘，它分析用户访问留下的日志文件，再对这些统计数据进 行挖掘；动态w e b 访问模式挖掘，例如对一个网站某一时刻不同访 问者的访问路径进行数据挖掘。访问模式的挖掘常使用统计方法研究 抽取词组在文档中出现的规律。通过对文档进行分类、聚类、序列模 式、关联规则、路径分析等数据挖掘技术发现用户的浏览模式。 在完成这些数据挖掘任务时，既需要使用一些与传统k d d 其同 的数据挖掘技术，也使用了一些w e b 挖掘特有的技术。 2 2w e b 数据的特点 w e b 是一个非常成功的基于超文本的分布式信息系统，它涉及新 闻、广告、消费信息、金融管理、教育、政府、电子商务等许多信息 服务。w e b 还包含了丰富和动态的超链接信息，以及w e b 页面的访 问和使用信息，这为w e b 挖掘提供了丰富的资源。 一般来讲，w e b 至少具有以下几个特点： ( 1 ) 对有效的数据仓库和数据挖掘而言，w e b 过于庞大。w e b 的 数据量目前以几百兆兆字节计算，而且仍然在迅速地增长。许多机构 和社团都在把各自大量的可访问信息嚣于w e b 上，这使得几乎不可能 去构造一个数据仓库柬复制、存储或集成w e b 上的所有数据。 5 b 京交通大学硕士学位论文 ( 2 ) w e b 页面的复杂性高于任何传统的文本文档。w e b 页面缺乏 同一的结构，它包含了远比任何一组书籍或其他文本文档多得多的风 格和内容。w e b 可以看作一个巨大的数字图书馆；然而，这图书馆 中的大量文档并不根据任何有关排列次序加以组织。它没有分类索 引，更没有按标题、作者、扉页、目次等的索引。在这样一个图书馆 中搜索希望得到的信息是极具挑战性的。 ( 3 ) w e b 是一个动态性极强的信息源。w e b 不仅以极快的速度增 长，而且其信息还在不断地发生着更新。新闻、股票市场、公司广告 和w e b 服务中心都在不断地更新着各自的页面，链接信息和访问记录 也在频繁的更新之中。 ( 4 ) w e b 面对的是一个广泛的形形色色的用户群体。因特网上连 接了以千万计的工作站，其用户群仍在不断的扩展当中。各个用户可 以有不同的背景、兴趣和使用目的。大部分用户并不了解信息网络结 构，不清楚搜索的高昂代价，极容易在“黑暗”的网络中迷失方向， 也极容易在“跳跃式”访问中烦乱不已和在等待信息中失去耐心。 ( 5 ) w e b 上的信息只有很小的一部分是相关的或有用的。据说9 9 的w e b 信息相对于9 9 的用户来说是无用的。虽然这看起来不是很明 显，但一个人只是关心w e b 上的很小很小一部分信息确是事实，w e b 所包含的其余信息对用户来说是不感兴趣的，而且会淹没所希望得到 的搜索结果。 正是由于w e b 数据的这些特殊之处，w e b 挖掘成为一项极具挑战 性的工作。 6 w e b 数据挖掘综述 2 3w e b 内容挖掘的原理和方法 2 3 1w e b 挖掘的一般过程 般的，w e b 挖掘的基本原理“”可以用图2 2 所示的处理过程表 示，目标数据集就是根据用户要求，从w e b 资源中提取相关数据，w e b 挖掘将主要从这些数据中进行数据提取；预处理是从目标数据集中去 除明显错误的数据和冗余数据，进一步精简所选数据的有效部分，并 将数据转换为有效形式，使得数据挖掘更有效；模式发现是根据任务 要求，选择合适的数据挖掘算法( 选取合适的模型、参数) ，寻求有用 的模型，用一定的方法表达成某些容易理解的形式；模式分析是对发 现的模式进行解释和评估，必要时还需要返回以上处理过程中的某一 些步骤，最后将发现的知识用用户可以理解的方式提供给用户。 1 5 2 - 2w e b l 2 掘过程 本文的研究内容在w e b 挖掘的整个过程中属于数据预处理工作， 主要就是针对w e b 数据抽取的模型、基于该模型的抽取技术和算法以 及如何将抽取出来的数据存储到关系数据库中进行了研究，这些是 w e b 内容挖掘中非常重要的部分，为后期的模式发现做好准备。 2 3 2w e b 内容挖掘常用方法 基于代理的方法 代理技术是从7 0 年代术期发展起来的一项人工智能技术，代理 7 北京交通人学硕士学位论文 可以通过一定的规则模仿人的行为，用以解决人所无法从事的人量的 信息处理工作。与传统的软件不同，代理具有自主性以及学习功能。 基于代理的方法包含了这样的一个人工智能系统：它可以“自主或半 自主地为某个特殊的用户服务，以发现和组织基十w e b 的信息”。一 些智能的w e b 代理可以利用用户描述文件来查找相关的信息，然后组 织和解释这些被查找到的信息。还有一些代理则利用各种信息检索技 术及开放的超文本文档的特性来组织和过滤检索到的信息。另外类 代理被设计成可以学习用户的喜好，并利用这些喜好束为那些特殊的 用户查找资源。代理表示了一个信息检索元素构成的“分布式”网络， 他们可以相互通信，并且无需人的控制。通过作用于每个w e b 服务器 及相互间的通信为终端用户提供查询结果。因此，与数据库中的信息 查询和过滤有所不同，代理构成的网络具有相当大的伸缩性。 基于数据库的方法 主要集中在“对w e b 上的异质的、半结构化的数据进行整合和组 织，使其成为结构化较好的、高层的资源集合”，然后再对这些组织 好的资源进行访问和分析。这些元数据( 或泛化了的数据) 于是可以组 织成有结构的数据集( 如关系数据库或面向对象数据库) ，然后加以 分析。目前的数据库方法又可分为多层数据库方法和w e b 查询系统。 ( 1 ) 多层数据库是由若干层信息构成的数据库。其主要思想是： 信息抽取，将w e b 上无结构或半结构的数据转化为较小的、结构化的 和位置较近的数据库，该数据库中包含了从层次结构的前一层数据库 中抽取出来的信息，随着数据分析、变化及泛化技术的发展，使得把 w e b 上的各种各样的原始信息变换为有一定结构的、分类的和高层的 信息成为可能，其代表了多数据库层次结构中的第二层，而包含原始 8 w e b 数据挖掘综述 的、半结构化信息的w e b 则属r 多层数据库中的第层。如果需要， 则叮以向上建立更多的层次。 ( 2 ) w e b 查询系统利用一个w e b 的简单关系试图，将结构和基于 内容的查询准则以类似于标准的数据库查询语言( 如s q l ) 的方式结合 起来，对w e b 上半结构化的数据进行奄询，此类查询系统中采用的都 是所谓的申明式查、诟j 语言。从w e b 上查询半结构化的数据需要两个阶 段，首先通过生成一个关联数据库来实现w e b 的关系结构，紧接着进 行关键字查询及创建用于把文档特征映射为数据模型中的实例( 如图 或表) 的外壳。目前已有多种w e b 查询系统，如：w 3 q i 、w e b l o g 、w e b s q l 及w e b o q l 。 2 4w e b 数据挖掘的用途 通过w e b 数据挖掘，可以获到以下的信息： ( 1 ) 用户的生活模式、爱好、购买频率、所属的用户群； ( 2 ) 不同用户群的共同特征； ( 3 ) 页面的访问情况； ( 4 ) 广告的点击情况； ( 5 ) 页面文本内容的基本信息； 应用可视化工具或通过相应的w e b 数据仓库工具对挖掘出的规律 和模式进行评价和验证后，进而可以对证实的结论和模式加以应用， 主要有以下几个方面“： ( i ) 信息反馈和广告发送； ( 2 ) 对广告设置的修改、改进页面排序 ( 3 ) 网站结构设计的修正； 9 北康交通人学硕十学位论文 ( 4 ) 对用户定制个性化的信息服务 ( 5 ) 搜索引擎的开发和改进； ( 6 ) w e b 文档分类； ( 7 ) 智能查询。 1 0 、f 结构化数据模犁 3 半结构化数据模型 3 1 现有的半结构化数据模型 数据库中的数据具有清晰的结构，这些数据可以被称为结构化数 据。但是许多多媒体数据( 比如声音、图像等的数据流) 几乎是完全无 结构的，被称为非结构化数据。而w e b 数据由于同时具有某些结构化 与非结构化的特征，被称为半结构化数据。w e b 上的半结构化数据的 特点已经在第二章中有了详细介绍。由于没有强制性模式的限制，半 结构化数据具有很大的灵活性，能够满足网络这种复杂分布环境的需 要，但同时也给数据处理带来了很大的困难“。关系型数据库使用二 维表作为数据模型，s q l 语占作为数据查询语言，d b m s 作为数据存 储和管理工具。同样，半结构化数据的也具有自己独特的数据模型、 查询语言和存储管理工具。现有的半结构化数据的数据模型有两种主 要的描述方式： 基于图描述形式的数据模型，例如s t a n f o r d 大学提出的o e m ( o b j e c te x c h a n g em o d e l ) 模型。 基于逻辑描述形式的数据模型，例如w e bl o g 提出的类d a t a l o g 语言。 在半结构化数据的查询语言研究方面，研究者参考了传统数据库 查询语言的设计思想，设计出类似关系数据库的类s q l ( s t r u c t u r e d 蚰e r yl a n g u a g e ) 查询语言，或者类似面向对象数据库的类 o o l ( o b j e c tq u e r yl a n g u a g e ) 查询语言。s t a n f o r d 大学的研究者还设 计了一个半结构化数据库系统l o r e ，这个系统可以存储和管理来自异 北京交通大学硕士学位论文 构数据源的半结构化数据。 国内的研究者也对半结构化数据模型进行了许多研究。复旦大学 的研究者设计了一个无模式的自描述简单对象模型的半结构化数据 模型s d o m 和基于其上的查询语言s d o q l ”，东南大学的研究者设计了 一个基于带根连通有向图的半结构化数据模型o i m 和基于其上的查询 语言o i q i 。”“。 下面分别介绍基于图和基于逻辑的数据模型原理。“。 3 1 1 基于图描述形式的数据模型 1 基于图描述形式的数据模型一般原理 在基于图的描述形式中，半结构化数据通常用带边标记的有向图 来表示。图3 1 是一个o e m 的数据图的例子，图3 - 2 是对应于图3 - 1 的数据图的一个可能的模式图。模式图中的边可以用简单类型的数据 标记( 如i n t 、c h a r ) ，也可以用其他的复杂类型来标记( 如n a m e 、d a t e ) 。 边也可以有名字，这样的边我们称为符号( s y m b o ) ，它在内部是用字 符串来表示的。模式图中的节点可以加一定的注释，表明其代表的语 义或其他特定的含义。这样的标记树可以用公式表示： t y p el a b e1 = i n ts t i n gf s y m b o l t y p et r e e = s e t ( 1 a b e l t r e e ) 第一行定义了标签的类型，第二行递归的定义了树是一个标签和 树对的集合。这个基本的模型可以根据具体情况作形式上的变化。 采用图来表示模式要研究的问题是：如何判断数据实例是否符合 模式图：以及如果数据图符合模式图，如何得到数据图中的对象与模 式图中的类型之间的对应关系。目前就这两个问题的研究是基于相似 半结构化数据模犁 脚e r 众b o o kp a p e r 脚 a l lc a 2 b l 图3 - l 数据图 b 2 n a f a u t h , p f i c e l a 8 】a 9。a 1 0 图3 - 2 模式图 表3 - 1 数据图和模式图的相似关系 d a t an o d es c h e m an o d e r 1r o o t & p l 、& p 2p a p e r b l 、b 2b o o k a l 、a 2 、a 3 、a 4 、a 5 、a 6 、a t o m i c a 7 、a 8 、a 9 、& a 1 0 s i m u l a t i o n 的概念进行的。相似就是两个图g l 和g 2 节点之间的一个 1 3 胁i 胁 呼八枷 。 躺 甲 ， 妒、 埘八1 北京交通大学硕十学位论文 关系，这种关系下g l 中的每条边在g 2 中有一条对应的边。具体到数 据图和模式图时，可以按特定的关系束对应，如数据图的根节点对应 于模式图的根节点，原子对象必须对应于原了类型等。如果在数据图 和模式图之间存在满足上述定义的相似关系，就可以认为数据图符合 模式图，而在相似关系中两个图的节点之间的对应关系就是数据对象 和类型的对应关系。表3 1 给出了图1 和图2 之间的相似关系。例如 r 1 和r o o t 类型有相似关系，那么，数据图中从& r l 发出的边 p a p e r ( r 1 ，& p 1 ) 、p a p e r ( & r l ，& p 2 ) 对应于模式图中从r o o t 发出的 边p a p e r ( r o o t ，p a p e r ) ，而且p l ，& p 2 与p a p e r 也有相似关系，从 r 1 发出的标记为“b o o k ”的边的相似情况以此类推。 在图模式的研究领域中，关于相似的判断算法、同数据图所符 合的多个模式之间的关系及可运算性等都是备受关注的研究方向。 2 基于图描述形式的数据模型 采用图描述形式的数据模型有很多种，他们都是以标记域为基础 的。如标记文件系统( t a g e df i l es y s t e m ) ”使用标签代替位置来表 示域，这种方法适用于记录包含大量空域的情况；l o t u sn o t e s “使 用标签一值模型来表示办公文档等等。随着面向对象技术的发展，人 们开始应用面向对象的数据模型来解决异构数据库的集成问题，出现 了各种面向对象的数据模型。 由于半结构化数据一般采用带标记的有向图来表示，所以这种描 述形式的一个显著优点是模式和数据采用同一种数据模型( 图模型) ， 非常便于处理。模式图通常是一个有根、边上带标记的有向图，其边 卜的标记可以与数据图相同，也可以加以扩充，如允许类似于“n a m e i a d d r e s s ”的形式，或采用特定形式的规则( 如一元谓词) 等等。对模 、r 结构化数据模型 式图中的节点，可以加以一定的注释，表明其代表的语义或其它特定 的含义，其中最有代表性的是o e m 。基丁o e m 模型的数据抽取方法是 将页面中各个部分表示为对应的o e m 对象。文献 3 6 研究的结构化和 半结构化信息抽取就是基于o e m 模型和启发式规则的。 此外，还有概念模型。通过一个自然简单的方法，了解h t m l 页 面的内部结构。它不同于o e m ，而类似于人对文档的概念化。它提供 虽然很少却十分有效的高层结构，用于描述文本的内容( 如通过引入 l i s t 对象解决了图、树描述方法所不能解决的l i s t 表问题) 。另有一 套相应的规则，把内容自动映射到概念模型中。但到目前为止，还没 有相应的查询语言。 3 1 2 基于逻辑描述形式的数据模型 在已经提出来的半结构化数据模型的描述形式中，基于逻辑的描 述形式包括：一阶逻辑( f i r sl o r d e rl o g i c ) 、描述逻辑( d e s c r i p t i o n l o g i c ) 、及d a t a l o g 等，它们之问很相似，只是在表达能力上有所差 别。其中比较典型的是基于d a t a l o g 的模式描述形式。 d a t a lo g 是一种数据库语言，也可以看作是基于逻辑的一种数据 模型，并且这种数据模型的模式也是由d a t a l o g 来定义的。采用 d a t a l o g 规则来描述半结构化数据模型，所给出的模式定义就是一组 d a t a l o g 规则。下面用一个例子进行描述。 假设我们要定义3 种数据类型的对象： r o o t 类型：有标记为“p a p e r ”的边指向p a p e r 类型的对象，标 记为“b o o k ”的边指向类型为b o o k 的对象： p a p e r 类型：有标记为“b e l o n gt o ”的边指向类型为b o o k 的对 北京交通大学硕十学位沧文 象，有标记为“n a m e ”“a u t h o r ”的边指向类型为s t r i n g 的原子对象， 还有来自r o o t 类型和b o o k 类型的相应标记的入边。 b o o k 类型：有标记为“i n c l u d e ”的边指向类型为p a p e r 的对象， 有标记为“n a m e ”“a u t h o r p r ic e ”的边指向类型为s t r i n g 的原子 类型，并还有来自r o o t 类型和p a p e r 类型的入边。 这三个类型可用下面一组d a t a l o g 规则来描述： r o o t ( x ) ：r e f ( x ，p a p e r ，y ) p a p e r ( y ) ，r e f ( x ，b o o k ，z ) ，b o o k ( z ) p a p e r ( x ) ：b o o k ( z ) ，r e f ( z ，i n c l u d e ，x ) ，r e f ( x ，b e l o n gt o ， u ) ，b o o k ( u ) ，r e f ( x ，n a m e ，n ) ，s t r i n g ( n ) ，r e f ( x ，a u t h o r ，p ) ， s t r i n g ( p ) b o o k ( x ) ：p a p e r ( z ) ，r e f ( z ，b e l o n gt o ，x ) ，r e f ( x ，i n c l u d e ， e ) ，p e r s o n ( e ) ，r e f ( x ，n a m e ，n ) ，s r i n g ( n ) ，r e f ( x ，a u t h o r ，a ) ， s t r i n g ( a ) ，t e l ( x ，p r i c e ，b ) ，s t r i n g ( b ) 。 这里的每条规则对应于一个类型定义。这种描述形式也可以等价 的用一阶逻辑来表示，如上述对p a p e r 类型的规则定义等价于以下的 一阶逻辑： 一p a p e r ( x ) z ( r e f ( z ，i n c l u d e ，x ) ( b o o k ( z ) ) a y ( r e f ( x ，b e l o n g t o ，y ) 八( b o o k ( y ) ) a n ( r e f ( x ，n a m e ，n ) a s t r i n g ( n ) ) 八p ( r e f ( x ， a u t h o r ，p ) 八( s t i n g ( p ) ) 对于类型定义规则的集合，要考虑另外个问题，就是如何确定 数据对象与类型的从属关系。可以采用的是最大不动点( t h eg r e a t e s t f i x p o i n t ) 理论，从包含咀后的知识和所有可能的类型划分的模型出 发，计算出他的最大不动点，这样就得到了一个对数据对象的类型划 分。 半结构化数据模型 w e b 数据抽取通常都是建立在半结构化数据模型及其抽取技术基 础上的，不过这并不是唯一的w e b 数据抽取的方法。文献“1 中就是通 过使用关键字、模式和样本来提取想要的信息。 3 2 x m l 简介 3 2 1x m l 的起源和发展 x m l ( e x t e n d e dm a r k u pl a n g u a g e )是从s g m l ( s t a n d a r d g e n e r a l z e dm a r k u pl a n g u a g e ) 进化来的，s g m l 最初是由i b m 开发 的一种用于排版的符号化语言，于1 9 8 6 年成为国际标准规范 ( i s 0 8 8 7 9 ) 。 s g m l 是为了解决文档及其格式问题的一种标记语言，非常的复杂 和难以使用。因此，8 9 年欧洲物理量子实验室( c e r n ) 的信息专家蒂 姆伯纳斯李( t i mb e r n e r s l e e ) 依据8 g m l 丌发出 h t m l ( h y p e r t e x tm a r k u pl a n g u a g e ) ，它能轻松地将。一个文件中的文 字或图形连到其它的文件中去。1 9 9 1 年，李定义了h t m l 语言的第一 个规范，之后成为w 3 c 组织为专门在互联网上发布信息而设计的符号 化语言规范。而h t m l 的d t d 作为标准被固定下来，因此h t m l 不能作 为定义其它符号化语言的元语言。 随着计算机的应用水平大幅的提高，人们已经对h t m l 开始不满， 因此又开始对其进行修改、升级，同时d h t m l ( 动态) 、v h t m l ( 虚拟) 、 s h t m l 等也飞速发展起来。但是因为h t m l 本身的缺陷，为了解决更多 的问题，x m l 出现了。x m l 是由w 3 c 于1 9 9 8 年2 月发布的一种标准。 它同样是s g m l 的一个简化子集，它将s g m l 的丰富功能与h t m i 。的易 北京交通大学硕士学位论文 用性结合到w e b 的应用中，以。种开放的、自我描述方式定义了数 据结构。在描述数据内容的同时能突出对结构的描述，从而体现出数 据之间的关系。这样所组织的数据对于应用程序和用户都是友好的、 可操作的。 严格地讲，x m l 也还是s g m l 。与h t m l 不同的是x m l 有d t d ，因而 也可以像s g m l 那样作为元语言来定义其它文件系统，或称其它符号 化语言。如果把符号化语言分为元符号化语言和实例符号化语言的 话，s b m l 和x m l 都是元符号化语言，而h t m l 和由x m l 派生的x h t m l 都是实例符号化语言。 x m l 近来逐渐成为因特网上数据表示和数据交换的新标准。它迅 速的被应用于科学数据( 如d n a 序列) ，语言，和电子商务等领域( 如 电了数据交换e d i ) 。x m l 的基本思想是：用标记表示数据的意义， 而不是像h t m l 仅仅用来规定数据的显示方式。x m l 将内容和形式相分 离具有很重要的意义：那些将数据以x m l 格式编码的w e b 服务和应用 程序可以迅速地以一种简单、有效的格式提供这些数据信息，这些w e b 服务和应用程序之间也可以很容易地进行交互；并且可以通过x s l 等 对同一数据内容提供多种数据表示形式。x i d l 突破了t t t i d l 的固定标记 集合的约束，用户可以根据需要定义任何一种标签来描述文档中的数 据元素。 3 2 2x 札的主要特点 x m l 具有简单性、可扩展性、互操作性、开放性、面向对象的特 性等特点： ( 1 ) 简单性 r 结构化数据模型 x m l 的严格定义和规则集，是人和机器都能更容易地阅读文档。 x m l 文档建立在斌本嵌套结构的基础之上，当新的细节被增加，结构 越来越复杂时，i ：发人员不需付出很大代价来表示复杂的结构。 ( 2 ) 扩展性和灵活性 开发者可以创建自己的d t d 或s c h e m a ，为不同的应用定制1 i 同 的标记集。这是因为x m l 是数据和格式分离设计的，所以x m l 元 数据文件就是纯数据的文件，这样就可以使用同一个数据源，显示多 种样式了。x m l 采用的t a g 是自己定义的，这样我们的数据文件的 可读性就能大大提高，也不再局限于h t m l 文件那些标准的t a g 了。 ( 3 ) 操作性 x m l 可以在多种平台上使用。并且文档的结构是相容的，所以分 析文档的解析器可以很容易的建立。为x m l 具有到目前为止其他方法 所不具备的数据描述特点，控制信息不是采用应用软件的独有形式， 而是采用谁都可以看得懂的标记形式来表现，所以x m l 可以作为电子 数据交换的统一格式。 ( 4 ) 开放性 结构良好的x m l 文档可以被容易的进行语法分析。即使各个公 司建立特定的x m l 应用，但x m l 中的数据可以被其他的应用使用。 f 5 ) 面向对象的特性 x m l 的文件是以树状方式存储，同时也有属性，这非常符合面 向对象方面的编程，而且也体现了以对象方式存储，o r a c l e 数据库 就使用了这种面向对象的特性，但是o r a c l e 数据库的根本是关系 型的数据库，因此速度和稳定性都有一定的问题，而且特别的复杂， 所以大家基本上是很少使用它的这一特性。 1 9 北京交通大学硕士学位论文 世界上永远也不会h 现完美的语言的，x m l 也是样，它也有 很多的缺陷。x m l 是一种数据描述的技术。x m l 文件的显示、文件 结构的变更、应用程序的操作等x m l 相关技术是非常必要的；虽然 x m l 是树状存储的，搜索的效率极高，但是它的插入和修改比较繁 琐。 3 2 3x 札的逻辑结构、语法、模式 1 x m l 的逻辑结构 一个x m l 文件最基本的构成是： 一个简单的x m l 文件 e l l i o t t er u s t yh a r o l dew s c o um c a n s x i a o l i n gk o n g & y a n l is h a n g x m li nan u t s h e l l 创建x m l 文档必须遵守下列重要规则“： 规则1 ：必须有x m l 声明语句 声明( d e c l a r a t i o n ) 也称p r o l o g ( 前言) 是x m l 文档的第一句，其 格式：为：( ? 舭v e r s i o n = ”1 0 8s t a n d a l o n e = ”y e s n o ”e n c o d i n g = u t f 一8 4 7 声明的作用是告诉浏览器或者其它处理程序：这个文档是x m l 文 档。语句中的v e r s i o n 表示文档遵守的x m l 规范的版本；s t a n d a l o n e f 结构化数据模犁 表示文档是否附带d t d 文件，如果有，参数为n o ：e n c o d i n g 表示文 档所用的语言编码，默认是u t f8 。 规则2 ：是否有d t d 文什 有的文档带有d t d 文件。d t d 文件的声明语句紧跟在x m l 声明语 句后而。格式如下： 规则3 ：注意大小写 在x m i ，文档中，大小写是有区别的。 和 是不同的标识。注 意在写元素时，前后标识大小写要保持一致。 规则4 ：属性值加引号 在h t m l 代码里面，属性值可以加引号，也可以不加。例如： w o r d 就可以被浏览器正确解释。但是在x m l 中则 规定，所有属性值必须；b r i g i 号( j 以足单引号，也可以是双引号) ，否 则将被视为错误。 规则5 ：所有的标签必须有相应的结束标签 在h t m l 中，标识可能不是成对出现的，比如： 。而在x m l 中规定，所有标识必须成对出现，有一个开始标识，就必须有一个结 束标识。否则将被视为错误。 规则6 ：所有的标签，包括空标签必须被关闭且标签不能交叉 空标签就是标签对之间没有内容的标签。比如 ， 等标 识。在x m l 中，规定所有的标签必须表示为一个起始标签紧跟一个结 束标签或空元素标签。针对这样的空标签，x m l 中处理的方法是在原 标签最后加，就可以了。例如： 应写为 ；标签的顺 序也不能交叉，这和h t m l 不同。x m l 所有的元素排列必须是严谨的树 状结构。否则就会出错。 2 1 北京交通大学硕士学位论文 2 x 札的语法 ( 1 ) 元素与属性 标签( t a g ) 实际上包含了两部分：元素( e l e m e n t s ) 和属性 ( a t t r i b u t e s ) 。在表3 1 中最高层的元素是n o t e ，称作“根元素( o o t e l e m e n t ) ”，元素a u t h o r 、t r a n s l a t e 、n a m e 是母元素b o o k 底下的子 元素。 每