点击挑战原文

简介

常用缩略语

• CDATA：字符数据
• DTD：文档类型定义
• GPS：全球定位系统
• HTML：超文本标记语言
• PPM：根据部分匹配预测
• SAX：XML 的简易 API
• W3C：万维网联盟
• XML：可扩展标记语言

XML 是因为 HTML 和万维网的广泛普及而出现的最有用、最重要的技术之一。XML 解决了许多问题，因为它可以在不同的架构之间提供中立的数据表示，通过最少的努力弥补软件系统之间的差距，并存储大量的半结构化数据。

XML 通常被称为自我描述的数据，因为它被设计为对文档中的每个记录使用重复的模式。这种自我描述功能为 XML 提供了巨大的灵活性，但是也引入了 XML 文档过于冗长的问题，这会造成文档较大。由于 XML 的使用率在不断增长，而且大型 XML 文档信息库目前也非常普遍，所以对高效 XML 压缩工具的需求非常大。

图 1 说明了使用 XML 压缩器减少通过网络传输 XML 数据的成本这一优势。为了解决大型 XML 文档的大小问题，许多 XML 感知的压缩器利用众所周知的 XML 文档的结构，使得压缩比率优于一般的文本压缩器的比率。XML 压缩工具的众多优势包括减少数据交换所需的网络带宽，减少存储所需的磁盘空间，并最大限度地降低了处理和查询 XML 文档的主要内存要求。

图 1. 使用 XML 压缩器通过网络传输 XML 数据的优势示例

从原则上说，XML 压缩器可以根据两个主要特点进行分类。图 2 说明了第一种分类，这种分类基于对 XML 文档结构的感知。根据这种分类，压缩器可分为两大类：

• 一般的文本压缩器。由于 XML 数据是以文本文件的形式进行存储的，因此压缩 XML 文档的第一种逻辑方法是采用传统的通用文本压缩工具（例如：gzip、bzip2）。这种 XML 压缩器是与 XML 无关的，也就是说，它们将 XML 文档用作普通的纯文本文件，因此采用的是传统的文本压缩技术。
• XML 感知压缩器。这种压缩器旨在利用对 XML 文档结构的感知，实现比一般文本压缩器更好的压缩比率。这组压缩器可以根据压缩器对如下所示的 XML 文档的模式信息可用性的依赖性进行进一步分类：
  • 依赖模式的压缩器。编码器和解码器都必须能够访问文档模式信息，以实现压缩流程（如：rngzip）。
  • 独立于模式的压缩器。不要求模式信息的可用性便可实现编码和解码流程（如：XMill、SCMPPM）。

图 2. 根据其对 XML 文档结构的感知对 XML 压缩器进行的分类

图 3 说明了对 XML 压缩器进行的第二种分类，基于压缩器支持以下查询的能力：

• 非可查询（归档）XML 压缩器。这种 XML 压缩器不允许通过被压缩的格式（例如：gzip、bzip2、XMill）处理查询。这类压缩器主要侧重于实现最高的压缩比。在默认情况下，通用文本压缩器是非可查询压缩器组。
• 可查询 XML 压缩器。这种 XML 压缩器允许通过其被压缩的格式处理查询。这种压缩器的压缩比通常比归档 XML 压缩器的压缩比差。这类压缩器主要侧重于避免在查询过程中进行完整的文档解压缩。实际上，对被压缩的 XML 格式执行直接查询的能力对于许多托管在资源有限的计算设备上的应用来说都非常重要，如：移动设备和 GPS 系统。在默认情况下，所有的可查询压缩器也是XML 感知的压缩器。根据它们如何对 XML 文档的结构和数据部分进行编码，可以对这组压缩器进行进一步分类：
  • 同质压缩器。XML 文档的原始结构被保留，您可以使用与原始格式相同的方式访问并解析被压缩的格式（如：XGrind）。
  • 非同质压缩器。对 XML文档的编码过程将结构部分和数据部分（如：XQueC）分离。因此，被压缩格式的结构与原始 XML 文档的结构不同。

图 3. 根据其是否支持执行查询对 XML 压缩器进行分类

 

一般文本压缩器

