XML数据压缩技术综述

维普资讯

ＸＭＬ数据压缩技术综述　

文苹编号：１００３　５８５０（２００８）０７　００６８—０３　

ＸＭＬ数据压缩技术综述　

Ｔｈｅ　Ｓｕｒｖｅｙ　０ｆ　ＸＭＬ　Ｄａｔａ　Ｃｏｍｐｒｅｓｓｉｏｎ　Ｔｅｃｈｎｉｑｕｅｓ　

陈　莎　包晓玲　张胜　

（南昌航空大学　南昌　３３００６３）　

【摘　要】随着互联网技术的迅速发展，ＸＭＬ已经成为Ｗｅｂ上信息表示和数据交换的事实标准。由于ＸＭＬ具　

有自我描述能力，使得ＸＭＬ文档显得冗长。以至于包含了大量的冗余信息，这样必将影响数据查询处理和交换　

的效率。因此，ＸＭＬ数据压缩技术对于减少资源的使用显得特别重要。概述了ＸＭＬ压缩研究的现状；分析了　

典型的ＸＭＬ压缩技术，对其性能进行了比较；总结ＸＭＬ压缩技术的不足及发展趋势。　

【关键词】ＸＭＬ数据压缩，数据冗余，查询处理，ＤＴＤ　

中图分类号：ＴＰ３０１．６　文献标识码：Ａ　

ＡＢＳＴＲＡＣＴ　Ｗｉｔｈ　ｔｈｅ　ｒａｐｉｄ　ｄｅｖｅｌｏｐｍｅｎｔ　ｏｆ　ｔｈｅ　Ｗｅｂ　ｔｅｃｈｎｏｌｏｇｙ，ＸＭＬ　ｈａｓ　ｂｅｃｏｍｅ　ｄｅｆａｃｔｏ　ｓｔａｎｄａｒｄ　ｆｏｒ　Ｄａｔａ　ｅｘｐｒｅｓｓｉｏｎ　ａｎｄ　

ｅｘｃｈａｎｇｅ．Ｈｏｗｅｖｅｒ，ｂｅｃａｕｓｅ　ｏｆ　ｔｈｅ　ｓｅｌｆ—ｄｅｓｃｒｉｂｅｄ　ａｂｉｌｉｔｙ　ｏｆ　ｔｈｅ　ＸＭＬ　ｍａｋｅｓ　ＸＭＬ　ｖｅｒｂｏｓｅ、Ｗｈａｔ　ｉｓ　ｍｏｒｅ，ｔｈｅ　ｉｎｃｒｅａｓｅｄ　ｓｉｚｅ　ａｆｆｅｃｔｓ　

ｂｏｔｈ　ｑｕｅｒｉｅｓ　ａｎｄ　ｔｒａｎｓｆｅｒｓ．Ａｆｔｅｒ　ａ　ｂｒｉｅｆ　ｉｎｔｒｏｄｕｃｔｉｏｎ　ｔＯ　ｔｈｅ　ｒｅｓｅａｒｃｈ　ｂａｃｋｇｒｏｕｎｄ　ｏｆ　ＸＭＬ　Ｄａｔａ　Ｃｏｍｐｒｅｓｓｉｏｎ　Ｔｅｃｈｎｏｏｇｙ，ｔｈｉｓ　ｐａｐｅｒ　

ｐｒｅｓｅｎｔｓ　ａｎ　ａｎａｌｙｓｉｓ　ｏｆ　ｔｈｅ　ＸＭＬ　ｃｏｍｐｒｅｓｓｉｏｎ　ｔｅｃｈｎｉｑｕｅｓ　ａｎｄ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ．Ａｔ　ｔｈｅ　ｅｎｄ　ｏｆ　ｔｈｉｓ　ｐａｐｅｒ　ｔｈｅ　ｆｕｔｕｒｅ　ｗｏｒｋ　ｏｆ　ＸＭＬ　

