レベル: 中級 David Mertz, Ph.D (mertz@gnosis.cx), Author, Gnosis Software, Inc.
2001年 9月 01日 今回のXMLの論考 では、XML文書のいくつかの圧縮方法を調べます。XMLは構造が特殊なため、単純な圧縮技法に対しては、いくつか改善が可能です。それらの改善点を活用する方法を、コラムニストのDavid Mertzが説明します。また、技法を示すためのサンプル・コードも含まれています。
フォーマットとしてのXMLには長所がたくさんあります。任意のデータ構造を表現する完全に汎用性のある方法ですし、人間にも (大体は) 理解できます。しかし、XMLには、顕著な短所が1つあります。それは、XML文書が冗長であるということです。少々 冗長であるという程度ではなく、信じられないほどの規模で冗長だと言えるでしょう。ほとんどの場合、XMLのこの欠点は大きな問題とはなりません。DASDは安価ですし、通信時間は処理時間の合計のわずかな部分を占めるに過ぎないことでしょう。しかし、帯域幅とストレージ・スペースが重要性を帯びる場合もあります。
これを量で表してみましょう。表中心のデータをXML文書で表現すると、CSVまたはデータベース表現、あるいはフラット・ファイルに比べて3倍の大きさとなることも珍しくありません。EDIデータ (ebXMLプロジェクトなど) を表現する場合も、同様の増加が見られるのが普通です。このようなコンテキストでは、何メガバイトものデータ・ソースを使って作業に取り掛かることになります。これを何倍も大きくするなら、不便なことになりかねません。伝送を目的とする場合は特にそう言えます。たとえば、わたしは、この記事のために約1 MBのApacheアクセス・ログ・ファイルのXML表現を作成しました。出来上がったXML文書は、元の行中心のログの3.18倍のサイズでした。この処理で追加された情報 はフィールドの記述名に過ぎません。しかし、これは100バイトに満たない単一のヘッダー行にも指定されたかもしれません。さらに、わたしの特定のXML表現では、タグに名前空間が含まれていなかったため、サイズがさらに大きくなった可能性があります。
文書の圧縮について考えるときにまず思い出すのは、Lempel-ZivやHuffmanなどの汎用圧縮アルゴリズムと、それらのアルゴリズムのバリエーションをインプリメントした一般的なユーティリティーでしょう。特に、UNIX型のプラットフォームの場合は、gzipというユーティリティーが最初に思い浮かぶのが普通です。他のプラットフォームの場合はzipの方が一般的です (PKZIP、Info-ZIP、およびWinZipなどを使用)。gzipはzipより一貫して優れていることが分かりますが、その差はわずかなものに過ぎません。これらのユーティリティーでも、XMLファイルのサイズを十分に小さくすることができます。しかし、2つの方法を個々に、あるいは組み合わせて使用することにより、より高い圧縮率が得られるということも分かります。
最初の技法は、Lempel-Ziv順次アルゴリズムの代わりに、Burrows-Wheeler圧縮アルゴリズムを使用するというものです。特に、bzip2ユーティリティー (またはそれに関連するライブラリーとAPI) は、一般的とは言えないものの、Burrows-Wheelerのインプリメンテーションの1つとして、多くのシステム・プラットフォームに対応しています (完全なソースとBSDスタイルのライセンスが付属)。Burrows-Wheelerは、Lempel-Zivのように出現ストリングの辞書を構築するのではなく、未圧縮ソースの関連ストリングをグループ化することによって機能します。bzip2は、多くのファイル・タイプで一貫してgzipよりも良好な圧縮が行えます。XML文書では特に劇的な効果が得られます。マイナス面として、bzip2はgzipより概して低速であることが挙げられます。しかし、帯域幅が低速であるために、CPUまたはメモリーの制約を受けるアルゴリズムの速度の違いが相殺されてしまうこともよくあるものです。
2番目の技法は、XML文書の構造が非常に特殊であることを利用して、より圧縮性 の高い表現を作成することです。XMillユーティリティーはこの技法のインプリメンテーションの1つであり、AT&Tから自由なライセンスを受けて使用可能です (C++ ソース付き)。しかし、XMillにはライセンス交付について閲覧スタイルの制限が必要なようですし、他人がこれを直接配布することはできません (少なくともわたしはそう理解しています)。わたしは、同じ汎用的な技法のインプリメンテーションを独自に作成しました。そのインプリメンテーションをこの記事の中で紹介します。ここに示すコードをパブリック・ドメインに解放します。インプリメントされた技法は独自に開発されたものであり、XMillとの類似点は大要だけです。XMillの方が動作が良好な場合もありますし、わたしの開発したものの方が良好な場合もあります (とはいえ、XMillの方がわたしの最初のインプリメンテーションに比べて常に高速と思われます。わたしのインプリメンテーションでは、圧縮結果にしか注意を払っていません)。
基本的なアルゴリズムの比較
この記事で比較を行うために、元となる4つの文書を入手または作成しました。最初の文書はシェークスピアの戯曲、ハムレット のXML文書です (参考文献を参照)。マークアップには、<PERSONA>、<SPEAKER>、および<LINE> などのタグが含まれており、それぞれ印刷されたコピーで目にする印刷上の形式に極めて自然に対応します。XMLマークアップが文書のサイズと圧縮性に与える影響を比較する目的で、hamlet.xmlからXMLタグを全部除去し、内容だけを残したhamlet.txtを作成しました。これは可逆的ではなく、情報の消失にほかなりません。hamlet.txtの読者は、意味内容を手掛かりに、どの内容が "話者" 名で、どれが "せりふ" であるかを見極めるのにそれほど困難を覚えないはずです。しかし、コンピューターが元のXML文書を再生成するのは容易ではありません。
次の2つの文書は、Apache Webログ・ファイル (行中心のレコードのコンパクトなセット) と、このファイルから作成したXML文書です。元の文書はログ・ファイルであるため、変換することで失われる情報はありません。また、XMLから元の形式を正確に再生成するのは簡単です。当然、ログ・ファイル・フォーマットに対してXMLパーサー、DOM、バリデーター、またはDTDを使用することはできません。リスト1で元の文書のサイズを見てみましょう。
リスト1. 元の文書のディレクトリー・リスト
288754 hamlet.xml
188830 hamlet.txt
949474 weblog.txt
3021921 weblog.xml
|
どちらの場合も、XMLの方がずっと大きくなっています。ハムレット の例は、まったく公平な比較とは言えません。テキスト・バージョンでは情報内容そのものも減少しているからです。しかし、Webログ・ファイルを見るなら、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. Webログの圧縮のディレクトリー・リスト
91029 weblog.txt.gz
115524 weblog.xml.gz
91144 weblog.txt.zip
115639 weblog.xml.zip
56156 weblog.txt.bz2
66994 weblog.xml.bz2
|
2つのリストのサイズを詳しく調べてみると、多くの興味ある事柄が分かります。両方のスタイルの文書について (どの圧縮技法についても) 言えることですが、圧縮ファイル同士のサイズの相違は、XMLと元テキストの差よりもずっと小さくなっています。注目に値するもう1つの点は、同じケースの場合にgzipとzipの結果は非常に近くなるのに対し、bzip2はいつもずっと良い結果を示していることです。さらに、bzip2をシェークスピアの文書に使用すると、元のXML文書のサイズが53%大きいにもかかわらず、テキスト形式とXML形式との圧縮サイズの差がほとんど無視できるほどになります。
しかし、Webログは明らかに問題のあるケースです。XML変換の結果として生じた膨張が圧縮によってかなり抑えられているものの、bzip2バージョンでさえ、XMLマークアップによって依然としてサイズが約20%も増加しています。これは必ずしも災いとは言えませんが、情報内容そのものにまで小さく圧縮できるに違いないという気がします。
可逆的な変換
XML文書は、どちらかと言えば、圧縮効率の悪い形式です。後で調べますが、bzip2はストリングの再グループ化によって、この効率の悪さをいくらか補います。しかし、実際には、XML文書は非常に異なるパーツの寄せ集めです。さまざまな種類のタグ、属性、要素の本体から成っています。比較的同種のもののセットを取り上げて、変換ファイルの中で近くにまとめるなら、標準的な圧縮プログラムはもっと多くを処理できるようになるでしょう。たとえば、Webログ内で<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)
|
DOMの代わりにSAXを使うことにより、この変換の時間の効率が著しく向上します。とはいえ、この開発において、時間は大きな考慮事項というわけではありません。変換を反転するには、リスト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.
という名前が含まれているので、見分けることが可能でしょう。(XMillについては、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がわたしの変換と同様の (それより悪い) 動作をすることは、わたしにとって慰めとなっています。
この技法は、Webログ・ファイルではかなりよい結果を示します。ここでは真価が発揮されています。
リスト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 Webログを再構造化すると、gzip圧縮にとって極めて有利です。とはいえ、gzipはわたしの好みの技法ではないため、ほどほどの興味があるに過ぎません。真に興味深いのは、ただでさえすばらしいbzip2の圧縮率を11%も改善できたということです。地球が壊滅するほどの重要性はないでしょうが、メガバイト単位のデータについて心配している場合、これは十分役に立ちます。価値のほどは不明ですが、この場合にXMillはxml2struct.pyよりいくらか優れた結果を示しました。この再構造化したXMLの圧縮と、元のテキストのWebログについて得られた最良の圧縮結果との差が7%以内であることも、興味深いことです。
結論
ここに示したユーティリティーは予備的な試みではありますが、この初期の形式でさえ、圧縮XMLファイルから最後の最後までバイトを削り取る点で、(少なくともいくつかの場合には) 驚くほど良い成果を挙げました。少しの調整と実験を重ねれば、もう何パーセントかの削減は可能と予想されます。このユーティリティーを書くのを困難にさせている原因のひとつは、とにかくbzip2があまりにも 良い働きをするということです。正直に言って、わたしは経験によるテストを開始したとき、Burrows-Wheelerアルゴリズムの効率に驚かされました。
商用ユーティリティーの中には、圧縮文書の特定のDTDに関する知識を活用してXMLを圧縮しようとするものもあります。こうした技法により、さらに圧縮できる可能性は極めて高いと言えます。しかし、xml2struct.pyとXMillには、XMLファイルに容易に適用できる単純なコマンド行ツールであるという優れた利点があります。それぞれの圧縮ごとにカスタム・プログラミングを行うのは、望ましいことでも可能なことでもありません。しかし、それが望ましい、または可能な場合、さらにバイトを削り取ることは達成可能な目標となるでしょう。
参考文献
- ibiblio.orgで、XML形式によるシェークスピアの全戯曲がダウンロード可能です。テストの目的で使用したhamlet.xmlはここで入手しました。
- M. BurrowsとD.J. Wheelerによる1994年の論文、"A Block-sorting Lossless Data Compression Algorithm" は、現在Burrows-Wheelerとして知られるアルゴリズムを紹介しました。この技法は、かなりポピュラーなbzip2ユーティリティーでインプリメントされています。
- 多くのUNIX型のシステムには、標準配布版の一部としてbzip2が含まれています。それ以外のプラットフォームをご使用の場合、あるいはより新しいバージョンが必要な場合は、Redhat にbzip2があります。
- わたしは、データ圧縮に関する一般的な入門として優れていると思えるものを執筆しました。
- これまでの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を比較検討し、開発者がどのような場合に、成熟しつつあるW3C XML Schemaに背を向けてDTDにこだわりたくなるのかを示しています。
-
XMLの論考 第8回では、コンピューター科学者たちによって概念化されたデータ・モデル という抽象的な理論が、特定の複数表現データ・フローを開発するために、どのように役立っているのかを説明しています。
-
XMLの論考 第9回では、RDBMSから独立したXML結果セットを生成できる、パブリック・ドメインのsql2dtdおよびsql2xmlユーティリティーについて説明しています。
-
XMLの論考 第10回 では、Davidの「魅力的なPython: Pythonによる全文検索システムの開発」というコラムで紹介された汎用全文検索システムを拡張して、XML特有の検索および索引付け機能を組み込みます。また、どのようにindexerがXMLの階層ノード構造を活用できるかを説明します。
-
XMLの論考 第11回 では、このシリーズの第1回で紹介したモジュールに再び立ち戻ります。
-
XMLの論考 第12回 では、SQLステートメントを生成するパブリック・ドメインのユーティリティーについて説明します。そのSQLステートメントを使えば、XML文書を開始するときに、一貫性のある、反転可能な方法でデータベースを作成して、それにデータを読み込むことができます。
著者について | 
| | David Mertz氏は多くの分野で活躍しています。ソフトウェア開発や、それについて著述もしています。その他、学術政策理念について分野を問わず、関係する雑誌に記事も書いています。かなり以前には、超限集合論、ロジック、モデル理論などを研究していました。その後、労働組合組織者として活動していました。そして、David Mertz氏自身は人生の半ばにもまだ達していないと思っているので、これから何かほかの仕事をするかもしれません。 |
記事の評価
| 