XML 是树形结构数据的文本表示。压缩 XML 文档的一种简单方法是使用传统的通用文本压缩工具。在过去几十年内，制定的许多算法都能够高效地压缩文本数据。这类压缩器中最受欢迎、效率最高的代表是 gzip、bzip2 和 PPM 压缩器。

gzip 压缩器基于 DEFLATE 无损数据压缩算法，它使用 LZ77 算法和 Huffman 编码的组合。为了压缩数据，LZ77算法使用对匹配数据的引用来取代数据部分。匹配数据已经通过编码器和解码器传递。Huffman 编码使用一种特定方法选择每个符号的表示，使用当时短位字符串的最常见的字符被使用，而不使用不常见的源符号。

bzip2 压缩器使用 Burrows-Wheeler 转换，将经常重复的字符序列转换成相同的字母字符串，然后应用 Move To Front 转换，最后使用 Huffman 编码。Burrows-Wheeler 变换排列字符的顺序可实现以下效果，如果原始字符串有经常出现的几个子字符串，那么变换后的字符串就会有几个地方出现一个字符，在一行中某个字符会重复出 现多次。这种方法对于压缩非常有用，因为它往往容易压缩拥有多行重复字符的字符串。在实践中，bzip2 压缩方法压缩文件的比率比使用 gzip 进行压缩的比率高，但是性能也较低。

PPM 是自适应统计数据压缩技术，基于上下文建模和预测。它使用有限的上下文统计建模技术，混合了多个顺序固定的上下文模型，预测输入序列中的下一个字符。对模 型中每个上下文的预测概率从频率数计算，进行自适应更新。对于实际出现的符号，会使用算术编码，相对于其预测分发进行编码。尽管 PPM 比较简单，但它是目前为止提供的最高效的压缩器，同时也是计算最昂贵的压缩器。

实际上，一般这类压缩器用于归档目的，或在数据交换过程中减少网络带宽。通常情况下，这些压缩器在两个主要指标（即压缩比和压缩/解压时间） 之间进行权衡。一方面，PPM 压缩可以实现最好的压缩比，而 gzip 实现的压缩比较差。另一方面，gzip 在压缩/解压时间方面拥有最佳性能，而PPM 的压缩/解压速度慢很多。bzip2 位于这两个指标的中间位置。因此，用户选择使用哪种压缩器主要取决于用户场景对这两个指标的要求。

不可查询（可归档）XML 压缩器

这组 XML 压缩器不允许通过压缩格式处理查询，因为它们的主要重点是实现最高的压缩比。本节讨论这组压缩器的两个主要类型的代表：

• 独立于模式的压缩器
• 依赖于模式的压缩器

独立于模式的压缩方案

此类压缩模式不要求提供可用的模式信息便能执行编码和解码流程。XMill 是第一次实现 XML 感知的压缩器，它引入了一个新颖的观点将XML 文档的结构与数据分隔开，并根据数据在树形中的相对路径及其数据类型，将数据值分组到同质 (homogenous) 容器中。

在 XMill 中，源 XML 文档的结构和数据值部分被单独收集和压缩。在结构部分，在将编码传递到后端一般文本压缩方案之前，XML 标记和属性以基于词典的方式进行编码。XMill 的结构编码方案为每个不同的元素和属性名称分配一个整数代码，作为进入元素和属性名称词典的密钥。在数据部分，数据值根据路径和数据类型被分组为同质和语 义相关的容器。然后，每个容器通过适用于该容器的数据类型的专用的压缩器进行独立压缩。该分组操作本地化重复，从而提高压缩程度。

在最新版本的 XMill 源分布中，压缩格式的中间二进制可以传递到三种替代后端通用压缩器之一：gzip、bzip2 和 PPM。图 4 说明了 XMill 压缩器的一般架构概述，提供 XML 解析器、结构和数据容器，一个或多个压缩方案，以及被压缩的 XML 文件（包含压缩结构和压缩数据）。

图 4. XMill 压缩器的一般架构

