レベル: 初級 David Mertz, Ph.D (mertz@gnosis.cx), Author, Gnosis Software, Inc.
2002年 4月 01日 この連載の以前の記事で、Davidは、圧縮率を改善するためにXML文書を可逆的に再構造化する技法について調べました。しかし、大規模なXML文書と組み込みプロセスの場合、圧縮パスに先立ってソース文書全体を再構造化するのは実用的でないことがあります。この記事でDavidは、再構造化の技法をブロック・レベルの処理にどのように適合させられるかについて、圧縮率の改善とCPU/メモリーの所要量の面から調べます。
XML文書は、他の形式のデータ表現と比べて、かなり大きくなる傾向があります。冗長であるとはいえ、XMLの簡潔さと汎用性は、XMLを価値あるものにしています。ほとんどの場合、XMLのサイズは問題になりません。ハード・ディスクは安価であり、通信時間は、処理に要する合計時間のわずかな部分を占めるに過ぎないからです。しかし、時には、帯域幅と記憶スペースが重要になることがあります。
もう少し具体的に言うと、表を中心としたデータをXML文書で表現すると、CSVまたはデータベースで表現する場合、あるいはフラット・ファイルで表現する場合と比べて3倍の大きさになることも珍しくありません。EDIデータ (たとえば、ebXMLプロジェクト) を表現する場合も、大きさは同様に増加します。そのようなコンテキストでは、多くの場合、数メガ・バイトのデータ・ソースから処理を始めるので、それがさらに何倍もの大きさになるとしたら、特に伝送のことを考えると、たいへん不便なことになります。
文書の圧縮について考えるときにまず思い出すのは、Lempel-Ziv、Huffman、Burrows-Wheelerなどの汎用圧縮アルゴリズムと、それらのアルゴリズムのバリエーションをインプリメントした汎用のユーティリティーでしょう。そのようなユーティリティーの例には、gzip、zip、bzip2 (および、それぞれのライブラリー・バージョン) があります。これらのユーティリティーはいずれも、XMLファイルのサイズを実質的に減少させます。特にbzip2は、圧縮率が優れています。しかし、圧縮のPPM技法を知っている人は少ないことでしょう。この技法では、一般に、bzip2よりもさらに高い圧縮率での圧縮が可能です。とはいえ、既に低速だと言われているbzip2よりもさらに長い処理時間を要するところが難点です。XML文書を圧縮する分野で君臨する「お山の大将」は、xmlppmです。xmlppmでは、この連載で紹介したのと同様のXML固有の技法を利用します。ただし、xmlppmは、ここで紹介するxml2structと比べて、桁違いに低速であり、無制限にメモリーを消費します。とはいえ、時間とメモリーに余裕があれば、xmlppmは驚異的な圧縮率を達成します。
XML文書の特定の構造を利用して、より圧縮性の高い 表現を作成すれば、相当高い圧縮率を達成できます。XMillユーティリティーは、この技法をインプリメントしたものです (その点でxmlppmと同様ですが、より洗練された仕方でインプリメントしています)。しかし、XMLの再構造化と汎用の圧縮アルゴリズムを組み合わせる従来の技法は、XML文書全体のレベルで処理するものでした。これは、XMill、xmlppm、そして私のオリジナルのxml2structユーティリティーに当てはまります。これらの技法すべての背後にある一般的な原則は、文書中の比較的同質の部分を見つけて、変換後のファイルではそれらの部分を互いに近い位置にグループ化する、というものです。そのようなグループ化を施すと、標準的な圧縮ユーティリティーによる圧縮がよくなります (圧縮率が上がり、わずかながら処理が高速にもなる)。とりわけ、XMLでは、特定の部分を同じ名前の要素タグで囲むことにより、それらの部分の類似性が高くなります。
数メガバイトのXML文書を処理しなければならないのであれば、そのような巨大な文書を操作するためにメモリー、ディスク・スペース、およびCPUのオーバーヘッドを消費するのは現実的でないことがしばしばです。数メガバイトのソース文書全体ではなく、解析されたブロックだけを逐次的に読み取り、同様の技法を適用できるとしたら、その方が優れています。このトピックに関するこの連載の以前の記事を思い出すと役立ちます。その記事によると、Burrows-Wheelerアルゴリズムを「汎用的に」適用した場合に、xml2structがXMLの知識を利用して実行するのとほとんど同じ再構造化が実行され、同様の圧縮結果が得られるとのことでした。Burrows-Wheelerアルゴリズムの効率は、大部分、大きな入力ソースに対してグローバルな分析を実行できるかどうかにかかっています。この後の定量的な分析で見るとおり、XML文書からの比較的小さな逐次ブロックを対象にした場合、Burrows-Wheelerの利点はすべて失われます。この制約のもとでは、再構造化パスの技法がかなりの程度まで有効です。
用途のシナリオ
この記事で取り上げるブロック・レベルの再構造化/圧縮の技法を実用的に応用する方法はたくさんあります。ごく単純なケースは、XMLファイルが比較的大きく (数百メガバイトまたは数ギガバイト)、メモリーとディスク・スペースがある程度限られており (数ギガバイトの余分なメモリーまたは記憶域を処理に利用できるわけではない)、チャネルのコストが比較的高価である (1ギガバイトの送信量を0.5ギガバイトに減らすことが有意義な節約である) ケースです。この単純なケースのシナリオでは、次のようなプロトコルを利用しているとします。
xmlstructの通信プロトコル
- マシンAは、マシンBへのチャネルと、大きなXMLソース (ファイル、またはXMLコンテンツを動的に生成するもの) へのチャネルを持っている。
- マシンA上のSAXパーサーは、ソースXMLから1ブロック分のデータを受け取るたびに、そのデータをフラッシュする。
- フラッシュされたデータは、再構造化される。
- フラッシュされたブロックは、gzipやbzip2などの従来の手段で圧縮される。
- 再構造化/圧縮されたブロックは、送信される。
- マシンBは、チャネルを介してブロックを受信する。基礎になるXMLが、逐次的に再構成される。XMLの各ブロックがファイルに追加される。あるいは、各ブロックがSAXパーサーに送られて要素と内容が処理され、処理が終わったら破棄される。
技法の概要
xml2structの再構造化の技法は、任意のブロック・サイズに適合させるための変更はほとんど必要ありません。この記事のアーカイブ・ファイルには、ブロック・レベルの再構造化の2つのインプリメンテーションが含まれています。Pythonインプリメンテーションは、「XMLの論考 第13回: 文書のエントロピーの調査」(参考文献を参照) で紹介したxml2struct.pyのパターンに密接に従っています。ただし、今回のコードの方がずっとコンパクトで、流れも追いやすくなっています。さらに、「最適化された」Cによるインプリメンテーションも、アルゴリズムの速度性能を調査するために開発しました。
元のアルゴリズムでは、タグのリストが、再構造化されたXML文書の最初の区切られたセクションとして組み込まれていました。このタグのリスト (実際の文書解析中に、その場その場で生成される) は、構造スキーマの中で使用される1バイトのタグ・プレースホルダーに対するインデックスとして使用されるものでした。タグの代わりに1バイトのインデックス値を使用するという戦略により、再構造化された文書のサイズがいくらか削減されますが、このアルゴリズムで処理できるDTDは、個別のタグ数が253個までに制限されます。
このあと説明するブロック・レベルの改訂版では、タグ・リストを独立して入手可能なものと想定します。DTDからタグ・リストを作成するユーティリティー関数は、この記事のアーカイブ・ファイルに含まれています。2つのチャネルの両方に必要なDTDがあれば、すべては適切に機能します。もしDTDがなくても、タグの順番を指定する任意の形式のデータがあれば、それで機能します。
必要な重要な改訂事項は、現在の要素のネストを示す新しい (最初の) 区切られた文書セクションを追加することだけです。元の文書レベルのフォーマットでは、すべての開始タグは終了タグとペアになっていました。しかし、ブロック・レベルのフォーマットでは、XML文書が自由な位置で分割されるため、ブロックの開始位置で未終了の要素のスタックを記録する必要があります。解析される最初のブロックでは、この最初のセクションに空のフィールドが入ります。それ以降のブロックでは、まだ終了していないタグ・インデックスを列挙した1バイト以上が入ります。
再構造化されたブロックのフォーマットはかなりシンプルで、次のとおりです。
- 未終了のタグのリスト。各開始タグは1バイト (バイト値は0x03以上)。このリストは、タグ・リスト・スタックと照合されて、対応する終了タグ・バイトとマッチングされます。
- セクション区切り文字: 0x00 (ヌル・バイト)
- ブロックの文書構造のコンパクトな表現。各開始タグは1バイトで表現され、内容の出現位置は0x02というバイトでマークされる。終了タグは0x01というバイトで表現され、対応する開始タグとマッチしなければならない。
- もう1つのセクション区切り文字: 0x00 (ヌル・バイト)
- 文書構造スキーマに示されているすべての要素の内容を、要素のタイプごとにグループ化したもの。個々の内容項目はそれぞれ0x02というバイトで区切られ、新しいタイプの要素が始まるごとにさらに0x01というバイトで区切られる (最後の仕様は、厳密には不要だが、これがあると逆の変換が容易になる)。
デモンストレーション・コードには2つの制限事項があるので、注意してください。最初の点は、純粋に、調査用のインプリメンテーションであるための便宜上の制限です。現在のパーサーでは、要素の属性は処理されません。これは、主として、提示したコードの流れを追いやすくするためです。属性を表すブロックを追加することは、現在の技法を拡張すれば簡単に実現することができ、その機能を組み込んでも圧縮率とパフォーマンスに目立った影響は出ないものと思われます。
第二の制限事項は、もっと重大です。ブロックがフラッシュされるのは、終了タグに出会ったときだけです。1つの要素のPCDATA内容が、使用されているブロック・サイズより小さくないことがあっても、一定のブロック・サイズが強制されることはありません。たとえば、1つの大きな<pre> 要素を含む、巨大なXHTML文書を処理する場合でも、ほどよい大きさのブロック・サイズが強制されることはありません。必要なら、この制限を変更することも可能です (しかし、SAXフレームワーク内で使うには美しくない方法を使うしかないでしょう)。しかし、この制限事項を取り去っても、あまり意味がありません。というのは、要素内容がブロック・サイズより大きいような文書では、再編成は取るに足りないものだからです (したがって、一般には、この制限を変更するべきではありません)。問題が起こり得る1つの状況は、インプリメントしているシステムの使用可能メモリーにハードウェア上の限界があり、ブロックが大きすぎて処理できないというケースです。
通常のケースでは、入力XMLブロックは、示されているブロック・サイズより少しだけ大きいものですが、タグを1バイトのタグ・プレースホルダーで置き換えた後は、そのブロック・サイズよりも少しだけ小さくなるのが普通です。そのブロックに対して圧縮を適用した後は、圧縮されたブロックのサイズは、入力ブロックのサイズより大幅に小さくなります。
圧縮の定量的な評価
定量的に評価する目的で、以前の調査で取り上げたのと同じ2つの代表的なXML文書を処理しました。1つは、散文中心の文書で、シェークスピアのハムレット のXML版です。もう1つのXMLソース文書は、1 MBのApacheログ・ファイルから作成したもので、ログ・ファイルの各フィールド (および各エントリー) をXMLタグで囲みました。使用したタグは特別に冗長なものではありませんでしたが、ファイルは約3 MBにまで増大しました。
この後のグラフで、前面にある2つのグレーのバーは、gzipとbzip2を使用した単純なファイル・レベルの圧縮で達成できる圧縮を表しています。前述のとおり、大きいファイルをファイル・レベルで圧縮するのは非実用的です。しかし、ファイル・レベルの圧縮は、予想通り、より良い結果を達成しています。反復されているストリングをファイル全体から検索するからです。一般に、ブロック・レベルの圧縮で、ファイル・レベルの圧縮にほぼ匹敵する結果を出すには、100 KBかそれ以上のブロック・サイズが必要です。それでも、ギガバイト単位のソース文書を取り扱う必要がある場合には、1メガバイトのブロック・サイズでさえ、元のソース文書に比べればずっと扱いやすく見えることでしょう。
グラフの後ろ側の緑色と青色のバーは、再構造化パスなしでブロックを圧縮した場合に達成できる圧縮を表しています。
最後に、中央の赤色のバーは、xml2struct.pyをzlibライブラリー圧縮と組み合わせた場合の圧縮性能を表しています。もしbzip2ライブラリーを使用したとすれば、もっと良い圧縮結果が得られたはずです。しかし、それはテストしませんでした。bzip2は、速度面での欠点ゆえに、予想される将来の使用からは除外されるに違いないからです。とはいえ、CPU時間よりも帯域幅の方が重要な場合には、bzip2圧縮の層を追加すれば、圧縮率を向上させることができます。
それでは、結果を見ていきましょう。その後で、私のコメントを記載します。ブロック・サイズは、1 KB、10 KB、100 KB、そして1 MBを調べました。最初にハムレット のファイルを調べ、次にWebログ・ファイルを調べました。
図1：各種の技法によるhamlet.xmlの圧縮
図2：各種の技法によるweblog.xmlの圧縮
hamlet.xmlとweblog.xmlでは、全体として同じ傾向が見られますが、その傾向はweblog.xmlのほうがいっそう 強く表れています。ログ・ファイルが反復の多い構造になっていることが、再構造化に対して最も有利に作用しています。小さいブロック・サイズでは、ファイル・レベルの圧縮よりずっと悪い結果になります。10 KBのブロック・サイズあたりから、圧縮の結果が少しずつ良くなり始め、100 KBのブロック・サイズでは、ファイル・レベルの圧縮技法に非常に近い結果になっています。
この記事のグラフで最も興味深い点は、ブロック・レベルの再構造化技法の圧縮特性です。再構造化は、単純なブロック・レベルzlibの圧縮結果よりも、常に良い結果を出しています (weblogでは約30%の改善、ハムレット ではそれよりも低い改善率)。約100 KBのブロック・サイズでは、再構造化の圧縮結果がファイル・レベルのgzipよりも良くなっており、これはたいへん肯定的な結果です。
意外な結果は、ブロック・レベルのbzip2圧縮の振る舞いです。ブロック・サイズが大きくなると、予想通り、ブロック・レベルの圧縮を使用するかどうかで違いがなくなります。しかし、まったく違いをなくすには、ブロック・サイズを1 MBまで大きくする必要があります。とはいえ、小さいブロック・サイズでは (特に1 KBの場合。しかし、10 KBの場合にも)、ブロック・レベルbzip2の結果は驚くほど悪いものです。圧縮の前に再構造化をしたとしても、この結果が大幅に改善されるとは思われません。実際、1 KBのブロック・サイズでは、bzip2はzlibより常にずっと悪い結果になっています。
CPU使用量と変換速度の定量的な評価
xml2structの最適化Cインプリメンテーションを使って、再構造化と圧縮の実行速度を調査しました。これらの手順をチャネルの中間段階として使用した場合、そのプロセスが出力チャネルを飽和させられるかどうかが非常に重要です。ここで紹介する時間は、Linuxのtimeユーティリティーを使って収集しました。各実行の経過時間を報告しています。各実行は、100%近くのCPU使用率を示し、大部分はユーザー時間でした。意外なことに、調査した変換のどれについても、ブロック・サイズによる実行時間の差はごくわずかでした。
図3：変換に要した時間 (グラフ)
図4：変換に要した時間 (表)
実行時間の全体的な傾向は、かなり明白です。Cインプリメンテーションによる再構造化はかなり高速で、gzipはさらに高速です。bzip2は低速です。ちなみに、PPMはbzip2よりさらに10倍以上低速です。Pythonインプリメンテーションの実行時間は、ベースラインとしてここに含めました。このバージョンは、まったく最適化していません。最適化すればもう少し速くなるはずですが、2倍以上高速になることはないと思われます。一般に、Pythonインプリメンテーションとbzip2のパスは、ほとんどのチャネルを飽和させるには、どちらも低速すぎます。
これらの実行時間は、出力チャネルの飽和とどのような関係になるでしょうか。3 MBのファイルを、PIII-733で1秒より若干短い時間で再構造化できます。ブロック・サイズが再構造化の速度に与える違いは、小さなものです。再構造化したファイルをgzip/'zlib' で圧縮すると、さらに4分の1秒の処理時間が加わります。これは、合計で約20メガビット/秒ということになります。言い換えると、xml2struct + gzipを実行するPIII-733が、2本の10メガビット・イーサネット・チャネル、または13本のT1回線を飽和させることができるということです。xml2structの処理を専門に実行した場合、T1回線を充足させるのに低速のPentiumで十分であり、XML文書を効率的に送信する作業を十分に実行できます。逆に、ギガヘルツを超えるクロック速度で稼動するIntel P4またはAMD Athlonを使用すれば、45メガビットのT3回線の要件を満たせるはずです。
結論
文書の構造は、標準的な圧縮アルゴリズムによる圧縮性に有意な影響を与えます。XMLでは、そのセマンティック構造の詳細の大半を、その構文形式でエンコードするため、XML文書を再構造化 すると、その圧縮性を改善できます。また、その再構造化の技法が、大規模なXML文書の解析されたブロックを使用する逐次化に順応させやすいことを、この記事で示しました。さらに、xml2structアルゴリズムを最適化Cでインプリメントしたときのパフォーマンス特性は、現行世代のCPUと現在の一般的なチャネル帯域幅を使用するXMLサーバーから専用の出力チャネルを飽和させることのできるものです。
参考文献
著者について  | 
| | David Mertz氏は多くの分野で活躍しています。ソフトウェア開発や、それについて著述もしています。その他、学術政策理念について分野を問わず、関係する雑誌に記事も書いています。かなり以前には、超限集合論、ロジック、モデル理論などを研究していました。その後、労働組合組織者として活動していました。そして、David Mertz氏自身は人生の半ばにもまだ達していないと思っているので、これから何かほかの仕事をするかもしれません。 |
記事の評価
| 
