（计算机软件与理论专业论文）基于xml面向web的数据抽取技术研究.pdf

摘要 随着近几年i n t e m e t 的飞速发展，信息量呈指数式增长。怎样从大量信息的w e b 中 抽取出有用的数据成为现今的研究热点。因此，本论文对现在的w e b 数据抽取技术进行 研究。 论文首先提出一种基于二叉树的h t m l 向x m l 的转换方法，有效地将h t m i 墙式 转换为x m l 格式。简化了数据抽取工作，为后面的抽取数据作了铺垫。其次对数据映 射进行分析，研究用x s l 皮档将x m l 数据进行映射。经过研究表明此方法对x m l 数据 源映射为需要的x m l 数据文件是最优的。再对x m l 数据集成进行分析，提出了x m l 数据的存储，尤其是数据库的存储。同时还提出了基于x m l 的w e b 查询模式，为整个 信息抽取工作的后期数据集成提供了很好的支持。 最后根据所做的研究结合数据抽取技术、x m l 技术和n e t 技术，提供了一个快速、 通用的基于x m l 的w e b 数据抽取原型系统。 关键词：数据抽取二叉树x s l x p a t h 原型系统 a b s t ra c t a l o n gw i t ht h er a p i dd e v e l o p m e n to fi n t e r n e t ，t h em a s so fi n f o m a t i o nh a v ei n c r e a s e di n e x p o n e n t i a lm o d e l h o wt oe x t r a c td a t af r o mw e ba p p l i c a t i o nh a sb e e nt h eh o t s p o to f n o w a d a y sr e s e a r c h s o ，t h i sp a p e rr e s e a r c h st h ee x t r a c t i o no fw e bd a t a f i r s t l y ，t h i sp a p e rb r i n g sf o r w a r dac o n v e r s i o nm e t h o do fh t m lt ox m l , e f f e c t i v e l y c o n v e r s i n gt h ep a t t e r no fh t m lt op a t t e r no fx m l rs i m p l i f y st h ew o r ko fd a t a e x t r a c t i o n a n dm a k e st h em a t t i n gf o rt h el a t t e rw o r k s e c o n d l y ，i th a sa n a l y z e dt h ed a t a r e f l e c t i o n ，r e s e a r c h su s i n gt h ex s ld o c u m e n tt or e f l e c tt h rx m ld a t a a sar e s u l tt h er e s e a r c h i n d i c a t et h es u p e r i o r i t yo ft h i sm e t h o d ，w h i c hr e f l e c t st h ex m ld a t as o u r c et ot h en e e d e d x m ld a t af i l e f i n i a l l y ，t o a n a l y z et h ex m ld a t a s e t ，i tb r i n g su pt h es t o r a g eo fx m l d a t a , e s p e c i a l l yt h es t o r a g eo fd a t a b a s e m e a n w h i l ei ta l s or a i s e st h em o d eo fw e bq u e r y b a s e do nx m l , t om a k eag o o ds u p p o r tf o rt h el a t e rs t a g eo fw h o l ee x t r a c t i o nw o r ka n d i n t e g r a t i o n a tl a s t ，b a s eo nt h ea l lr e s e a c h ，c o m b i n et h ed a t ae x t r a c t i o n ，x m lt e c h n i q u ea n d n e t t e c h n o l o g yt od e s i g nar a p i d ，c o m m o nu s i n gw e bd a t ae x t r a c t i o ns y s t e mb a s e do nx m l k e yw o r d s ：d a t ae x t r a c t i o nb i n a r yt r e ex s lx p a t h p r o t o t y p es y s t e m 长春理工大学硕士学位论文原创性声明 本人郑重声明：所呈交的硕士学位论文，基于x m l 面向w e b 的数据抽取技术研 究是本人在指导教师的指导下，独立进行研究工作所取得的成果。除文中已经注明 引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识 到本声明的法律结果由本人承担。 作者签名：茧型建垒幽年三月旦日 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学硕士、博士学位论文版权使用 规定，同意长春理工大学保留并向中国科学信息研究所、中国优秀博硕士学位论文全 文数据库和c n k i 系列数据库及其它国家有关部门或机构送交学位论文的复印件和电 子版，允许论文被查阅和借阅。本人授权长春理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编 学位论文。 作者签名：i 氢硷型奎 2 竺鱼字年立月望日 指导导师签名：季立羔鱼尊年立月丛日 第一章绪论帚一早三百下匕 1 1 课题研究背景 随着i n t e r n e t 及其相关技术的飞速发展，信息发布与传播变得非常简便和迅速。w e b 也因此成为人们最大的信息和知识来源，堪称有史以来最为成功的网上“百科全书”。 怎样对w e b 上大量的数据信息进行数据抽取成了现今数据挖掘研究的热点。w e b 数据抽 取技术研究的是如何获取存在于w e b 上的数据。众所周知，w e b 以h t m l 网页为主要形 式存在于因特网上，是因特网上最流行、使用最广泛的服务形式。而且，因为基于h t m l 语言所编写的网页具有简单、容易传输、标准开放、查看与编写工具广泛存在等一系 列特点，所以因特网上主要的数据都以h t m l 网页的形式存储和传播。因此，如何获 取存在于w e b 上的数据，很大程度上是如何获取存储在h t m l 网页形式中的数据的问 题。w e b 数据抽取问题所主要研究的即是如何从h t m l 网页中抽取结构化或半结构化的 数据。 w e b 数据抽取是十分具有实际应用价值和研究价值的，任何试图利用w e b 数据进行 生产或者研究的项目必然先遇到w r e b 数据抽取的问题，因此近几年来各种w e b 数据抽取 的相关研究工作大量出现在各种学术会议、期刊杂志中。这些工作涵盖了人工智能、 数据挖掘、数据库和信息检索等多个领域，一方面证明了其实际价值，一方面也证明 了完全解决这个问题的难度。 必须承认的是，w e b ( 主要是h t m l 网页) 本身的无结构化，或者半结构化，使得 任何在之上的研究工作必然面临语义这个难题，然而可以依赖于数据库技术，找到一 些解决方法。基于数据库技术的w e b 数据抽取技术研究经过了人工、半自动化和自动化 方法三个阶段。人工方法通过程序员人工分析出网页模板，借助一定的编程语言( 例 如j a v a 、n e t 这样的适合处理h t m l 文件的程序编写语言) ，来针对具体的问题生成具体 的包装器。半自动化方法中，应用网页模板抽取数据生成具体包装器的部分被计算机 接管，而网页模板的分析仍然需要人工参与。自动化方法中，网页模板的分析部分也 交给了计算机进行，仅仅需要很少的人工参与( 例如检查结果进行校准) 或者完全不 需要人工参与，因而更加适合大规模、系统化、持续性的w e b 数据抽取。近年来，研究 者更加倾向于自动化方法。 1 2 国内外研究现状 1 2 1 国外研究现状 2 0 世纪6 0 年代中期，从自然语言文本中获取结构化信息的研究，被看作是信息抽 取技术的初始研究，它以两个长期的、研究性的自然语言处理项目为代表i 1 1 美国纽约大学开展的l i n g u i s t i cs t r i n g 项目2 1 开始于6 0 年代中期并一直延续到8 0 年代。该项目的主要研究内容是建立一个大规模的英语计算语法，与之相关的应用是 从医疗领域的x 光报告和医院出院记录中抽取信息格式，这种信息格式实际上就是现 在所说的模板。 另一个相关的长期项目是由耶鲁大学r o g e rs c h a n k 及其同事在2 0 世纪7 0 年代开 展的有关故事理解的研究。由他的学生g e r a l dd ej o n g 设计实现的f r u m p 系统口1 是根据故事脚本理论建立的一个信息抽取系统。该系统从新闻报道中抽取信息，内容 涉及地震、工人罢工等很多领域或场景。该系统采用了期望驱动与数据驱动相结合的 处理方法。这种方法被后来的许多信息抽取系统采用。 从2 0 世纪8 0 年代末开始，信息抽取研究蓬勃开展起来，这主要得益于消息理解 系列会议( m u c ，m e s s a g eu n d e r s t a n d i n gc o n f e r e n c e ) 4 1 的召开。正是m u c 系列会议 使信息抽取发展成为自然语言处理领域一个重要分支，并一直推动这一领域的研究向 前发展。 1 9 8 7 年开始到1 9 9 8 年，m u c 会议共举行了七届，它由美国国防高级研究计划委 员会( d a r p a ，t h ed e f e n s ea d v a n c e dr e s e a r c hp r o j e c t sa g e n c y ) 资助。m u c 的显著特 点并不是会议本身，而在于对信息抽取系统的评测1 5 1 0 只有参加信息抽取系统评测的 单位才被允许参加m u c 会议。在每次m u c 会议前，组织者首先向各参加者提供样例 消息文本和有关抽取任务的说明，然后各参加者开发能够处理这种消息文本的信息抽 取系统。在正式会议前，各参加者运行各自的系统处理给定的测试消息文本集合。由 各个系统的输出结果与手工标注的标准结果相对照得到最终的评测结果。最后才是所 谓的会议，由参与者交流思想和感受。后来，这种评测驱动的会议模式得到广泛推广， 如1 9 9 2 年开始举行的文本检索会议t r e c 等。 就在这个时候，南加州大学信息科学研究正在研究w e b 数据挖掘，并且研制一个 信息集成系统，其特点是发展和应用了多种人工智能技术，访问各类信息源，构造了 一个智能的动态接口。其认为h t m l 具有严谨的结构，如层次树型结构，它采用元组 列表的形式来表达半结构化的信息。元组列表带有明确的分隔符以区分不同的元素。 为了描述文档的结构，其设计了一种叫做嵌入式目录的表达形式，用于表达半结构化 文档的信息。其中，树叶代表将被提取的信息，每一个内节点代表一个同构列表( 如一 个名字的列表) 或一个异构元组( 如一个包含姓名、地址和序列号码的三元组) ，对待提 取项目的识别被认为是一个对树的搜索过程，搜索状态的改变依据是各个节点处的路 标，路标的不同值导致搜索转向不同的分支，生成的规则以一种路径表达式的形式给 出。 美国斯坦福大学的j h a m m e r 等人开发了一个信息提取工具强1 ，从w e b 上提取半结 构化的信息。它主要是基于网页的结构，准确率高，但是对不同的结构需要不同的抽 取规则文件，而且定义规则文件非常繁琐，不具有通用性。 1 。2 2 国内研究现状 2 0 0 0 年以后，国内把x m i _ 和数据挖掘结合起来的研究逐渐增多，由于x m l 广泛应 2 用于w e b 上，因此基于x m l 的w e b 挖掘( w e bm i n i n g ) 的研究越来越受到重视，研究的 w e bm i n i n g 包括w e b 内容挖掘、w e b 结构挖掘、w e b 使用挖掘。现在x m l 正在成为 i n t e r n e t 上数据描述和交换的标准，并且在将来x m 啪代替h t m l 而成为w e b 上驻留数 据的主要格式，为了将现有的w e b 网页转换为x m l 3 之档，已提出t w m a ( w e bm i n i n g a g e n t ) 系统，现今普遍认为的数据挖掘形式可以分为知识发现和预言挖掘两大类，上述 绝大部分文献在研究基于x m l 的数据挖掘应用时，往往只注意到了x m l 在w e bm i n i n g 方面的应用，这只是一种基于x m l 支：档的知识发现。而对于x m 魄数据挖掘预言模型 中的应用研究的不是太多。x m 陇数据挖掘预言模型中的主要应用是p m m l ( p r e d i c t i v e m o d e lm a r k u pl a n g u a g e ) ，它是一种基于x m l 的语言，用来对数据挖掘预言模型进行描 述和定义。它是由国际化组织数据挖掘工作组( d a t am i n i n gg r o u p ，简称d m g ) 提出的， 它描述了大量不同的模型，包括预言模型、聚集和关联规则等。 国内一些科研单位在某些领域范围内也对信息提取进行了研究。例如，地壳垂直 运动信息提取，海岸带环境遥感信息提取等等。在w e b 信息抽取和集成方面则由于w e b 信息非常复杂，信息量也非常大，这使得面向整个i n t e m e t 的信息抽取和集成难度大， 所以研究w e b 信息抽取和集成的单位很少，即使对其进行研究也大多仅限于特定领域 信息的抽取和集成。 根据自动化程度可以将w e b 信息抽取分为人工方式的信息抽取、半自动化方式的 信息抽取和全自动化方式的信息抽取三大类。 根据各种工具所采用的原理不同可以将w e b 信息抽取分为基于自然语言处理方式 的信息抽取、包装器归纳方式的信息抽取、基于o n t o l o g y 方式的信息抽取、基于h t m l 结构的信息抽取和基于w e b 查询的信息抽取 1 。 ( 1 ) 基于自然语言处理方式的信息提取 这类信息提取主要适用于源文档中包含大量文本的情况( 特别针对于合乎文法的 文本) ，在一定程度上借鉴了自然语言处理技术，利用字句结构、短语和字句间的关系 建立基于语法和语义的提取规则实现信息提取。目前采用这种原理的典型系统有 r a p i e r 、s r v 和w h i s k 。 ( 2 ) 包装器归纳方式的信息提取 包装器归纳方式的信息提取根据事先由用户标记的样本实例应用机器学习方式的 归纳算法，生成基于定界符的提取规则。其中定界符实际上是对感兴趣语义项上下文 的描述，即根据语义项的左右边界来定位语义项。目前采用这种原理的典型系统有 s t a i k e 、s o f t m e a i ，y 和w i e n 。 ( 3 ) 基于o n t o l o g y 方式的信息提取 基于o n t o l o g y 方式的信息提取主要是利用对数据本身的描述信息实现数据提取，对 网页结构的依赖较少。目前采用这种原理的典型系统有b y u ( b f i g h a r ny o n gu n i v e r s i t y 信息提取小组开发的信息提取工具) 、q u i x o t e 。 ( 4 ) 基于h t m l 结构的信息提取 3 基于h t m l 结构的信息提取技术的特点是根据w e b 页面的结构定位信息，在信息提 取之前通过解析器将w e b 文档解析成语法树，通过自动或半自动的方式产生提取规则， 将信息提取转化为对语法树的操作实现信息提取。目前采用这种原理的典型系统有 i ，i x t o 、x 佩a p 、r o a d r u n n e r 和w 4 f 。 ( 5 ) 基于w e b 查询的信息提取 由于上述的信息提取技术，采用了不同的原理，提取规则的形式和感兴趣信息的 定位方式也各不相同，因此均不具有通用性。基于w e b 查询的信息提取和它们最大的 不同之处在于它将w e b 信息提取转化为使用标准的w e b 查询语言对w e b 文档的查询，具 有通用性。目前采用这种原理的典型系统有w e b o q l 和p o a g e n t 。 不同的提取工具有其不同的实现方式，对不同的w e b 网页也有不同的提取效果和 效率，其优点也各有不足。 1 3 课题研究的目的及意义 当前，w e b 是世界上最丰富和最密集的信息来源，h t m l 噶1 ( h y p e r t e x tm a r k u p l a n g u a g e ) ，是w e b 上信息的主要载体。无论在公司、政府机构、还是个人，w e b 和它 最初用以表达信息的方法，h t m l 都获得了圆满的成功。然而，h t m l 并不完美，它的 缺点包括： ( 1 ) h t m l 只是一种表达技术，不能揭示m m 珠记的含义9 1 。 ( 2 ) 标准的h t m l 规定了固定数据的标签集合，不允许用户定义自己的扩展标签。 ( 3 ) h t m l f 吏得服务器端要处理的数据量过大。 ( 4 ) 标准的h t m 珠记对于表现w e b 页面的动态性，显得力不从心。 万维网联盟( w o r l dw i d ew e bc o n s o r t i u m ，简称w 3 c ) 审视了h t m l 的缺点，制定的 x m l 规范已经成为一个研究热点，x m l 是网络应用发展的产物，是w 3 c 推荐的取代 h t m l 的网络语言。很多学者认为，x m l 作为一个手段和方法，推动着网络技术和社 会进步。 x m l 的提出，主要基于以下目的： ( 1 ) 国际化的信息发布的标准，可以独立于各种平台和系统。 ( 2 ) 允许各行各业定义平台独立的协议规范来交换数据。 ( 3 ) 实用化。用户可以通过方便简单的软件来处理数据，不需要昂贵的专业软件。 ( 4 ) 个性化。允许用户以自己喜欢的方式显示数据，数据内容与显示方式分离。 ( 5 ) 提供元数据。比如信息的来源和其他说明信息等，都是关于数据的解释和描述。 由于x m l 自描述的灵活性和可扩展性，越来越多的系统采用x m l t 乍为建模语言和 接口语言，各行各业提出了基于x m l 的专业标准，下一代因特网也把x m l 作为w e b 的 描述语言和接口语言。 x m l 的出现为解决w e b 数据挖掘中异构数据的难题带来了机会。由于x m l 能够使 不同来源的结构化的数据很容易地结合在一起，因而使搜索多样的不兼容的数据库能 4 够成为可能，从而为解决w e b 数据挖掘难题带来了希望。x m l 的扩展性和灵活性允许 x m l 描述不同种类应用软件中的数据，从而能描述搜集的w e b 页中的数据记录。同时， 由于基于x m l 的数据是自我描述的，数据不需要有内部描述就能被交换和处理。作为 表示结构化数据的一个工业标准，x m l 为组织、软件开发者、w e b 站点和终端使用者 提供了许多有利条件。 基于x m l 的w e b 数据抽取技术的研究将新一代的w e b 信息表达语言，x m l 应用于 数据抽取，对w e b 数据获取、数据转换、数据抽取与数据映射合并提出新的方法，并 实现一个快速通用的数据抽取原型系统，从而为w e b 信息集成、智能信息处理、数据 源间的相互操作、客户应用的快速构建等相关w c b 应用提供一种获取和利用w e b 信息的 通用平台。 因此，x m l 技术为基于w e b 的数据抽取技术的研究带来了新的希望，对新一代w e b 技术的发展及w e b 信息的开发利用，具有重要的理论意义和广阔的应用前景。 1 4 本文主要研究内容 本文主要研究如何实现半结构化的w e b 数据到结构化的x m l 数据的转换以及 x m l 数据到关系型数据的转换，从而实现w e b 数据的抽取与集成。本文讨论了w e b 信 息抽取的相关技术，并在w e b 信息抽取的基础上，提供了一套信息抽取、转换、集成 的方法与模型，将w e b 上的数据进行转换，并集成到目标数据库中去，最大限度的实 现了w e b 信息的再利用。 全文共分为六章，第一章是绪论部分，介绍了本课题的研究背景和国内外的研究 现状，并阐述了本课题的研究目的以及本课题要解决的问题。 第二章主要介绍了h r m l 到x m l 的转换算法。当前w e b 信息大多数都是h t m 璐式 的，w e b 数据抽取就是针对h t m l 格式的页面。结合x m l 的特性，提出了一种基于h t m l 到x m 瞒换算法，有机结合对称二叉树的概念，消除了h t m l 格式中不严格语法，为 下一步的x m l 数据抽取提供了可用的格式。 第三章介绍了基于x m l 数据映射分析。研究用x p a t h 和x s l t 文档将x m l 数据进行 映射。研究表明用x s l 文档对x m l 数据源映射为需要的x m l 数据文件是最优的。 第四章是对基于x m l 的数据集成进行分析。数据集成是数据抽取的最后一步，包 括数据关系存储和数据查询。本章对加工抽取出来的x m l 数据，以便用户进行对数据 的操作或二次查询。同时还提出了基于x m l 的w e b 查询模式，为整个信息抽取工作的 后期数据集成提供了很好的支持。 第五章结合数据抽取技术、x m l 技术和n e t 技术，提供了一个快速、通用的基于 x m l 的w e b 数据抽取原型系统。 5 第二章基于x m l 的数据转换方法分析 当前w e b 信息大多数都是h t m l n o 格式的，主要是由于具有简单、易用的特点， 所以目前被广为接受。尽管作为信息主要的载体，h t m l 提供了一种能方便地向读者 呈现信息的方法，但它可能并不是一个很好的可以从中自动抽取与数据驱动的服务或 应用程序相关的信息结构。 x m l 1 是由万维网协会( w 3 c ) 设计的一种中介标示语言。x m l 是一种元标记语 言，用户可以定义自己需要的标记n 2 1 。它提供了描述结构化数据的格式，可以通过独 立运行程序的方法来共享数据。与m m l 相比，x m l 具有内容与形式相分离的特性， 以及良好的可扩展性、跨平台移植性和自描述性等特征。 随着互联网应用需求及相关支撑产业的发展，x m l 已经成为互联网环境中数据描 述和网上应用系统间数据交换事实上的标准。因而删l 有效数据与x m l 结构化数据 的相互转换也是h t m l 内容数据重用和支持x m l 系统与支持h t m l 系统互操作的一个 关键问题。特定的环境中需要应用程序采用一定的策略来提取h t m l 中带有语义信息 的数据，或者重用、或者与其他系统中的数据交换，最后的问题都归结到如何将h t m l 格式转换成为x m 瞒式n 3 l 。 本章基于二叉树对称性从h t m i _ 格式到x m 略式的转换方法n 4 1 研究，并和数据转 换的其它工具进行比较，为下一步数据映射研究提供了可用的格式。 2 1 h t m l 和x m l 格式比较 x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 即可扩展标记语言，它与h t m l 一样， 都是s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ，标准通用标记语言) 。x m l 是 i n t e r n e t 环境中跨平台的，依赖于内容的技术，是当前处理结构化文档信息的有力 工具。扩展标记语言x m l 是一种简单的数据存储语言，使用一系列简单的标记描 述数据，而这些标记可以用方便的方式建立，虽然x m l 占用的空间比二进制数据 要占用更多的空间，但x m l 极其简单易于掌握和使用。 x m l 的卓越性能正是由其特点决定的，作为一种标记语言，它的主要特点如下： ( 1 ) 简单明了。x m l 经过精心设计，整个规范简单明了，它由若干规则组成，这些 规则可用于创建标记语言，并能用一种常常称作分析程序的简明程序处理所有新创建 的标记语。 ( 2 ) 7 f 放式。开放式标准x m l 的基础是经过验证的标准技术，并针对网络做最优化。 x m l 解释器可以使用编程的方法来载入一个x m l 文档，当这个文档被载入以后，用户 就可以通过x m l 3 = 件对象模型来获取和操纵整个文档信息，加快了网络运行速度。 ( 3 ) 高效且可扩充。支持复用文档片断，使用者可以发明和使用自己的标签，也可 与他人共享。在x m l 中，可以定义无限量的一组标注。x m l 提供了一个独立的运用程 序的方法来共享数据，使用d t d ，不同组中的人能够使用共同的d t d 来交换数据。 6 ( 4 ) 国际化。这源于依靠它的统一代码的新的编码标准，这种编码标准支持世界上 所有以主要语言编写的混合文本。因此，x m 坏仅能在不同的计算机系统之间交换信 息，而且能跨国界和超越不同文化疆界交换信息。 w e b 网站上的信息来自于不同的站点，每一个站点上数据源的结构都各不相同。 这就构成了一个巨大的异构数据库。另外，w e b 上的数据库与传统数据库中的数据不 同，没有固定的数据模型。每一站点的数据都各自独立设计，并且数据本身具有自述 性和动态可变性。因而w e b 上的数据虽然有一定的结构，但因自述层次的存在，是一 种非完全结构化的数据，这也被称之为半结构化数据。要充分利用这些数据，就要解 决半结构化数据的集成与查询问题。解决该问题的关键是寻找一个半结构化的数据模 型来清晰地描述w e b 上的数据。 在w 3 c s f j 定的h t m l 规范n 5 1 中，h t m l 规定了固定数据的标签集合，不允许用 户定义自己的扩展标签，而且m m l 在语法结构上的规格限制是比较松散的，就像控 制标记中的英文名称是大小无差别的那样，另外也没有严格要求每个控制标记都要有 相应的结束控制标记。这是因为h t m l 燕j 语法结构的要求并不十分严谨，外加浏览器 本身对h t m l 文件的容错性很高，即使h t m l 文件中有部分的语法结构错误，浏览器也 能将h t m l 文件显示。而x m l 可以让信息提供者根据需要，自行定义标记及属性名， 结构化地描述信息内容。创建x m l 的目的就是把它作为一个构造、存储和发送信息的 方式，因此其语法规则必然要求得非常严格。 在把h t m l 文件转换为x m l 文件时，所要消除的h t m l 格式中不严格的语法主要 包含以下3 种情形：一是在h t m l 中，一些标记不需闭合，而一些标记可以是开放的( 即 此标记可用闭合标记也可不用_ ) ，但是在不同浏览器中会引起问题，许都加上闭合标 记。二是标记嵌套不恰当，如 示例 仍然可以正常工作。以上 情形在x m l 中是不允许出现的。三是在h t m l 中，字母不区分大小写，在x m l 中，要 全部写成小写，满足w 3 c 标准。 2 2 基于二叉树的h t m l 向x m l 转换算法 2 2 1 原理和步骤 从语法上看，h t m i _ 和x m l 没有本质的区别，两者都是源于s g m l 的思想。只是 标准的h t m l 规定了固定数据的标签集合，不允许用户定义自己的扩展标签。而x m l 可以让信息提供者根据需要，自行定义标记及属性名，结构化地描述信息内容。另外， h t m l 语言是一种不甚严格的语言，很多时候读者直接看到的效果并非是原代码表现 出来的效果，而是浏览器很善意的向读者屈服，将一些不完全的代码也正常显示。然 而，x m l 主要用来存储和发送数据信息，所以其语法规则非常严格，具体表现就是所 有的元素必须有闭合标记。如果不考虑这些差别，x m l 只会l l h t m l 多出第一行的 ，而其他的内容都是一样的。 对于一个格式良好的h t m l 文件来说，一段简单的h t m l 文本及相应的x m l 文本， 7 只需要在首行加上x m l 的第一行代码 ，同时 将相应的文件扩展名h t m l 改为x m l ，就转换为x m l 文件了。也就是说，对于h t m l 格 式到x m l 格式转换的关键就是将h t m l 文本消除不严格的语法，形成格式良好的 m m l 文件，使得起始标记和结束标记界定的元素逐层嵌套。 由于x m l 严格的语法，所有的x m 昧记都必须有一个匹配的结束标记，有一个包 含所有其他元素的父( 或根) 元素，那么可以运用数据结构中的二叉树n 们来检验h t m l 文件的良好性，通过生成含有左右子树的对称二叉子树来达到检验的目的，对称的左 右子树表示匹配的标记，根节点表示包含所有其他元素的父( 或根) 元素。在方法中定义 带头节点的线性链表l 作为存储结构如图2 1 所示。 图2 1 线性链表l 每读入一个起始标记就将它的标记内容作为l 的一个元素。当读入一个结束标记 时，把它的内容写入变量p 中并与l 当前尾节点元素( 如图2 1 中的a ) 比较，如果两者相同 则以b 为根的二叉树的左右子树对称，表示这是一对匹配标记，符合x m l 的严格语法， 只需删除l 中的此元素即可，不需做其它处理。如果两者不相同，则要依次把它与a 的 祖先节点比较。假设如图2 1 找到b ，此时以c 为根的二叉树的左右子树不对称，则需要 增加相应的结束标记和a 构成一匹配对，然后可以去掉a 。这样以c 为根的二叉树的左 右子树对称，接着可以去掉c 。如此递推，直到l 中只剩下含头节点元素，即表示转换 成功。 输出格式良好的h t m l 文档是整个方法的核心，最后输出转换后的x m l 文档。整 个转换过程分为以下两个步骤： ( 1 ) 使用二叉树的左右子树的对称性来消除h t m l 文本中不严格的语法，输出格式 良好的h t m l 文件。 ( 2 ) 按照生成的格式良好的h t m l 文件，输出相应的x m l 文件。 8 2 2 2h t m l 不严格语法的消除算法 使用二叉树结构消除h t m l 文本中不严格的语法，输出格式良好的文件。为了实 现h t m l 的二叉树结构表示，因此，需要定义了一个字符串数组s ，作为数据元素。 其具体过程是依次从m m l 文件1 7 1 中读入字符，判断读入的字符是为“ ”还是为 “ 尸，并且记住每一个“ ”的位置。若为“ ”结尾的字符串) 的内容作为链表l 的一个元素。依次记载出现的在每一个 “ ”中的每一个字符串。若为“ 尸，则将此结束标记的内容与链表l 的最后一个元素 的内容比较，若相同，即表示此起始标记和读入的结束标记符合x m l 的严格语法，则 删除链表l 中的这个元素；如果不相同的话，则与链表l 中当前元素的父节点比较，直 到找到相同的节点元素。这种情况表示找到的起始标记和读入的结束标记界定的元素 不是逐层嵌套的，即不符合x m l 的严格语法。此时就要给在找到的起始标记和读入的 结束标记界定中的元素增加相应的结束标记。增加的方法为，如果找不到与读入的结 束标记相等的节点元素，可能是原h t m l 文件中不存在相等的节点元素，也可能是原 h t m l 文件中存在标记嵌套错误，但此嵌套错误已被前一个读入结束标记修正了，故 找不到与此读入结束标记相匹配的起始标记。如 示例 ，当 读入 时，根据上面的方法会在 前自动加入 ；当再读入 后 面的 时，在l 中就找不到匹配的 ，故应删除h t m l 中的 。消除h t m l 的不严格语法的算法如下： ( 1 ) 首先读取h t m l 文件，如果不是h t m l 文件的结束，就依次读取字符，如果 是“ ”符号则继续读取下一字符，将“ ”之间的内容作为一个元素加入链表l 中。 ( 2 ) 如果是“尸，则将“ ”的内容读入并赋值给字符串变量s 作为读入结束标 记。指针p 指向l 中的最后一个元素。 ( 3 ) 如果s 的值等于p 指向的元素的值，则删除链表l 中p 指向的元素。否则，与当前 指针指向的元素的父节点元素比较直到找到相同的节点元素，然后将链表l 中此节点元 素之后的元素内容分别加上“ ”后按逆序写入原h t m l 文件处，再删除l 中这 些元素。 ( 4 ) 如果找不到与s 的值相等的节点元素，则将此变量s 的值直接从h t m l 中删除掉， 然后继续读h t m l 文件。 如果读完原h t m l 文件后，l 中还有除头节点外的元素存在，则把这些元素的内 容分别加上“ ”后按逆序写入原h t m l 文件尾。 2 2 3x m l 文件的输出 输出x m l 文件这个子过程很简单，只要将前一步生成的符合x m l 严格语法的 h t m l 文本的开始处加上 即可。输出过程如 下： 9 v o i do u t p u t x m l ( h t m l f i l e ) f p r i n t f ( ” h a ”) ； f p r i n t f ( h t m l f i l e ) ； ) 输出的x l 订l 文件可以通过像m i c r o s o f ti n t e r n e te x p l o r e r5 或者其更高版本检查x m l 文件的格式是否良好，当然邀游浏览器也可以检查。若达不到结构良好的要求，就可 能要修改算法，也就是出现了某些特殊情况，要进行处理。 2 2 4 算法的修正 现在来分析一些特殊的情况，对算法进行一些修正。 ( 1 ) 对于h t m l 中含有i 拘s c r i p t 脚本，由于脚本中的表达式可能包含“ ”、“ ”，s t a r t l n d e x + 1 ” o ) 户 c a t c h t h r o wn e ws y s t e m x m l x m l e x c e p t i o n ( ”在解析结点信息时，出现未知异常! ”) ；) ) 2 3 二叉树转换算法与其它方法的比较 h t m lt i d yn 8 1 是一个免费的h t m l 语言检查工具，检查代码并指出一些与已发布 的w 3 c 标准不一致的地方。它可以用来解析包含h t m l 标记的h t m l 文件或字符串，并 可以自动改正错误，使其与相关标准完全一致。 。 h t m lt i d y 的工作原理是：首先是把满足w 3 c 标准的标记存储到数据字典中。之 后对一个h t m l 文件进行词法分析，将它的所有标记存储到一个队列之中，把结束标 记存储到另一个队列里面。接下来程序根据这两个队列进行查错。 2 3 1 二叉树转换算法的优势 首先从效率上，因为t i d v 工具需要在字典中逐一的比较h t m l 中的标签，而本论文 中所使用的二叉树算法是进行就近比较( 在当前结点就近比较) ，因此在效率上要大 大的优于t i d y i 具。 其次经过多次转换比较发现，t i d y i 具只能要求h t m l 文挡中的标签至少是按循序 嵌套的，而二叉树算法则可以很好的避免此类问题。 第三由于t i d y i 具是将符合w 3 c 标准的标签存储到字典中进行比较，所以当遇到不 满足w 3 c 标准的标签时，则不能处理。而二叉树算法可以将不符合w 3 c 标准的标签转 化为符合w 3 c 标准的标签。 以下两段代码是采用t i d y 和二叉树算法分别对同一数据源进行转换，其中左边的是 使用t i d y i 具进行转换的结果，右边是二叉树算法转换的结果。对比两种h t m l 转换方 法可以看出t i d y i 具转换并没有解决嵌套标签的问题，而二叉树算法则可以很好的避 免此类问题。 温度 温度加 风力 风力 2 3 3 实验结果 x m l 文档执行了转换操作之后成功地将h t m l 文档转换成了x m l 文档。图2 2 显示 转换后的代码结构，使用的是m i c r o s o f t 的i n t e r a c te x p l o r e r 查看转换后的x m l 3 9 档。其 中数据来源于新浪网的天气预报专题页面。 1 2 粤骘墨血墨皿圆口雹口曙田藏瞄口墨暖髓嗣瑶 j 徘 锶= i ：一i 吲目 i 1 l m l “l n mp - 蛳一蟹螂! 萼。! 图22 转换成x m l 的新浪天气页面 本文以在网络上抽取网站的网页原文件为例，验证了所设计的算法的功能和性能。 针对上面提出的h t m l 转换为x m l 时，所要消除的h t m l 格式中两种主要的不严格语 法，有针对性地修改了网页原文件，使其满足标记不闭合或标记嵌套