图 5说明了将 XML 文件分到结构和数据容器中的示例。元素和属性表存储 XML 文档的结构容器。每个独特路径（元素或属性）的值存储在单独的表格（容器）中，因此每个容器中的值均变为同质，可以更高效地进行压缩。本示例包括独立的元 素（customers、customers/customer、customers/customer/firstName、customers /customer/lastName、customers/customer/invoice、customers/customer/invoice /items 和 customers/customer/invoice/items/item）以及属性（customers/customer/@id 和 customers/customer/invoice/@total）表。

图 5. 将 XML 文件分裂为结构和数据容器的示例

图 6 说明了 XMill 压缩器的命令行选项。

图 6. XMill 压缩器的命令行选项

图 7 说明了压缩 XML 文档（tpc.xml，大小为 282 KB）的效果，使用 XMill 压缩器，其中输出压缩文件（tpc.xmi，大小为 41 KB）的大小代表 15% 原始 XML 文件的大小。

图 7. 通过 XMill 压缩器压缩 XML 文件的输出

XMLPPM 是流 XML 压缩器，使用称为 MHM 的复用分层 PPM 模型。XMLPPM 被认为部分匹配压缩方案 (PPM) 采用的通用预测。在 XMLPPM 中，XML 文件首先通过 SAX 解析器进行解析，以生成 SAX 事件流。每个事件都通过称为 ESAX（编码的SAX）的字节码表示法进行编码。ESAX 字节码根据其句法结构（元素、字符、属性和杂项符号）通过多个复用 PPM 模型之一进行编码。SCMPPM 压缩器已经被作为 XMLPPM 压缩器的一个版本提供。SCMPPM 结合了称为结构上下文建模 (SCM) 的技术和 PPM 压缩方案。它使用了一组比 XMLPPM 更大的 PPM 模型，因为它使用独立的模型压缩每个元素符号下的文本上下文。

XMill 和 XMLPPM 的压缩比和压缩/解压时间依赖于并与其后端、通用压缩器（gzip、bzip2 或 PPM）相关。因此，它们与自己的通用后端压缩器具有相同的权衡。

依赖于模式的压缩方案

此类压缩器在编码和解码流程中要求可用 XML 文档的模式信息。例如，XAUST XML 压缩器将 DTD 的模式信息转换成一组确定性有限自动机 (DFA)，每个 DFA 对应于 DTD 中的一个元素。然后每个转换都用一个元素标记，与转换有关的行为是调用 DFA 的模拟器，可将该行为用于标记该转换的元素。XAUST 将同一元素的所有数据都归入单一容器，然后使用算 order-4 压缩器的单个模型以递增方式压缩该容器。使用 DTD 模式信息，XAUST 能够跟踪文档的结构，并能够准确预测预期符号。只要预测到符号是独特的，就不需要对其进行编码，因为解码器从 DTD 生成相同的模型，从而可以生成独特的预期符号。

RNGzip XML 工具可以压缩符合给定 Relax NG 模式的 XML 文档。在 RNGzip 中，发送方和接收方必须提前同意使用相同的模式。在这个意义上说，模式类似于用于加密和解密的共享密钥。RNGzip 使用 Relax NG 模式验证程序从指定的模式构建确定性树自动机。然后，给出一个 XML 文档，用它检查 XML 是否被自动机接受。有了这种自动机，接收方可以通过传输少量信息，重建整个 XML 文档。如果在自动机中有一个选择点，那么 RNGzip 只传输已经完成的转换，如果遇到文本转换，则值传输匹配的文本。

从理论上说，依赖于模式的压缩器可能实现比独立于模式的压缩器更高的压缩比。但是它们并不是更好的选择，或通常被用作 XML 文档的模式信息，并不总是可用，从而它们失去了 XML 表示半结构化数据的灵活性。只有使用此类压缩器来压缩带有预定义模式的 XML 文档时，这类压缩器才是有效的。

 

可查询 XML 压缩器

可查询 XML 压缩器的主要功能是允许通过其压缩格式直接评估查询，而无需对整个文档进行解压缩。这类压缩器的压缩比通常比归档 XML 压缩器的压缩比差。此类压缩器对于许多托管在资源有限的计算设备上的应用（如移动设备和 GPS 系统）来说非常重要。本节讨论这类压缩器的两个主要类型的代表：