Ｄａｔａ　Ｃｏｍｐｒｅｓｓｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ　ｉｓ　ｐｒｅｓｅｎｔｅｄ．　

ＫＥＹＷＯＲＤＳ　ＸＭＬ　ｄａｔａ　ｃｏｍｐｒｅｓｓｉｏｎ，ｄａｔａ　ｒｅｄｕｎｄａｎｃｙ，ｑｕｅｒｙ　ｐｒｏｃｅｓｓ，ＤＴＤ　

随着互联网技术的迅速发展，ＸＭＬ已经成为　

压缩技术主要是用来解决ＸＭＬ的数据冗余问题，以　

满足网络宽带和存储空间的需求，其压缩率都高于传　

统的数据压缩技术，但是支持压缩文档的直接查询，如　

Ｗｅｂ上信息交换与数据处理的事实标准。ＸＭＬ的主　

要优势在于结构信息丰富、语义明确，因此越来越多的　

信息以ＸＭＬ文件的形式进行存储和交换。但是由于　

ＸＭＬ具有自我描述性，使得ＸＭＬ显得冗长，给数据　

的存储和传输带来极大的不便。因此近些年来，为了更　

好地推广ＸＭＬ的应用，提高数据文件的传输和存储　

效率，在压缩领域提出了许多针对ＸＭＬ数据的压缩　

技术，着重考虑了ＸＭＬ数据的特殊性，分析ＸＭＬ数　

ＸｍｉｌｌＩ３］、ＸＭＬＺｉｐ、ＸＭＬＰＰＭ、ＭｉｌｌａｕＩ４　等都属于这类　

压缩技术。随着ＸＭＬ应用范围的扩大，ＸＭＬ文档的　

容量也在不断地加大，如果通过完全解压缩来对压缩　

数据进行操作处理必然造成了系统的负担，因此在没　

有完全解压缩的情况下进行随机存取和查询处理成为　

了发展的必然，这就出现了可查询的ＸＭＬ数据压缩　

技术，如ＸＧｒｉｎｄ［　、ＸＰＲＥＳＳ：　、ＸＧｚｉｐ　Ｅ　、ＸＱｕｅＣＥ。］　

等。　

据的结构和特点，在传统数据压缩算法的基础上进一　

步改进，提高数据压缩的性能。　

本文将分别介绍ＸＭＬ数据压缩技术研究的现　

状、ＸＭＬ数据压缩的典型技术及其性能比较、ＸＭＬ　

数据压缩技术的不足及发展趋势。　

２　ＸＭＬ数据压缩技术简介　

２．１不可查询ＸＭＬ数据压缩技术　

１　ＸＭＬ数据压缩研究现状　

由于ＸＭＬ数据自身的特点，决定了其数据冗余　

较大，由此构成了空间的浪费、查询效率的降低。针对　

这些问题，目前提出了许多ＸＭＬ数据的压缩技术，针　

ＸＭＬ结构特征和语义信息进行压缩，得到比传统压　

缩技术更好的压缩性能。　

根据查询的支持程度，ＸＭＬ数据压缩可以分为　

不可查询与可查询的数据压缩技术。不可查询的数据　

＊　２００８—０１—０４收到，２００８＝０５—２５改回　

这类压缩技术都拥有较好的压缩性能，有着出色　

的压缩比、压缩／解压缩时间短、存储空间小等，但是不　

能对压缩文档进行直接查询。　

２．１．１　Ｘｍｉｌｌ　

Ｘｍｉｌｌ是最早的不支持查询的ＸＭＬ压缩技术，建　

立在传统压缩技术Ｇｚｉｐ之上，核心思想是将结构与内　

容分离。它在压缩ＸＭＬ文档时遵循３个规则：①结构　

与内容分离：文档结构由ＸＭＬ标签和属性组成，在　

Ｘｍｉｌｌ中对于开始标签和属性一般采用字典编码的方　

