XML问题#13：XML和压缩

XML问题#13：XML和压缩
 
－－探索文档的平均信息量

David Mertz 博士 (mertz@gnosis.cx)

内部设计师，Gnosis Software，Inc.

2001 年 9 月

本 XML 问题专栏探索了几种压缩 XML 文档的方法。XML 中的特殊结构允许它对最原始的压缩技术进行某些改进。专栏作者 David Mertz 阐明了利用它们的几种方法，以及包含演示这些技术的样本代码。

XML 作为一种格式具有许多优良的特性；它是表示任意数据结构的完美通用方法，并且它是人可读的（或多或少的）。但是 XML 有一个非常显著的缺点。XML 文档是冗长的；并不仅是在文字方面有点冗长，其大小也几乎都是令人难以置信的巨大。多数时候，XML 的这个缺点实际上没什么影响。DASD 是便宜的，并且线路上的时间可能仅是过程中总时间的一小部分。但其他时候，带宽和存储空间可能是重要的。

要量化事物，对于表示面向表格数据的 XML 文档是 CSV 或数据库表示或甚至是平面文件的三倍大是再平常不过的。类似的增长在表示 EDI 数据中是很典型的（例如对于 ebXML 项目）。在许多这样的环境中，人们是从有好几兆字节的数据源着手。使这些文件增大几倍会带来不便，特别是用于传输目的。例如，出于本文目的我创建了一个大约一兆字节的 Apache 访问日志文件的 XML 表示。这创建了是基本面向行日志的 3.18 倍大小的 XML 文档。此过程中添加的唯一信息是一些字段的描述名称，但那本来也可以使用不超过一百个字节的、简单的标题行指定。此外，我的特定 XML 表示没有在标记中包含任何名称空间，它会进一步增加大小。

当考虑压缩文档时，通常首先考虑常用的压缩算法，如：Lempel-Ziv 和 Huffman，以及在它们上面实现变化的一些常用实用程序。特别是，在类 Unix 平台上，首先想到的通常是实用程序 gzip；在其它平台上，zip 更为常用（使用实用程序如：PKZIP、Info-ZIP 和 WinZip）。现已证明 gzip 始终要优于 zip，但使用的人较少。这些实用程序实际上意在充分地减少 XML 文件的大小。但是，同样证明了通过两种方法 — 单独或组合可以获得相当好的压缩率。

第一种技术使用 Burrows-Wheeler 压缩算法而不是顺序 Lempel-Ziv 算法。特别是，相对较少使用的实用程序 bzip2 （或者与其相关库和 API）是许多系统平台上的 Burrows-Wheller 的实现（并且伴随完整的源文件和 BSD 风格的许可证）。Burrows-Wheeler 通过对未压缩的源文件中的相关字符串进行分组来操作，而不是象 Lempel-Ziv 风格那样构建一个字符串重现的字典。在许多文件类型上，bzip2 始终比 gzip 获得较好的压缩效果，而对 XML 文档的效果尤其显著。bzip2 通常较 gzip 慢是其不足之处。再次，低带宽常会掩盖 CPU 或内存限制的算法中的速度差异。

第二种技术是利用 XML 文档非常特定的结构生成更可压缩的表示。XMill 实用程序就是这种技术的一种实现，遵守 AT&T 的自由许可证就可以使用（带 C++ 源文件）。然而，看起来 XMill 许可证上需要某些点击完成风格的限制，因而不能由其他方直接发布（至少我是这样理解的）。我对同一通用技术创建了自己的实现，并且我会在本文中呈现该实现。此处代码向公众域发布，实现的技术由本人独立开发且与 XMill 有“鸟瞰”的类似性：有时 XMill 更好，有时我更好（但 XMill 可能总是比我的初始实现更快，因其只关注压缩结果）。

比较基本算法

本文中，我获取或创建了四个基本文档用于比较的目的。第一个是莎士比亚的戏剧 哈姆雷特作为 XML 文档（请参阅参考资料）。标记中包括如 <PERSONA>、<SPEAKER> 和 <LINE> 等标记，这些十分自然地映射到人们可能在印刷拷贝中遇到的排版形式。为了对 XML 标记如何有助于文档大小和可压缩性作比较，我从 hamlet.xml 派生了一个文档 hamlet.txt，仅仅只是删去所有 XML 标记而保留其内容。这种派生是不可逆的且是一种信息的绝对丢失。例如，阅读 hamlet.txt 的人从语义上去确定哪个内容是“speaker”名称以及哪一个是“行”不会有什么大困难，而计算机可能无法轻易地重新生成源 XML 文档。