• 同质压缩器
• 非同质压缩器

同质可查询 XML 压缩器

此类压缩器以压缩格式保留 XML 文档的原始结构，以便能够使用与原始格式相同的方式对其进行访问和解析。XGrind 是第一个与 XML 有关的压缩方案，支持查询且无需完全解压整个被压缩的 XML 文档。XGrind 没有分离数据和结构。它保留了 XML 文档的原始结构。

XGrind 压缩格式的同质性质为 XGrind 提供了许多有趣的功能：

• 可以将被压缩的 XML 文档视为原始 XML 文档，相应的编码取代其标记和元素/属性值。因此，可以将 XGrind 视为扩展的 SAX 解析器。
• 可以在压缩文档上构建 XML 索引技术，构建方式与在常规 XML 文档上构建它们的方式相同。在 XGrind 中，元素和属性名称使用基于词典的编码方案进行编码，字符数据通过半自适应 Huffman 编码进行压缩。XGrind 的查询处理器只能处理压缩值的精确匹配和前缀匹配查询，还可以处理对解压值的部分匹配和范围查询。然而，XGrind 不支持一些操作，例如，它不支持压缩域中的不等式选择。因此，XGrind 不能执行任何连接、聚合、嵌套查询或构建操作。

XPress 是另一种同质 XML 压缩器，使用组合功能高效地压缩和检索 XML 数据。为了编码 XML 文档的标签和路径，它在不同的间隔使用反向算术编码方法。利用间隔之间的约束关系，可以根据已压缩的 XML 数据评估路径表达式。XPress 的压缩方案是一个半自适应的方案，使用输入文件的初步扫描来收集统计信息，数据的编码规则与数据位置无关。它还根据自动推断的类型信息对数据值使用适当的 编码器。

非同质可查询 XML 压缩器

此类压缩器在 XML 文档的编码过程中将结构部分和数据部分分隔开。因此，与同质类不同，压缩后的格式的结构不同于原始 XML 文档的结构，需要在解压过程中使用不同的方式进行解析。但是，它们可以实现更好的压缩比。例如，XSeq 是基于语法的可查询 XML 压缩方案，它采用了著名的基于语法的文本串压缩算法 Sequitur。

在 XSeq 中，输入 XML 文件的标记被分隔到一组容器中，然后使用 Sequitur 对每个容器进行压缩。Sequitur 压缩算法是线性时间在线算法，为给定的字符串输入生成了一种与上下文无关的语法。使用定义的上下文无关语法，XSeq 可以避免无关压缩数据的后续扫描，只处理将通过给定查询进行匹配的数据值。此外，上下文无关的语法允许 XSeq 直接通过压缩文件处理查询，而不必对文件进行全部或部分解压缩。为了关联存储在不同容器中的数据值并加快查询评估速度，XSeq 使用了一组存储在压缩文件中的索引，并在处理规则内容之前将它们加载到内存中。例如，它使用了一些结构性索引，通过这些索引在容器中快速定位每个数据值， 而无需进行解压缩处理，同时头文件索引中包含指针列表，这些指针指向文件中每个容器的入口。

TREECHOP XML 压缩器是另一种可查询 XML 压缩器，在使用该压缩器时，压缩流程以构建 XML 文档的基于 SAX 的解析开始，并按照最深者最先的顺序将已解析的标记写出到压缩流中。每个节点的代码字的前缀是其父节点的码字，如果 XML 文档树中的两个节点拥有相同的路径，则它们共享相同的代码字。每个 CDATA 部分、注释、处理指令和非叶节点都被分配一个二进制代码字。该代码字根据树节点的路径进行唯一分配。因为树节点编码都按照最深者最先的顺序被写入压缩流， 因此解码器可以使用自适应编码信息，以递增方式重新生成原始 XML 文档。在 TREECHOP 中，可以通过压缩流使用单一扫描，执行精确匹配和范围查询。