＊＊　基金项目：江西省教育厅科技计划项目（ＪＧＧ０８２２３）；博士启动基金资助项目（ＥＡ２００６０６１９８）。　

＊＊＊陈莎，女，１９８４年生，硕士研究生，研究方向：ＸＭＬ，数据压缩。　

维普资讯

第２１卷第７期　电脑开发与应用　

式进行，所有的结束标签都用“／”代替，数据项都用其　

的文档有着非常出色的压缩比。　

所在的容器的号表示。②具有相关语义的数据项分组：　

２．２查询ＸＭＬ数据压缩技术　

将具有相关语义的数据项放人同一个数据容器中。决　

这类ＸＭＬ数据压缩技术可以对压缩文档进行直　

定数据项放　那个容器主要是有两个因素决定：首先　

接查询，但是一定程度上牺牲了压缩性能。但是随着　

是数据项的路径，其次是容器表达式。③运用语义压缩　

ＸＭＬ压缩技术的不断改进，这类压缩技术将会成为　

机：在Ｘｍｉｌｌ中针对不同的数据容器运用专门的压缩　

了ＸＭＬ压缩领域的一大趋势。　

机。Ｘｍｉｌ１支持３种语义压缩机：元语义压缩机、联合　

①ＸＧｒｉｎｄ：ＸＧｒｉｎｄ是一种支持压缩域查询的　

语义压缩机、用户自定义语义压缩机。　

ＸＭＬ数据压缩技术，主要采用了同构转换的压缩思　

由于Ｘｍｉｌｌ将结构和内容分离，因此Ｘｍｉｌｌ具有　

想。压缩过程如图１所示，首先ＸＧｒｉｎｄ核心使ＤＴＤ　

出色的压缩比率，其次内存消耗降低、减少了网络带　

解释器对ＸＭＬ文档的ＤＴＤ进行分析，然后初始化一　

宽。同时Ｘｍｉｌｌ也存在一定的问题，不能对压缩文档进　

个表，用来列出元素和非枚举类型属性出现的频率，同　

行查询，需要人工干预等。因此Ｘｍｉｌｌ并没有被广泛地　

时还为枚举数据类型建立一个标志表。接下来ＸＧｒｉｎｄ　

应用。但是Ｘｍｉｌｌ的优点对以后ＸＭＬ数据压缩技术　

核心使ＸＭＬ解释器对ＸＭＬ文档进行两次扫描，第１　

的研究和发展起到了重要的作用。　

次扫描把ＸＭＬ文档的元素和不含枚举数据类型的属　

２．１．２　ＸＭＬＺｉｐ　

性出现的频率统计到频率表中去，第２次扫描是对元　

ＸＭＬＺｉｐ与Ｘｍｉｌｌ类似，也是建立在Ｇｚｉｐ压缩技　

素、属性或数据值进行相应的编码。对于元数据和枚举　

术之上的ＸＭＬ压缩技术。　

类型属性值使用枚举类型属性编码器，对于非枚举类　

ＸＭＬＺｉｐ压缩的ＸＭＬ文档结构用ＤＯＭ树来表　

型属性值使用Ｈｕｆｆｍａｎ压缩机。最后将编码过的数据　

示。在压缩过程中深度变量Ｌ起到了决定性作用，　

和所建立的表格通过ＸＭＬ生成器处理，得到ＸＭＬ压　

ＸＭＬＺｉｐ可以将这个ＤＯＭ树分解为根组件：包括深　

缩文档。　

度为Ｌ的树结构中的所有节点，子组件：深度从Ｌ开　

始到所有子树节点的集合。最后利用Ｇｚｉｐ压缩工具对　

各个组件进行独立压缩并最终输出一个ＸＭＬ压缩文　

档。值得注意的是深度Ｌ可以由用户指定，并且压缩　

性能的好坏直接取决于深度变量Ｌ值的大小，随着Ｌ　

的值增加会使得压缩性能变的非常糟糕。　

