级别： 初级 David Mertz，博士 (mertz@gnosis.cx), 简化工程师, Gnosis Software，Inc.
2002 年 4 月 01 日 在本专栏以前的文章中，David 研究过一些能够用来可逆地重新构造 XML 文档以改进压缩的技术。然而，对于大型 XML 文档和嵌入式处理，在压缩过程之前重新构造整个源文件似乎不太实际。在本文中，David 研究了重新构造技术在多大程度上适合块级别处理 ― 在压缩改进和 CPU／内存需求方面。
和其它形式的数据表示相比，XML 文档往往很大。尽管这样能提供详细的信息，但 XML 的简单性和通用性却使得它物有所值。很多时候，XML 的大小实际上并没有多大影响 ― 硬盘很便宜，而且文件传输用的时间也许只占整个处理时间的一小部分。但另外一些时候，带宽和存储空间会非常重要。
举个例子，表示面向表的数据的 XML 文档的大小是采用 CSV 或数据库表示甚至平面文件的 3 倍，这一点并不少见。类似的文件大小增加在表示 EDI 数据时非常典型，如对于 ebXML 项目。在许多这样的环境中，您要从数兆字节的数据源文件着手，因此若将它们增加几倍会引起不便，尤其对于传输用途。
当考虑压缩文档时，您通常会首先想到象 Lempel-Ziv、Huffman、Burrows-Wheeler 这样的常规压缩算法，以及实现转换的公共实用程序。这类实用程序的例子有 gzip、zip 和 bzip2（以及每个实用程序的库版本）。这些实用程序往往能很大地减少 XML 文件的大小 ― 尤其是 bzip2。较少有人知道 PPM 压缩技术 ― 它通常甚至能以比 bzip2 更高的压缩比进行压缩 ― 但代价是比本来就缓慢的 bzip2 更多的时间需求。在压缩 XML 文档方面处于领先地位的是 xmlppm，它利用的技术与本专栏介绍的那些特定于 XML 的技术相似；然而，xmlppm 比下面介绍的 xml2struct 慢得多，而且更消耗内存。但如果您有时间和内存，xmlppm 可以达到令人惊讶的压缩比。
当使用 XML 文档的特定结构以产生
可压缩性更好的表示时，您就可以取得好得多的压缩比。XMill 实用程序就是该技术的实现（xmlppm 也是利用该技术，只是以更复杂的方式）。然而，以前将 XML 重新构造与一般压缩算法相结合的技术是作用于整个 XML 文档级别的。XMill、xmlppm 和我的原始 xml2struct 实用程序都是如此。所有这些技术背后的一般原则是定位文档的相对同构部分，然后在已转换文件中将它们相互组织在一起。这样进行分组之后，标准压缩程序压缩的效果会更好（高压缩比，不过通常也是名义上很快）。特别地，XML 通过将文档特定部分的内容括在具有相同名称的元素标记中，来间接地表明它们之间的相似性。
若必须处理许多兆字节的 XML 文档，花费内存、磁盘空间和 CPU 开销来操作这么大的文档通常是不实际的。如果能不对整个数兆字节大小的源文件而只对已解析的块进行处理，连续读取并且使用相似的技术，那么问题就解决了。值得就这一主题回顾一下本专栏以前的文章，被“广泛”采用的 Burrows-Wheeler 算法执行的重新构造与 xml2struct 使用 XML 知识所执行的大部分相同，并产生相似的压缩结果。Burrows-Wheeler 算法的效果很大程度上取决于对大量输入源文件执行全局分析的能力 ― 您将在下面的量化分析中看到：Burrows-Wheeler 在解决来自 XML 文档相对较小的串行块时失去了所有的优势。在这一约束下，重新构造过程技术在更大程度上依然有效。
使用方案
本文中介绍的块级别重新构造／压缩技术有几个实际的应用程序。在最简单的情况中，XML 文件相当大（数百或数千兆字节）、内存和磁盘空间比较有限（没有用于该过程的吉字节大小的额外内存或存储），而且通道成本比较昂贵（发送半吉字节与发送一吉字节相比，就是非常值得的节省）。用于最简单情况的方案会利用与下面相似的协议：
xmlstruct 通信协议
- 机器 A 有通向机器 B 和大型 XML 源文件（一个文件或一些动态生成的 XML 内容）的通道。
- 机器 A 上的 SAX 解析器每次遇到一块 XML 源文件就刷新其数据 。
- 重新构造已刷新的块。
- 用传统工具（如 gzip 或 bizp2）压缩已刷新的块。
- 发送重新构造／压缩的块。
- 机器 B 通过通道接收块。 以串行方式重新构造底层 XML。每块 XML 数据可以附加到文件后；或提供给 SAX 解析器，该解析器作用于元素和内容并在处理完毕后废弃 XML 数据块。
技术概述
只需要对 xml2struct 的重新构造技术稍加更改就可以适应任意块大小。本文压缩文档中包含两个块级别重新构造的实现。严格参照了“XML 问题 #13：探索文档的平均信息量”（请参阅
参考资料）中介绍的 xml2struct.py 实用程序模式的 Python 实现 ― 代码更加紧凑而且更易于理解。还开发了一个“经过优化的” C 实现来研究算法的速度性能。
在原始算法中，包括了作为重新构造的 XML 文档第一个定界节的标记列表。该标记列表 ― 在实际的文档解析期间在特别基础上生成 ― 用作结构示意图中使用的单字节标记占位符的索引。使用字节索引值来代替标记的策略在某种程度上减少了重新构造后的文档的大小，但也限制算法只能处理不同标记数少于 254 的 DTD。
在以下的块级别算法修订中，我假设可以独立使用标记表。本文压缩文档中提供了从 DTD 创建标记表的实用程序函数。假设通道两端都有必需的 DTD，一切正常，若没有 DTD，任何其它指定标记次序的格式也可奏效。
唯一需要的重大修改是增加新的（第一个）定界文档节以指示当前的元素嵌套情况。在原始文档级别格式中，每个开始标记与一个结束标记配对。但因为 XML 文档在块级别格式中是从任意位置断开的，因此有必要记录打开元素（块在其中开始）的堆栈。第一个被解析的块有这个第一节的空白字段；后续块可能有一个或多个字节列出尚未关闭的标记的索引。
重新构造的块的格式相当简单：
- 开始标记的列表：每个开始标记是单个字节（ 字节值 >= 0x03）；将该列表压入标记列表堆栈以匹配相应的结束标记字节
- 节定界符：0x00（空字节）
- 块文档结构的紧凑表示法： 其中每个开始标记由单个字节表示，出现的内容由 0x02 字节表示；结束标记由 0x01 字节表示并且必须与相应的开始标记向后匹配
- 另一个节定界符：0x00（空值字节）
- 文档结构示意图中指示的所有元素的内容 按元素类型分组：每个单独的内容项由 0x02 字节定界，新类型元素的开始由 0x01 字节定界（最后一个元素没有严格要求，但它使逆向转换更容易）
要注意演示代码的两个限制。第一个限制完全是研究实现方便的结果：元素属性不是由当前解析器处理。这主要是为了使所呈现的代码更易于理解。添加类属性的块是对当前技术的简单扩展，不太可能对压缩或性能有较大的影响。
第二个限制更为重要。只有当遇到结束标记时才刷新块。若单个元素的 PCDATA 内容不是始终都小于所用的块大小，则不强制块大小。例如，包含一个大的
<pre> 元素的大型 XHTML 文档不会强制任何合理的块大小。更改这个限制是可能的（尽管这样做会在 SAX 框架内造成不雅效果）。不过，指出这一点并没有很大意义，因为重组元素内容大于块大小的文档并不合理（而且通常不应该执行）。一种会引起问题的情况就是正在执行的系统对可用内存有严格限制，并且遇到了一个大得无法处理的块。
通常情况下，输入 XML 块比指定的块大小略大一些，不过一旦用单字节标记占位符替代标记，则替换后的大小通常比块大小略小一些。一旦对块进行了压缩，则压缩的块大小明显小于输入块大小。
量化压缩
出于量化用途，我使用前面研究中所介绍的两个有代表性的相同 XML 文档。一个是面向散文的文档，莎士比亚的
哈姆雷特的 XML 版。另一个 XML 源文档是从一个 1MB Apache 日志文件创建的，在文档中用 XML 标记环绕日志文件中的每个字段（和每个输入项）。尽管所用的标记不是特别详细，但文件还是扩充至大约 3MB。
在下面的图中，前面的两个灰色条表示简单的文件级别压缩（使用 gzip 和 bzip2）所取得的压缩效果。正如上面所讨论的，对大文件进行文件级别的压缩可能不太实际；但正如预期的那样，文件级别的压缩会取得更好的结果，因为它是在整个文件中寻找重复的字符串。通常，要使块级别压缩的效果与文件级别压缩几乎相同，块的大小必须要有 100k 或更大。尽管如此，如果您不得不处理吉字节的源文档，则相比较之下，即使兆字节大小的块也显得很好管理。
图后部的绿色条和蓝色条表示不使用重新构造过程对块进行压缩所取得的压缩效果。
最后，中间的红色条表示结合了 zlib 库压缩的 xml2struct.py 的压缩性能。使用 bzip2 库会取得更好的压缩效果。但没有对此进行测试，因为最能预见的将来的用途可能就是消除了 bzip2 的速度劣势。然而，如果带宽比 CPU 时间更重要，那么添加 bzip2 压缩层可能会使我们更加获益。
让我们来研究一下结果，随后我将做一些注释。我试过的块大小有 1k、10k、100k 和 1MB。首先是
哈姆雷特的压缩比较图，然后是 weblog 的压缩比较图：
hamlet.xml 和 weblog.xml 中都出现了同样的常规模式，但 weblog.xml 中的模式
更强。日志文件高度重复的结构使重新构造能发挥其最大优势。块大小比较小时，压缩比文件级别压缩差很多。块大小约为 10k 时，块级别压缩开始显得比较不错；块大小为 100k 时，块级别压缩就非常接近文件级别压缩技术了。
本文中图表最有趣的部分是重新构造块策略的压缩特征。重新构造始终比简单的块级别 zlib 的行为有改进（对于 weblog 提高约 30%，对于
Hamlet则少一些）。当块大小为 100k 左右时，重新构造比文件级别 gzip 要好得多，这是很好的结果。
令人惊奇的结果是块级别 bzip2 压缩的行为。正如预期的那样，一旦块大小变大，是否使用块级别压缩并没有区别。不过块大小必须达到 1MB 才能完全消除差异。然而，块大小较小（尤其是 1k，甚至是 10k）时，块级别 bzip2 表现得非常差。之前的重新构造并不能明显地改进这一点。事实上，在块大小为 1k 时，bzip2 始终比 zlib 差得多。
量化 CPU 使用和转换率
通过使用 xml2struct 优化的 C 实现，我研究了重新构造和压缩的执行速度。如果您使用这些程序作为通道中介，则能使输出通道饱和的处理能力至关重要。这里给出的时间是用 Linux time 实用程序获得的。报告了运行的经过时间；每次运行显示出接近 100% 的 CPU 使用率，并且主要是用户时间。块大小对所有被检查转换的运行时间产生如此小的影响使我觉得很奇怪。
这个综合计时模式非常清楚。C 实现中的重新构造非常快；gzip 甚至更快；bzip2 较慢。顺便说一下，PPM 又比 bzip2 要慢 10 多倍。我引入 Python 实现的运行时间作为基线；该版本完全没有优化。可以使它更快，但可能不会超过 2x。通常，Python 实现和 bzip2 过程对于大多数通道饱和使用都
太慢。
这些运行时间对于输出通道饱和有什么意义？在一台 PIII-733 机器上用不到一秒的时间就可以重新构造一个 3 MB 文件，并且块大小对于重新构造的速度只有略微区别。用 gzip/‘zlib’压缩已重新构造的文件使处理时间又增加了四分之一秒。其处理量是大约 20 兆位/秒；换句话说，一台执行 xml2struct+gzip 的 PIII-733 可以使两条 10 兆位以太网通道或大约 13 条 T1 线路饱和。若专门用于 xml2struct 处理，则一台较慢的 Pentium 应该足以填满一条 T1 线路，该线路专门用于有效地发送 XML 文档。另一方面，以超过 1GHz 的时钟速度运行的 Intel P4 或 AMD Athlon 应该能够满足一条 45 兆位 T3 线路的需求。
结束语
若采用标准压缩算法，文档结构明显影响其可压缩性。因为 XML 将其语义结构的大量详细信息编码成自己的语法形式，
重新构造这样的文档可以提高其可压缩性。此外，我说明了重新构造技术应遵从于使用来自大的 XML 文档的已解析块的串行化。而且，xml2struct 算法可以用优化的 C 实现，其性能特征足以允许它使用当代 CPU 和目前常用的通道带宽使来自 XML 服务器的专门输出通道饱和。
参考资料
关于作者
对本文的评价
| 