XQuec 系统基于 XML 文档内的分隔结构和内容，将片段和存储模型用于已压缩的 XML 文档。此外，它通过正确选择将容器进行分组的方法，确保属于同一个组的容器也会在查询谓语中一起出现。为了执行压缩域内的谓语评估，它确保涉及到谓语的容 器属于同一个组，并采用在压缩域中支持该谓语的算法进行压缩。关于谓语的信息可以使用可用查询工作负载进行推测。XQueC 利用查询工作负载信息，根据源模型将容器分为不同的集，并为每个集分配最适当的压缩算法。XQueC 还设计了用来评估 XML 查询的代数。该代数由基于成本的优化器使用，该优化器能够自由混合使用常规运算符以及与压缩有关的运算符。

 

结束语

在这篇概述性文章中，介绍了最先进的 XML 压缩技术。在该域的第一次实现中，XMill 展示了 XML 压缩机制的主要创新。它介绍了一种思路，即将 XML 文档的结构部分和数据部分分隔开，然后将相关的数据项归入同质容器中，对这些同质容器单独进行压缩。这种分隔改进了利用通用压缩器或其他压缩器机制对同质 容器的进一步压缩，因为它们能够更轻松地检测冗余数据。

其他大多数 XML 压缩器以不同的方式模拟这种思路。压缩时间和解压时间指标在区别不同的 XML 压缩技术方面发挥了至关重要的作用。原则上，依赖于模式的 XML 压缩器并不可取，并且实际上也不经常用到，因为 XML 文档的模式信息并不总是可用，或者不是所要求的格式（DTD、XML Schema、RElaxNG）。尽管可查询 XML 压缩器对于许多应用非常重要，但是它没有可靠的基于语法的 XML 压缩技术，也没有公开可用的可查询 XML 压缩器。这两个领域为 XML 压缩方面的进一步研究和开发提供了许多有趣的途径。

 

参考资料

学习