２．１．３　其他不可查询ＸＭＬ压缩技术　

①ＸＭＬＰＰＭ：压缩过程与Ｘｍｉｌｌ类似，ＸＭＬＰＰＭ　

的核心思想也是将结构与内容分离。然而与Ｘｍｉｌｌ不　

图１　ＸＧｒｉｎｇ￣构图　

同的是它采用了一种叫做多层次建模的建模技术，其　

ＸＧｒｉｎｄ系统的最大特点是在压缩数据之上支持　

中应用了ＳＡＸ和ＰＰＭ建模技术。　

查询，同时ＸＧｒｉｎｄ在保留了结构完整性的同时，又具　

ｘＭＬＰＰＭ采用了两步压缩的思想：首先　

有Ｘｍｉｌｌ的数据与结构分离的特点。当然，付出的代价　

ＸＭＬＰＰＭ采用了ＳＡＸ将ＸＭＬ文档中的标签、属性　

是压缩比率要比Ｘｍｉｌｌ低，而且需要对ＸＭＬ文档进　

以及数据项进行分离并存人相对应的模型中去。接着，　

行两次解析，所以需要更长的压缩时间。　

ＸＭＬＰＰＭ采用ＰＰＭ编码方式对各个模型中的数据　

进行压缩编码。具有以下特点：不需要人工干预，拥有　

ｘＭＬ分析器　

出色的压缩比率，支持在线压缩。　

ｒｊ统计收集器Ｉ　

Ｘ～Ｉ解　ｌ　ｌ呻Ｉ数据类型识别器ｆ　

②Ｍｉｌｌａｕ：是一种在线的ＸＭＬ压缩技术，可以充　

析　

分的利用文档结构来进行压缩，来取得出色的压缩性　

器　Ｉ倒装算术编码器１　

Ｉ类型编码器　１

能，编码方式主要基于ＷＢＸＭＬ规则。在压缩过程中　

ＸＭＬ编码器　

采用了一个标记表来对ＸＭＬ标签和属性进行编码，　

图２　Ｘｐｒｅｓｓ￣构图　

而数据项使用传统的文本压缩机来进行压缩。虽然　

②Ｘｐｒｅｓｓ：Ｘｐｒｅｓｓ是一种支持直接高效查询　

Ｍｉｌｌａｕ对于大容量的的ＸＭＬ文档的压缩性能没有传　ＸＭＬ压缩技术。主要思想是：首先采用了一种为　

统的文本压缩算法好，但是对于大小界于ＯＫＢ～５ＫＢ　

ＸＭＬ文档中元素的树型路径进行编码而设计实现的　

维普资讯

ＸＭＬ数据压缩技术综述　

反向算术编码的编码方式：让每一个树路径都对应一　

要降低内存消耗，就要避免将整个未压缩文档调入内　

个［Ｏ．０，１．Ｏ］的实数区间，在整个压缩过程中就是利用　

这些实数区间来进行编码的。同时采用了数据类型的　

自动识别，这样避免了人工干预；接下来它还对不同的　

类型的数据采用不同的编码方式，这样可以得到更高　

的压缩比率；另外，也采用了与ＸＧｒｉｎｄ压缩算法相似　

的同构压缩思想，以保持与原来ＸＭＬ文档无论在语　

义还是结构上都保持相同，这样可以对ＸＭＬ压缩文　

档进行直接查询。如图２所示为Ｘｐｒｅｓｓ的结构图。　

存，所以一般采用ＳＡＸ分析器对ＸＭＬ文档进行分　

析。如表１所示给出了各ＸＭＬ压缩技术结构与性能　

的比较。　．．　

３　ＸＭＬ数据压缩技术的发展趋势　

通过本文的分析可以得知，上述的压缩算法都是　

在不可查询与可查询之间作着某种权衡，那么如何处　

理这种权衡就成为了一个很大的挑战。　

结合所存在的问题，提出ＸＭＬ数据压缩技术的　

