xml解析技术的发展

xml解析技术的发展

1wp解析技术xml可扩展为标准语言（xml），万维网协会（w3c）定义的数据传输和交换基准语言。最新版本是该组织2006年8月推出的版本1.1版。作为标准通用标记语言SGML(StandardGeneralizedMarkupLanguage,简称SGML)的子集,XML在保留SGML主要功能的同时极大地缩减了SGML的复杂性。XML独立于任何语言和体系结构,提供了适合表示半结构化数据的松散的树型结构,具有定义严格、结构清晰、灵活易读的特点,可以用来描述各种复杂信息,已经成为计算机系统中最广泛地用来数据交换和存储的格式之一,尤其是SOAP和Web服务领域的成功应用,使之成为下一代商业计算基础设施的重要组成部分。作为XML应用的基础,XML解析技术一直是XML领域的研究热点。在提高解析性能、降低资源占用、改善XML解析器的可用性上,人们做了大量的研究和实践工作。然而,随着XML应用领域的扩展,XML解析的性能仍无法满足部份应用的需要。在某些应用中,XML解析甚至成为瓶颈[6~8]。此外,XMLSchema验证为XML的应用提供了一定程度的错误自动检测能力。但是,验证过程降低了解析器的性能。如何兼顾错误检测能力和性能,已成为XML解析的挑战。2行为能力的挑战XML自身的特点以及应用的广泛性、复杂性给XML解析带来了巨大的挑战。本文认为,主要的挑战可以分为以下三个方面:(1)XML自身的特性带来解析时大量的计算开销。XML以基于文本的自描述方式组织信息,在带来了灵活性和可读性的同时也带来了大量的处理开销,主要表现在:对XML的解析需要大量的字符串操作,而且XML规范支持多种编码格式导致大量的编码转换开销;XML规范允许不定长的数据,在标签中允许可以忽略的空格,支持多种换行符,对每一个字符的判断操作导致的开销也是可观的;XML文档往往是冗长的,大量的冗余信息的处理需要占用计算资源;XML规范对名字空间的支持,使得解析器需要进行大量的栈操作。另外,如果需要将解析的结果构造成对象也需要大量的计算开销。(2)计算平台的变化给XML解析带来了挑战。一方面,随着普适计算逐渐从理想走向现实,XML技术被广泛应用于资源受限的设备中,比如手机、PDA等,XML解析的计算开销和运行时占用的资源成为瓶颈。另一方面,桌面计算领域多核处理器得到广泛的应用,使得原来的串行解析模式受到了挑战,设计高效的基于多核处理器的XML解析器需要新的探索。(3)XML应用本身对XML解析提出了挑战。随着XML应用领域日趋广泛,XML文档的规模也在不断增长[11~13],有的甚至可以达到GB级,传统解析技术很难对之作高效处理;在某些应用中,XML是以流而非传统文件的形式存在,要求新的解析技术支持;绝大多数应用场合要求对XML文档实例进行合法性验证,但主流的XML解析技术在验证过程中需要频繁访问XML实例和XMLSchema,导致了性能的显著下降,无法满足实时性较高的应用的需求。3串行解析技术为了更好地分析不同技术之间的区别,本文按如下方法将XML解析模型和技术进行了分类,如图1所示。其中,串行解析技术是指解析XML文档过程中采用单线程方式,即解析相关操作按照顺序执行的解析技术。根据对XML实例进行验证的模式,可以将串行解析进一步分为独立解析和解析与验证集成两种解析模式。并行解析技术是指在解析XML文档时采用多线程方式,将解析相关操作分解到不同的线程同时执行的解析技术。4字符串分析技术4.1独立分析模式独立解析的模式指将解析过程与验证过程彼此独立、验证过程处于解析过程之后的处理模式。其中,验证过程是可以选择的。4.1.1析期文书的解析经典解析模型指得到业界肯定并得到广泛商业应用的模型,具体包括DOM、SAX和XPP。(1)DOM。文档对象模型DOM(DocumentObjectModel,简称DOM)是W3C推荐的一种独立于语言和平台的标准,其目标是提供一个可以通用于各种程序语言、操作系统和应用程序的编程接口。DOM模型在解析XML文档时先将整个XML文档扫描一遍,得到独立的元素、属性和注释等,然后以结点树(即DOM树)的形式在内存中创建XML文档的表示,每一个结点代表一个可以和之交互的对象。用户可以通过结点树访问文档的内容,并根据需要修改文档。此模型有多种针对不同语言的成熟实现。这种解析模式的主要优点是在内存中保留整个文档的所有信息,用户可以随意访问任意位置的节点的信息或是对之进行修改,开发人员可以方便地编写程序。主要缺点包括:需要占用大量的资源,在文献中指出解析XML文档所用的内存大小达到原始XML文档大小的2~5倍;同时,解析完成之后才能把控制权转交给用户,因此文档较大时会造成很明显的延迟;即使只访问文档中的一小部分,也需要解析并构造整个文档,造成资源的浪费。(2)SAX。XML简易应用程序接口SAX(SimpleAPIforXML,简称SAX)是一个基于事件、采用“推”模式的解析模型,作为工业界的事实规范应用相当广泛。SAX解析器在解析XML文档过程中触发事件并激活用户预定义的回调(Callback)方法,通过向用户报告解析过程中的事件流来告知用户所解析文档的内容;对于这个事件的反应取决于用户。开发人员的主要工作就是编写回调函数。这种方式的主要优点是:解析很大的XML文档时,SAX与DOM相比需要的内存小得多,而且与文档大小基本无关;可以只访问XML文档中用户感兴趣的部分文档,从而显著提高内存利用效率和运行速度。但是,相对于DOM来说,SAX还是比较底层的,易用性差,必须由用户处理所有回调事件,而且应用逻辑的复杂性随着文档的复杂性增加而增加。此外,由于没有结构信息,需要时只能由用户自己构造,无法实现遍历,不支持XPath。另外,SAX只能通过创建一个新的文档来实现文档修改能力。和DOM模型一样,SAX需要解析整个文档,在解析过程中用户无法得到控制权,不支持随机访问。(3)XPP。以基于事件的“拉”(Pull)模式的解析器正成为工业界关注的热点,即XPP(XMLPullParser,简称XPP)。和SAX一样,XPP也使用事件驱动的模型,用户主动向XPP发送请求,XPP根据用户的请求返回相应的事件;用户可以控制解析过程,使得代码更易于编写和维护。XPP由于具有返回所请求事件的能力,而使应用程序无需跟踪事件在文档中的位置。XPP接口具有灵活小巧的特点,用户可以控制解析过程,比较适合于网络计算和移动环境的应用需求,有利于实现高效的XML文档解析。由于XPP只将用户所需要的事件流发送给用户,减少了向用户发送不必要的事件反馈,同时能很好地实现对文档的控制,具有类似于流媒体的优点。因此,与DOM和SAX相比,它具有占用内存少、更高效、更轻量等优势。对于在资源受限的环境下运行的应用程序以及当应用程序为了提高性能而需要利用数据流模型时,XPP解析是一种理想的选择,特别是处理Web服务等新领域中数据量小且要求能够快速响应的SOAP数据。与DOM相比,XPP有一些与SAX相同的缺点,那就是缺乏全面的导航支持。但是,XPP中对文档的前向遍历比SAX中的容易,因为应用程序可以控制它获取哪个事件以及获取时间。XPP修改文档的能力与SAX的相似,因为都需要创建一个新的文档。4.1.2实验结果分析上述经典的解析模型由于强调通用性、规范性,在具体应用时有的不能胜任,有的存在很大的性能提升空间,因此需要对经典的解析模型进行优化。通过优化,性能与原来的相比可以获得质的提升,弥补原来模型的某些方面的不足,扩大了应用的范围。本文将主要的优化方法分为简化接口和基于预处理技术两种技术。(1)简化接口。经典的解析模型为了保证通用性,提供了规范的编程接口。但是,对于一些特定应用来讲,这些接口不是必须的。使用这些编程接口,增加了数据操作,反而降低了性能。通过简化接口,尽可能早地按照应用要求组织解析得到的数据,将数据发送给应用程序,减少数据拷贝,可以极大地提高解析性能。比如,在文献中,为了快速高效地对SOAP/XML消息中的签名进行处理,借鉴Xercesc,设计了名叫QXP(QuickXMLParser,简称QXP)的解析器。QXP的思想是不构造一个标准的文档对象树,而是直接构造用来验证签名的二进制数组,同时采用类似于Cache的哈希表保存信息,并且在定位签名的所有阶段共享,提高访问效率。在两个测试中,QXP的速度达到了Xercesc的7至21倍。这种为特定应用场景进行的优化措施破坏了原有解析模型的通用性和兼容性。另外,延迟结点展开技术在一定情况下提高了DOM模型的解析性能[21~24]。解析器不在XML文档解析完成后就构造整个文档结点树,只有当用户正真访问到某一结点时才构造相关的子树,同时保持了DOM的兼容性。但是,这种实现方式也要占用大量的资源,开销很大,解析效率依然不高。特别地,当需要访问的是整个文档时,采用这种技术反而会降低性能。(2)基于预处理技术。通过在经典模型的解析过程前增加一定的预处理过程,解析性能可以获得很大的提高,同时可以保持应用编程接口的兼容性。针对相连处理的XML文档具有很大相似性的应用场景:所有信息的形式是统一的,比如Web服务应用中大多数消息是机器产生的,文献基于这样的思想设计了名叫“三角洲”的解析器:要实现更高的解析性能,就必须降低需要处理的字节数,同时减少对每一个字节的处理开销。“三角洲”在对用户透明的前提下增加了一个基于字节的比较引擎,其关键思想和技术如下:(1)XML文档的字节层次的匹配,通过只做字节层次的匹配,实现可靠的XML文档的比较;(2)用确定性有限状态自动机DFA(DeterministicFiniteAutomaton,简称DFA)保存已经处理过的文档,DFA中的每一个状态转换有一个字节序列及其对应的作为结果的处理事件;(3)部分解析技术,只解析那些与先前处理的文档不同的部分,每一个DFA状态保存了用于处理剩下字节序列的上下文;(4)递增的良定性检查,通过部分处理XML文档来判断整个文档是否是良定的。在最好的情况下,对于给定的一个以字节流形式的新的XML文档,“三角洲”不做XML的语法分析,而仅仅是把字节流与前面已经处理好的字节流做比较。处理器重复利用那些存储在内存中被匹配的部分就可以完成解析工作。文献中的实验结果很鼓舞人心。预过滤技术是一项重要的用来提高解析器性能、改善其可用性的手段。根据一定的规则、机制,在解析之前对XML文档进行预处理,将用户真正需要的部分过滤出来,然后执行解析,降低了解析的工作量,从而提高了解析性能。针对DOM、SAX模型在解析XML文档时必须访问整个文档,从而可能造成大量计算资源浪费的情况,以及SAX缺乏随机访问能力,文献提出了基于现有DOM和SAX模型的预处理框架,用来处理大的XML文档。该预处理框架采用一个微型的搜索引擎,该引擎根据用户的Xpath表达式定位目标XML文档中的有效位置,然后将有效文档片段收集到一XML文档中作为候选集,最后将该候选集发送给DOM、SAX等解析器进行解析。该预处理框架不但提高了DOM、SAX模型的解析性能,同时使得SAX具有了随机访问XML文档的能力,适合XML文档很大、不经常更新但会被经常查询的场景。但是,该方法在提高了效率的同时却占用了较多的内存资源。与此相类似的研究有文献。另外,预过滤技术的相关研究还有文献[28~30],这些研究着重建立大规模的XML过滤系统,比如发布/订阅系统。另外,文献提到了利用文档类型定义DTD(DocumentTypeDefinition,简称DTD)的过滤技术。4.2最终解析器tdx大多数XML解析器都支持根据XMLSchema验证XML文档实例。典型的验证过程是在解析完成后单独执行的,一般是位于解析器的最上层。但是,这种解析与验证分开的模式需要频繁地访问Schema,导致了显著的性能下降。Schema定制的解析器将解析与验证集成一起进行,以降低计算开销[32~36]。这些解析与验证集成的解析模式基于代码自动生成技术和编译技术,一般都需要工具(生成器)由指定的Schema根据一定的规则生成解析器代码,然后由对应语言的编译器编译得到最终的解析器。这类解析器在实验上可以取得很高的性能,但可用性不好,而且大多数不能支持语义上的验证。另外,生成器对于编程语言、编译器、操作系统、支持库、硬件都很敏感,使得其通用性受到损失。文献提出了一种以表格驱动的XML解析器TDX(Table-DrivenXMLparsing,简称TDX)。TDX将解析与验证集成到一个过程中,用以提高基于XML的应用性能。TDX利用LL(1)分析的优点来解析XML的语法和验证约束。XMLSchema中大多数的结构性约束能够利用LL(1)转化为语法规则;剩下的非结构性的语义上的验证规则转化为语义动作。如图2所示,一个TDX解析器由以下部分组成:扫描器、解析器、LL(1)解析表、语法结果及语义动作集、令牌集。解析器将XML实例作为输入,然后生成令牌流或CData文本输入到解析器,由解析器根据LL(1)解析表和语法结果及语义动作进行验证,最后将有效的数据送到应用程序。实验证明,TDX具有优越的性能,并且可以提供结构性约束与语义约束验证,可以满足那些要求高性能解析验证的应用要求。文献设计了一个实验系统:利用解析器生成与编译技术将解析与基于Schema的验证集成,从而获得了很高的性能。其策略是尽可能减少不必要的数据拷贝和转换,尽可能让绝大多数输入和输出的数据只访问一次。为了实现这个目的,该系统跨越了传统的分层结构,同时采用了支持不同API可配置的技术,并针对不同接口做了编译时的优化。与此类似的相关相关研究见文献。解析与验证集成的模式受到人们越来越多的重视,可望成为那些对解析性能要求很高、需要验证XML文档的应用的首选解决方案。5并行解析4周来图7.微处理器技术正向多核处理器过渡,基于Web服务的应用将广泛部署在多核处理器上。目前,大多数Web服务应用的XML解析性能在XML文档的大小增长时表现不好,而且在多核处理器上性能可能会进一步恶化。在科学计算应用中,巨大的(可以达到GB级)XML文档将越来越普遍,XML解析已经成为此类应用的瓶颈,并行的XML解析模型已成为解决上述问题的关键。目前,关于并行解析XML的技术研究处于探索阶段,工作集中在实验、分析方面,还没有成熟的设计与实现。虽然并行的编译技术已经发展了许多年,但并行解析XML的技术却刚刚起步。文献认为,并行解析技术没有得到人们的重视是由以下几个认识上的误区造成的:现在的解析器已经足够快以致能解决大部分问题;XML解析只是应用中的很小的一部分;解析器所做的大部分工作是固有的只能串行的扫描工作。对XML文档扫描是可以并行的,而且XML文档所具备的一定的结构化特性使其并行操作更为容易。基于上述前提,文献对并行解析XML文档的相关技术进行了探索,选择了基于Java语言的Piccolo作为参照。在Piccolo基础上,设计了两种体系结构的并行解析器,在不同场景下进行了实验。实验证明,对于大的XML文档而言,管道同步的开销是稳定的、可接受的(5%),可以使用现有的管道技术作为多线程间通讯机制来设计并行解析器;实验还表明,当解析巨大的XML文档时,试图在独立的线