• XML 1.0 规范，W3C：访问该资源，了解关于 XML 功能的具体细节。
  
  
• The XML FAQ (Editor, Peter Flynn)：在另一个卓越的 XML 信息源查找许多关于 XML 的常见问题的解答。
  
  
• XML DOM 教程（来自 W3schools.com）：探索这个标准方式访问和操作 XML 文档。本教程向你展示了哪些基于 XML 的界面可用于浏览器（以及哪些浏览器支持这些界面）。
  
  
• 理解 DOM（Nicholas Chase, developerWorks，2007 年 3 月）: 了解本教程中 DOM 文档的结构。
  
  
• XML and data compression: Optimize your XML information with data compression ：查看这个 developerWorks 知识路径，其中介绍了数据压缩的理论和实际细节。
  
  
• Data compression using adaptive coding and partial string matching [John G. Cleary 和 Ian H. Witte, IEEE Trans. Commun. OM-32 (4), 1984]：探索部分字符串匹配如何解决高阶 Markov 模型，以及快速形成的需求。
  
  
• Merging prediction by partial matching with structural contexts model. Proceedings of the Data Compression Conference [Joaquin Adiego、Pablo de la Fuente 和 Gonzalo Navarro; (DCC)美国，华盛顿，2004 年]：考虑压缩结构化文档的文本结构，并学习以提高基本 SCM 技术的压缩比。
  
  
• Compressing XML documents using recursive finite state automata[Hariharan Subramanian and Priti Shankar, Proceedings of the 10th International Conference on Implementation and Application of Automata (CIAA), Sophia Antipolis，法国，2005 年]：阅读关于从 DTD 规范自动生成用于 XML 文档的压缩器。
  
  
• XGRIND:A query-friendly XML compressor, in: [Pankaj M. Tolani and Jayant R. Haritsa, Proceedings of the 18th International Conference on Data Engineering (ICDE), Washington, DC, USA, 2002]: 了解更多关于支持查询和重复使用标准的 XML 技术的压缩工具。
  
  
• TREECHOP: A tree-based query-able compressor for XML, Technical report(Gregory Leighton, Tomasz Muldner, and James Diamond; Jodrey School of Computer Science, Acadia University, 2005)：探索无损 XML 压缩，支持查询压缩的 XML 数据而无需完全解压。
  
  
• Supporting efficient query processing on compressed XML files[Yongjing Lin, Youtao Zhang,Quanzhong Li, and Jun Yang; Proceedings of the ACM Symposium on Applied Computing (SAC), New York, USA, 2005]：阅读关于基于 Sequitur 压缩算法的 XML 压缩方案。
  
  
• XPRESS: A queriable compression for XML data(Jun-Ki Min, Myung-Jae Park, and Chin-Wan Chung; Proceedings of the ACMSIGMOD International Conference on Management of Data, California, USA,2003)：检查支持根据反向算术编码对压缩 XML 数据进行直接、高效地查询评估的 XML 压缩器。
  
  
• Compression and explanation using hierarchical grammars [Craig G. Nevill-Manning and Ian H. Witten, Computer Journal 40(2), 1997]：了解离散符号序列的层次结构，以及 SEQUITUR 如何使用该信息用于数据压缩。
  
  
• XQueC: Pushing queries to compressed XML data[Andrei Arion, Angela Bonifati, Gianni Costa, Sandra D'Aguanno, Ioana Manolescu, and Andrea Pugliese; Proceedings of 29th International Conference on Very Large Data Bases (VLDB), Berlin, Germany, 2003]：了解关于 XQueC 系统的更多信息，该系统压缩 XML 数据，并尽可能在其压缩表格下对数据进行查询。
  
  
• XML compression techniques: A survey and comparison [Sherif Sakr, Journal of Computer System Science (JCSS) 75(5), 2009]：仔细阅读本次 XML 压缩方法调查。
  
  
• XML 新手入门 获取您学习 XML 所需的参考资料。
  
  
• developerWorks 中国网站 XML 技术专区：寻找提高您在XML 领域技能所需的资源，包括 DTD、模式和 XSLT。参见 XML 技术文档库 获取广泛的技术文章和技巧、教程、标准和 IBM 红皮书。
  
  
• IBM XML 认证：了解如何能够成为 XML 领域的 IBM 认证开发人员及相关技术。
  
  
• developerWorks 技术活动 和 网络广播：随时关注这些会议中涉及的技术。
  
  
• developerWorks 播客：聆听针对软件开发人员的有趣的访谈和讨论。
  
  
• developerWorks 演示中心：观看面向初学者的产品安装和设置演示，以及为经验丰富的开发人员提供的高级功能。
  
  

获得产品和技术

• The gzip website：下载并试用 gzip (GNU zip)，一个旨在取代 compress的压缩工具。
  
  
• The bzip2 website：下载并试用这个免费提供的、高品质的数据压缩器。
  
  
• The XMill project website：下载并试用用户可配置的 XML 压缩器，该压缩器将结构、布局和数据分隔开，并将数据元素分发到不同的数据流。
  
  
• The XMLPPM project website：下载并试用结合了用于文本压缩的 PPM 算法和树形结构的 MHM 数据的数据压缩程序。
  
  
• The RNgzip project website：下载并试用基于文档类型的压缩技术，表达为 Relax NG 模式。
  
  
• IBM 产品评估试用版软件：下载或 IBM SOA 人员沙箱 中查看在线试用产品，从 DB2®、Lotus®、Rational®、Tivoli® 和 WebSphere®获取应用程序开发工具和中间件产品。
  
  

讨论

• XML 专区讨论论坛: 参与多个与 XML 相关的讨论。
  
  
• 加入 developerWorks 中文社区：查看开发人员推动的博客、论坛、群组和 wikis，并与其他 developerWorks 用户交流。
  
  

关于作者

SherifSakr 博士是 National ICT Australia (NICTA) 软件系统集团的研究科学家，NICTA 位于澳大利亚悉尼。他也是新南威尔士大学 (UNSW) 计算机科学与工程学院 (CSE) 的联合讲师。2007 年，他获得了德国康斯坦茨大学的计算机科学博士学位。他分别在 2000 年和 2003 年获得了埃及开罗大学计算机和信息学院的计算机科学信息系统专业的理学学士学位和硕士学位。在 2011 年，Sakr 博士担任了位于美国华盛顿州雷蒙德的微软研究院 eXtreme Computing Group (XCG) 的客座研究科学家的职务。