③其他可查询压缩技术　

ａ．ＸＱｚｉｐ与ＸＭｉｌｌ类似，采用了结构和内容分离　

的压缩思想，同时采用了结构索引树的技术，使得可以　

对ＸＭＬ压缩文档进行直接查询，而无需进行解压。　

ｂ．ＸＱｕｅｃ也沿用了ＸＭｉｌｌ的压缩思想，将结构和　

内容相分离，并将具有相关意义的数据项放到同一个　

数据容器中去，最后对不同的容器采用不同的压缩算　

法。此外为了支持对ＸＭＬ压缩文档的查询功能，　

ＸＱｕｅｃ为ＸＭＬ文档建立了结构树以及索引树。　

２．３　ＸＭＬ数据压缩技术的性能比较　

表１　ＸＭＬ压缩技术结构与性能比较　

压缩　压缩率　压缩时　内存消耗　应用的　ＸＭＬ文　查询　其他性能　

技术　／Ｇｚｉｐ　间Ｇｚｌｐ　压缩算法　档分析器　功能　

Ｇｚｉｐ、　不可　

关键在于：①应该具有良好、稳定的压缩性能，这包括：　

出色的压缩比、合理的压缩／解压缩时间、存储空间的　

有效利用、节省网络带宽；②ＸＭＬ压缩文档可以支持　

复杂查询及更新功能，减少人工干预。　

ＸＭＬ数据压缩技术目前已经成为ＸＭＬ研究领　

域的研究热点，并且具有很大的发展空间，随着Ｗｅｂ　

］

Ⅱ　

　］　］　］　］

技术的快速发展，ＸＭＬ数据压缩技术将会面临更大　

的挑战。　

参考文献　

万常选．ＸＭＬ数据库技术［Ｍ］．北京：清华大学出版　

社，２００４．　

Ｄａｖｉｄ　Ｓ．Ｄａｔａ　Ｃｏｍｐｒｅｓｓｉｏｎ　Ｔｈｅ　Ｃｏｍｐｌｅｔｅ　Ｒｅｆｅｒｅｎｃｅ　

需人工干　

ＸＭ＇ｌ１　好　差不多　恒定　

Ｂｚｉｐ　

ＳＡＸ　预、不可　

查询　

在线压缩　

［Ｍ］．Ｓｅｃｏｎｄ　Ｅｄｉｔｉｏｎ．Ｂｅｉｊｉｎｇ：Ｐｕｂｉｓｈｉｎｇ　Ｈｏｕｓｅ　ｏｆ　

Ｅｌｅｃｔｒｏｎｃｓ　Ｉｎｄｕｓｔｒｙ，２００３．　

ＸＧｒｉｎｄ　差　

至少　大致　Ｈｕｆｆｍａｎ　

两倍　恒定　编码　

ＳＡＸ　

可　无需人　

查询　工干预　

Ｌｉｅｆｋｅ　Ｈ，Ｓｕｃｉｕ　Ｄ．ＸＭＩＬＬ：Ａｎ　Ｅｆｆｉｃｉｅｎｔ　Ｃｏｍｐｒｅｓｓｏｒ　

ｆｏｒ　ＸＭＬ　Ｄａｔａ　ｒＣ］．ＵＳ：Ｐｒｏｃ　ｏｆ　ｔｈｅ　２０００　ＡＣＭ　

ＳＩＧＭＯＤ　Ｃｏｎｆ　ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ，２０００．　

倒装算术　

ＸＰＲ　差　至少　大致　

ＥＳＳ　

编码、　ＳＡＸ　可　无需人　

查询　工干预　

ＷＩ１ｆｒｅｄ　Ｎ。Ｌａｉｎ　Ｗ　Ｙ，Ｊａｍｅｓ　Ｃ．Ｃｏｍｏｐａｒａ　ｔｉｖｅ　

两倍　恒定　Ｈｕｆｆｍａｎ　