下两个文件是 Apache Weblog 文件（一组简洁的面向行的记录）及从这个文件创建的 XML 文档。因为源文档是日志文件，在转换中无信息丢失，而从 XML 重新创建原始格式的文档非常繁琐。当然，对于日志文件格式您不能使用 XML 解析器，或DOM，或验证器，或 DTD。让我们看看清单 1 中的基本文档大小。

清单 1 .基本文档的目录清单

 288754  hamlet.xml
 188830  hamlet.txt
 949474  weblog.txt
3021921  weblog.xml

在两种案例中，XML 格式文档都非常大。在哈姆雷特示例中，由于文本版本中实际信息内容也减少而使比较不是完全公平。但是对于 Weblog 文件，XML 开始看上去相当槽糕。但凡事皆不可只看其表面。压缩程序做了一件相当好的工作 — 将文档压缩到其实际信息内容大小，并且在已压缩版本中无意义的填充趋向于零大小（如果一切顺利的话，压缩是渐进地）。让我们在清单 2 和清单 3 中尝试 gzip、zip 和 bzip2 。

清单 2 .已压缩的莎士比亚目录清单

  78581  hamlet.xml.gz
  72505  hamlet.txt.gz
  78696  hamlet.xml.zip
  72620  hamlet.txt.zip
  57522  hamlet.xml.bz2
  56743  hamlet.txt.bz2

清单 3 .已压缩的 Weblog 目录清单

  91029  weblog.txt.gz
 115524  weblog.xml.gz
  91144  weblog.txt.zip
 115639  weblog.xml.zip
  56156  weblog.txt.bz2
  66994  weblog.xml.bz2

通过研究两个清单中的文件大小显现出来一些有趣的事情。对于两种风格的文档而言（对于每种压缩技术），已压缩文件中的文件大小差异比 XML 和文本原始文件之间的差异要小。同样值得注意的是：对应的案例中 gzip 和 zip 非常接近形成一组，而 bzip2 始终都做得更好。此外，当对莎士比亚文档使用 bzip2 时，文本格式和 XML 格式之间压缩大小差异几乎可忽略，尽管 XML 基本文档比文本格式的大 53％ 。

而 Weblog 代表了一个问题案例。虽然压缩相当多地减小了 XML 转换的膨胀，即使 bzip2 版本仍然让 XML 标记使大小增加了大约 20％ 。这未必是灾难，感觉好象我们应当能够将其压缩至真实的信息内容大小。

可逆转换

当 XML 文档涉及压缩时有效率相当低的形式，正如您将看到的，bzip2 通过对字符串重新分组就稍微减轻了这种低效性。就本质而言，XML 文档是十分不同部分的混合物 — 不同类型的标记、属性和元素体。如果您能获取每个相对一致的事物的集合并且在已转换的文件中将它们相互紧密分组，标准压缩程序将会有很多工作要处理。例如：如果 Weblog 中每个 <host> 标记体出现在另一个附近，包含主机 IP 地址的那块东西就非常易于压缩。本处的技巧在于：找到将 XML 文档转换成包含所有相同信息的一种方法，而以一种对压缩程序友好的风格构造布局。

实用程序 xml2struct.py 和 struct2xml.py 恰恰能做我们所希望的。下面的版本包含了“几点限制”，但它们演示了涉及的原理。一些限制在于每个文档的不同标记限制为 253 个，并且不处理属性和处理指令。而修订那些限制不会改变结果的本质。XMill 执行类似的转换，但带有一些额外选项和较少的限制。

"struct"文档的常用格式如下：

原始 XML 文档中出现的标记列表，由新行字符分隔。

章节分隔符：0x00 （空字节）

总体文档结构的紧凑表示，每个开始标记由单一字节表示，内容的出现由 0x02 字节标记。

另一个章节分隔符：0x00 （空字节）

在文档结构示意图中显示的所有元素的内容，按元素类型分组。每个单独的内容项由 0x02 字节分隔，而新类型元素的开始由 0x01 字节分隔（最后的一个并非严格必需的，但它使逆向转换更简便）。

下面是实现和逆转所描述转换的完整 Python 代码。用另一个编程语言实现这一转换同样也是简单的：

清单 4 .xml2struct.py

import sys
import xml.sax
from xml.sax.handler import *

class StructExtractor(ContentHandler):
    """Create a special structure/content form of an XML document"""
    def startDocument(self):
        self.taglist = []
        self.contentdct = {}
        self.state = []             # stack for tag state
        self.newstate = 0           # flag for continuing chars in same elem
        self.struct = []            # compact document structure

    def endDocument(self):
        sys.stdout.write('\n'.join(self.taglist))
                                    # Write out the taglist first
        sys.stdout.write(chr(0))    # section delimiter \0x00
        sys.stdout.write(''.join(self.struct))
                                    # Write out the structure list
        sys.stdout.write(chr(0))    # section delimiter \0x00
        for tag in self.taglist:    # Write all content lists
            sys.stdout.write(chr(2).join(self.contentdct[tag]))
            sys.stdout.write(chr(1)) # delimiter between content types

    def startElement(self, name, attrs):
        if not name in self.taglist:
            self.taglist.append(name)
            self.contentdct[name] = []
            if len(self.taglist) > 253:
                raise ValueError, "More than 253 tags encountered"
        self.state.append(name)     # push current tag
        self.newstate = 1           # chars go to new item
                                    # single char to indicate tag
        self.struct.append(chr(self.taglist.index(name)+3))

    def endElement(self, name):
        self.state.pop()            # pop current tag off stack
        self.newstate = 1           # chars go to new item
        self.struct.append(chr(1))  # \0x01 is endtag in struct

    def characters(self, ch):
        currstate = self.state[-1]
        if self.newstate:           # either add new chars to state item
            self.contentdct[currstate].append(ch)
            self.newstate = 0
            self.struct.append(chr(2))
                                    # \0x02 content placeholder in struct
        else:                       # or append the chars to current item
            self.contentdct[currstate][-1] += ch

if __name__ == '__main__':
    parser = xml.sax.make_parser()
    handler = StructExtractor()
    parser.setContentHandler(handler)
    parser.parse(sys.stdin)

使用 SAX 而不是 DOM 使这一转换相当节省时间，即使时间不是开发它的主要考虑事项。要逆向转换，可以使用清单 5 。

清单 5.struct2xml.py

def struct2xml(s):
    tags, struct, content = s.split(chr(0))
    taglist = tags.split('\n')      # all the tags
    contentlist = []                # list-of-lists of content items
    for block in content.split(chr(1)):
        contents = block.split(chr(2))
        contents.reverse()          # pop off content items from end
        contentlist.append(contents)
    state =  []                     # stack for tag state
    skeleton = []                   # templatized version of XML
    for c in struct:
        i = ord(c)
        if i >= 3:                  # start of element
            i -= 3                  # adjust for struct tag index offset
            tag = taglist[i]        # spell out the tag from taglist
            state.append(tag)       # push current tag
            skeleton.append('<%s>' % tag)
                                    # insert the element start tag
        elif i == 1:                # end of element
            tag = state.pop()       # pop current tag off stack
            skeleton.append('</%s>' % tag)
                                    # insert the element end tag
        elif i == 2:                # insert element content
            tag = state[-1]
            item = contentlist[taglist.index(tag)].pop()
            item = item.replace('&','&')
            skeleton.append(item)   # add bare tag to indicate content
        else:
            raise ValueError, "Unexpected structure tag: ord(%d)" % i

    return ''.join(skeleton)

if __name__ == '__main__':
    import sys
    print struct2xml(sys.stdin.read()),

压缩转换结果

当尝试压缩结果时，所讨论转换的真正要点来了。如果一切都按计划进行，foo.struct 比 foo.xml 更可压缩，即便是两者包含同样的信息（这是可证明的，因为二者是对称可派生的）。从某种意义上，xml2struct.py 已经是一种压缩算法（它生成了相对较小的文件），但真正要点是并非直接使用它而是将其作为进一步压缩的基础。

让我们看看一些大小，包括几个上面重复提及的。XMill 产生的某些结果也放入以作比较；您将能够因包含名称 .xmi 而识别出它们。（XML 有使用 gzip 和 bzip2 算法的版本。）

清单 6.“结构化 XML”的目录清单

 228610  hamlet.struct
  57533  hamlet.struct.bz2
  57522  hamlet.xml.bz2
  71060  hamlet.struct.gz
  78581  hamlet.xml.gz
  61823  hamlet.xmi.bz2
  75247  hamlet.xmi.gz

这段文档上的结果稍嫌混杂。“重新构造” XML 文档对 gzip 相当有帮助。原始 XML 文件上普通的旧 bzip2 在生成可压缩的结构上比我的尝试好 11 个字节。当然，值得欣慰的是 XMill 有类似的表现，但比我的转换差。

该技术对 Weblog 文件做的相当好。这里它实际产生作用。

清单 7.“结构化 XML”的目录清单 2