编码　

Ａｎａｌｙｓｉｓ　ｏｆ　ＸＭＬ　Ｃｏｍｐｒｅｓｓｉｏｎ　Ｔｅｃｈｎｏｌｏｇｉｅｓ［ｚ］．　

Ｗｏｒｌｄ　Ｗｉｄｅ　Ｗｅｂ：Ｉｎｔｅｒｎｅｔ　ａｎｄ　Ｗｅｂ　Ｉｎｆｏｒｍａｔｉｏｎ　

无需人　

Ｓｙｓｔｅｍｓ．２００６：５－３３．　

ＸＭＬ　好　

ＰＰＭ　

长　恒定　

ＰＰＭ　ＳＡＸ　

不可　工干预、　

查询　不可在　

Ｔｏｌａｎｉ　Ｐ　Ｍ，Ｈａｒｉｔｓａ　Ｊ　Ｒ．ＸＧＲＩＮＤ：Ａ　Ｑｕｅｒｙ－ｆｒｉｅｎｄｌｙ　

ＸＭＬ　Ｃｏｍｐｒｅｓｓｏｒ　Ｅｃ］．Ｉｎ　ＩＥＥＥ　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　

１８ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　Ｏｉｌ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，　

２００２．　

线压缩　

ＸＭＬ　

接近　较长　档大小　

与输入文　

Ｇ

不可　不

ＤＯＭ　ｚｉｐ　

可在　

ｚｌｐ　成比例　查询　线压缩　

Ｍｉｎ　Ｊ，Ｐａｒｋ　Ｍ　Ｊ　Ｐ，Ｃｈｉｎ　Ｗ　Ｃ．ＸＰＲＥＳＳ：ａ　Ｑｕｅｒｉａｂｌｅ　

Ｃｏｍｐｒｅｓｓｉｏｎ　ｆｏｒ　ＸＭＬ　Ｄａｔａ［Ｃ］．ＵＳ：Ｐｒｏｃ　ｏｆ　ｔｈｅ　２００３　

与输入文　

ＭｉｌｌＤＴＤ　ｔｒｅｅ、　不可　可在线　

ａｕ　较好　较长　档大小　Ｄ０Ｍ　

ＡＣＭ　ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ．２００３．　

成比例　Ｇｚｉｐ　查询　压缩　

Ｃｈｅｎｇ　Ｊ，Ｎｇ　Ｗ．ＸＱｚｉｐ：Ｑｕｅｒｙｉｎｇ　Ｃｏｍｐｒｅｓｓｅｄ　ＸＭＬ　

Ｕｓｉｎｇ　Ｓｔｒｕｃｔｕｒａｌ　Ｉｎｄｅｘｉｎｇ［ｃ］．Ｉｎ　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　

ＥＤＢＴ。２００４．　

高效的ＸＭＬ压缩技术需要在压缩比率、压缩／　

解压缩时间、内存消耗等方面有非常出色的性能，能够　

Ａｒｉｏｎ　Ａ，Ｂｏｎｉｆａｔｉ　Ａ，Ｃｏｓｔａ　Ｇ，ｅｔ　ａ１．ＸＱｕｅＣ：Ｐｕｓｈｉｎｇ　

产生比传统的压缩技术Ｇｚｉｐ更好的压缩性能。产生好　

的压缩率需要充分地利用ＸＭＬ文档的结构和数据。　

产生好的压缩／解压缩时间需要对文档分析遍历一次，　

Ｑｕｅｒｉｅｓ　ｔＯ　Ｃｏｍｐｒｅｓｓｅｄ　ＸＭＬ　Ｄａｔａ［Ｃ］．Ｉｎ　Ｐｒｏｃｅｅｄｉｎｇｓ　

ｏｆ　ｔｈｅ　２９ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅｏｎ　Ｖｅｒｙ　Ｌａｒｇｅ　

Ｄａｔａ　Ｂａｓｅｓ。２００３．