1764816  weblog.struct
  59955  weblog.struct.bz2
  66994  weblog.xml.bz2
  56156  weblog.txt.bz2
  76183  weblog.struct.gz
 115524  weblog.xml.gz
  59409  weblog.xmi.bz2
  74439  weblog.xmi.gz

如前所述，重新构建 XML Weblog 极大地帮助了 gzip 压缩。但由于 gzip 不再是我喜爱的技术，因而仅能吸引我部分注意力。我真正的兴趣在于我已经将这个已经相当好的 bzip2 压缩率改进了 11％。虽然可能没什么大不了，但对于为兆字节而发愁的问题来说已经足够。不管怎样，本例中 XMill 改进比 xml2struct.py 更好。同样令人感兴趣的是，这一重新构建的 XML 的压缩在原始文本形式的 Weblog 获得的最佳压缩的 7％ 以内。

结束语

尽管这里呈现的实用程序是一种初步的尝试，即便是在这一早期形式中它也做得令人称奇的好 — 至少在某些情况下 -- 从压缩的 XML 文件中榨干最后那几个字节。经过一些改进和实验，我期望能获得几个百分点的降低。使编写这一实用程序困难的一部分原因在于 bzip2 从一开始就完成了如此完美的工作。当我开始凭经验测试时，我实在惊奇 Burrows-Wheeler 算法的有效性。

某些商业实用程序尝试利用压缩文档的特定 DTD 知识的方式执行 XML 压缩。这些技术相当有希望获得附加压缩。xml2struct.py 和 XMill 作为简单的命令行工具的优点在于：您可以透明地应用于 XML 文件。但是，每次压缩定制编程并非总是值得或可能的。榨干更多字节也许是可达到的目标。

 参考资料

• 加入有关本文的论坛。
  
• 本文的许多灵感来源于对 XMill XML 压缩程序的工作。在 XMill 页面 您可以发现相关信息和一个可下载的版本。许可证需要点击完成，不幸的是：下载页面看来有个错误的脚本，以致于并不允许所有站点里都可下载。
  
• 完整的 XML 形式的莎士比亚戏剧可从 ibiblio.org 下载。用于测试的文档 hamlet.xml 就取自那里。
  
• M. Burrows 和 D.J. Wheeler 1994 年合著的文章“ A Block-sorting Lossless Data Compression Algorithm”，介绍了现在称为 Burrows-Wheeler 的算法。在相当流行的实用程序 bzip2 中实现了该技术。
  
• 许多类 Unix 系统包括了 bzip2 作为其标准发行版的一部分。对于其它平台或更新版本，可以在 Redhat 中找到 bzip2。
  
• 我撰写了我认为是 数据压缩相当常用的介绍。
  
• 了解以前 David Mertz 的 XML 问题专栏：
  
• • XML 问题 #1 介绍 Python 的 xml_pickle 对象。
    
  • XML 问题 #2 描述如何使用 Python 的 xml_objectify。
    
  • XML 问题 #3 介绍 DocBook。
    
  • XML 问题 #4 继续讨论关于如何使用 DocBook 构建旧有的文档归档。
    
  • XML 问题 #5 说明如何通过 XSLT 将 XML 文档转换成 HTML 。
    
  • XML 问题 #6 比较了半打 XML 编辑器，同时特别着眼于那些适合于有大量文本的文档的工具。
    
  • XML 问题 #7 将 DTD 与 XML Schema 进行了权衡，并建议开发者在什么时间需要坚持使用 DTD 而不管 W3C XML Schema 规范有多么成熟。
    
  • XML 问题 #8 讨论了由计算机科学家概念化出来的数据模型的抽象理论是如何帮助我们开发特定的多表示数据流的。
    
  • XML 问题 #9 讨论了公众域的 sql2dtd 和 sql2xml 实用程序；这些实用程序可以不依赖 RDBMS 生成可移植 XML 结果集。
    
  • XML 问题 #10 扩展了 David 的 可爱的 Python：使用 Python 开发全文本索引器 专栏中介绍的常规全文本索引器，使它包含了特定于 XML 的搜索和索引特性，并且讨论了索引器如何利用 XML 的层次节点结构。
    
  • XML 问题 #11 重温了本系列第一个专栏中介绍的模块。
    
  • XML 问题 #12 讨论了公众域实用程序，当着手 XML 文档时，它以一种一致和可逆的方式生成 SQL 语句来创建和填充数据库。

关于作者 David Mertz 相信“少就意味着多”。可以通过 mertz@gnosis.cx 与 David 联系；在 http://gnosis.cx/publish/ 上详细介绍了他的生活。欢迎对过去的、这一篇和以后的专栏文章提出意见和建议。