最先端の XML 圧縮手法の調査

XML を認識する (または認識しない) データ・コンプレッサー、そして問い合わせ処理が可能 (または不可能) なデータ・コンプレッサーについて検討する

XML は、World Wide Web でデータを表現し、交換するための標準と見なされています。優れた柔軟性を持つ XML は幅広く受け入れられていますが、XML 文書のサイズが大きいという難点があります。サイズが大きいということは、送信、処理、保管、問い合わせ処理の対象となる情報の量が他のデータ形式よりも多くなりがちであることを意味します。この問題に対処するための XML 圧縮手法には、いくつかの選択肢があります。そこで、この記事では最新の XML 圧縮手法について概説します。

Sherif Sakr (ssakr@cse.unsw.edu.au), Research Scientist, National ICT Australia

Dr. Sherif Sakr は、オーストラリア・シドニー所在の NICTA (National ICT Australia) のソフトウェア・システム・グループに所属する研究専門の科学者です。また、ニューサウス・ウェールズ大学 (UNSW) の The School of Computer Science and Engineering (CSE) で共同講師も勤めています。2007 年にドイツのコンスタンツ大学でコンピューター・サイエンスの博士号を取得しました。エジプトのカイロ大学のコンピューターおよび情報学部の情報システム学科で、2000年にコンピューター・サイエンスの理学士号を、2003年に修士号を取得しました。2011年には、米国ワシントン州レドモンドにある Microsoft Research の eXtreme Computing Group (XCG) で客員研究科学者として迎えられました。



2011年 8月 26日

はじめに

よく使われる頭文字語

  • CDATA: Character DATA
  • DTD: Document Type Definition
  • GPS: Global Positioning System
  • HTML: HyperText Markup Language
  • PPM: Prediction by Partial Match
  • SAX: Simple API for XML
  • W3C: World Wide Web Consortium
  • XML: Extensible Markup Language

XML は、HTML および World Wide Web の急速な普及の結果として登場した、最も有用かつ重要な技術の 1 つです。さまざまなアーキテクチャーにとって中立的なデータ表現を提供し、最小限の作業でソフトウェア・システム間の隔たりを埋め、そして大量の半構造化データを保管する XML は、さまざまな問題を解決します。

XML は文書内のレコードごとにスキーマが繰り返されるように設計されているため、自己記述的なデータと呼ばれることがよくあります。自己記述的であるという特徴は、XML に極めて高い柔軟性を与えている一方、XML 文書を冗長にし、それによって文書が膨大なサイズになってしまうという問題をもたらします。XML の使用が増え続けていること、そして XML 文書の大規模なリポジトリーが普及していることから、効率的な XML 圧縮ツールへの需要が高まっています。

図 1 に示すように、XML データをネットワーク上に送信する際に XML コンプレッサーを使用すると、圧縮された XML が送信されるため、XML コンプレッサーを使用しない場合に比べ、さまざまなコストが削減されるというメリットがあります。サイズが大きな XML 文書に対処するため、XML を認識するいくつかのコンプレッサーは、XML 文書の既知の構造を利用することにより、一般的なテキスト・コンプレッサーよりも高い圧縮率を達成しています。XML 圧縮ツールによってもたらされるメリットには、データ交換に必要なネットワーク帯域幅が削減されること、保管に必要なディスク・スペースが削減されること、XML 文書に対する処理や問い合わせ処理をするためのメイン・メモリー要件が最小化されることなど、さまざまなものがあります。

図 1. XML データをネットワーク上に送信する場合に XML コンプレッサーを使用することによるメリット
XML データをネットワーク上に送信する場合に XML コンプレッサーを使用することによるメリットを示す図

原則として、XML コンプレッサーは 2 つの主な特性を基準に分類することができます。図 2 に示すのは、そのうちの 1 つ、XML 文書の構造を認識するかどうかという特性に基づく分類です。この分類によれば、コンプレッサーは 2 つのグループに大別されます。

  • 一般的なテキスト・コンプレッサー: XML データはテキスト・ファイルとして保管されることから、XML 文書を圧縮するための当然の手法として最初に考えられたのは、従来の汎用テキスト圧縮ツール (gzip や bzip2 など) を使用することでした。このグループの XML コンプレッサーは XML を認識しません。つまり、XML 文書を通常のプレーン・テキスト文書として扱い、従来のテキスト圧縮手法を適用します。
  • XML を認識するコンプレッサー: このグループのコンプレッサーは、一般的なテキスト・コンプレッサーよりも高い圧縮率を達成するために、XML 文書の構造を認識するように設計されています。これらのコンプレッサーは、XML 文書のスキーマ情報の可用性に依存するかどうかに基づいて、さらに以下のサブグループに分けることができます。
    • スキーマに依存するコンプレッサー: 圧縮プロセスを実現するためには、エンコーダーとデコーダーの両方が文書のスキーマ情報を使用する必要があります。この分類にあてはまるコンプレッサーとしては、rngzip が挙げられます。
    • スキーマに依存しないコンプレッサー: 符号化プロセスおよび復号化プロセスでスキーマ情報を使用しません。この分類にあてはまるコンプレッサーとしては、XMill や SCMPPM が挙げられます。
図 2. XML 文書の構造を認識するかどうかによる XML コンプレッサーの分類
XML 文書の構造を認識するかどうかによる XML コンプレッサーの分類を示す図

図 3 に、2 番目の XML コンプレッサーの分類を示します。この分類で基準となっているのは、問い合わせ処理をサポートできるかどうかです。

  • 問い合わせ処理が不可能な (アーカイブ) XML コンプレッサー: このグループの XML コンプレッサーは、圧縮された XML 文書に対する問い合わせ処理をすることができません。この分類にあてはまるコンプレッサーとしては、gzip、bzip2、XMill などが挙げられます。このグループで主な焦点としているのは、できるだけ高い圧縮率を達成することです。デフォルトでは、汎用テキスト・コンプレッサーは問い合わせ処理が不可能なコンプレッサー・グループに属します。
  • 問い合わせ処理が可能な XML コンプレッサー: このグループの XML コンプレッサーは、圧縮された XML 文書に対する問い合わせ処理をすることができます。これらのコンプレッサーの圧縮率は、一般にアーカイブ XML コンプレッサーの圧縮率よりも劣りますが、このグループの主な焦点は、問い合わせ処理をする際に文書の完全な圧縮解除を回避することにあります。実際、圧縮された XML に直接問い合わせ処理をできるということは、リソースの限られたコンピューター機器 (モバイル機器や GPS システムなど) でホストされる多くのアプリケーションにとって重要な機能です。デフォルトでは、問い合わせ処理が可能なすべてのコンプレッサーは、XML を認識するコンプレッサーでもあります。このグループのコンプレッサーは、XML 文書の構造部分とデータ部分をどのように符号化するかによって、さらに以下のサブグループに分けることができます。
    • 同型コンプレッサー: XML 文書の元の構造が維持されるため、圧縮後の XML 文書には、圧縮前の XML 文書に対するのと同じようにアクセスして、構文解析することができます。この分類にあてはまるコンプレッサーとしては、XGrind が挙げられます。
    • 非同型コンプレッサー: XML 文書の符号化プロセスで、構造部分をデータ部分から切り離します。したがって、圧縮後の XML 文書の構造は、元の XML 文書の構造とは異なります。この分類にあてはまるコンプレッサーとしては、XQueC が挙げられます。
図 3. 問い合わせ処理をサポートするかどうかによる XML コンプレッサーの分類
問い合わせ処理をサポートするかどうかによる XML コンプレッサーの分類を示す図

一般的なテキスト・コンプレッサー

XML は、ツリー構造のデータを対象としたテキスト表現です。XML 文書を圧縮する至極当然の直接的な手法は、従来の汎用テキスト圧縮ツールを使用することです。過去数十年にわたって考案された数々のアルゴリズムは、テキスト・データを効率的に圧縮します。このグループで最もよく使用されている効率的なコンプレッサーとしては、gzip、bzip2、および PPM が挙げられます。

gzip コンプレッサーのベースとなっているのは、LZ77 アルゴリズムとハフマン符号化を組み合わせた DEFLATE 可逆データ圧縮アルゴリズムです。LZ77 アルゴリズムではデータを圧縮するために、データの一部分と一致するデータが、エンコーダーとデコーダーの両方に既に渡されているデータのなかに見つかる場合、その一部分を一致するデータへの参照に置き換えます。ハフマン符号化では、出現頻度が高い文字にはそれぞれのシンボルを表すために短いビット列が使用され、出現頻度が低い文字には長いビット列が使用されるという特有の手法を使って符号化が行われます。

bzip2 コンプレッサーは、Burrows-Wheeler 変換を使用して、頻繁に出現する文字のシーケンスを同一文字からなる文字列に変換します。その上で Move-To-Front 変換を適用し、最後にホフマン符号化を適用します。Burrows-Wheeler 変換では、元の文字列に頻繁に出現するサブ文字列がいくつもある場合には、文字の順序を入れ換えて同じ 1 つの文字が連続する箇所がいくつもあるような文字列へと変換を行います。この手法が圧縮に役立つ理由は、同じ文字が連続する文字列は圧縮しやすいためです。実際のところ、bzip2 でファイルを圧縮すると、gzip で圧縮する場合よりも高い圧縮率を達成できます。その一方、パフォーマンスは低下します。

PPM は、文脈モデルと予測に基づく、統計型の適応型データ圧縮手法です。この手法では、次数が固定された複数の文脈モデルを組み合わせた統計型の有限文脈モデル手法を使用して、入力シーケンスで次に出現する文字を予測します。モデルでの文脈ごとの予測確率は、適応的に更新される出現回数から算出されます。実際に出現するシンボルは、そのシンボルに予測される分布に応じ、算術符号を用いて符号化されます。PPM は単純で、これまで紹介したコンプレッサーのなかで最も効率的ですが、計算という点では最もコストがかかります。

実際には、一般的なテキスト・コンプレッサーはアーカイブ目的、あるいはデータ交換プロセスでのネットワーク帯域幅を削減する目的で使用されています。概して、これらのコンプレッサーの間には 2 つの主要な測定基準に関するトレードオフがあります。それは、圧縮率と圧縮時間/圧縮解除時間です。圧縮率の基準で言うと、PPM 圧縮は最大の圧縮率を達成する一方、gzip の圧縮率は最も劣っています。しかし、圧縮時間/圧縮解除時間に関しては、gzip のパフォーマンスが最も優れていて、PPM ではかなりの時間がかかります。この両方の測定基準において中間に位置するのは、bzip2 です。したがってどのコンプレッサーを選ぶかは、主にユーザーのシナリオでのこの 2 つの測定基準に関する要件に大きく左右されます。


問い合わせ処理が不可能な (アーカイブ) XML コンプレッサー

このグループの XML コンプレッサーは、圧縮された XML 文書に対する問い合わせ処理をすることができません。このグループで主な焦点としているのは、できるだけ高い圧縮率を達成することだからです。このセクションでは、このグループの以下の主要なクラスをそれぞれ代表するコンプレッサーについて説明します。

  • スキーマに依存しないコンプレッサー
  • スキーマに依存するコンプレッサー

スキーマに依存しない圧縮方式

このクラスの圧縮方式では、符号化プロセスおよび復号化プロセスでスキーマ情報を使用しません。XML を認識するコンプレッサーの最初の実装は、XMill です。XMill は、XML 文書の構造とデータを分離し、ツリー内での相対パスとデータ型に応じて、データの値を同種のコンテナーにグループ化するという斬新なアイデアを採り入れました。

XMill では、ソース XML 文書の構造部分とデータ値の部分の両方が収集されて、別々に圧縮されます。構造部分の場合、XML タグと属性が辞書方式で符号化されてから、バックエンドの一般的なテキスト圧縮方式でのプロセスに渡されます。XMill の構造に関する符号化方式では、個々の要素名と属性名のそれぞれに、要素名の辞書と属性名の辞書へのキーの役割を果たす整数コードが割り当てられます。データ部分に関しては、データ値がそれぞれのパスとデータ型に応じて、意味的に関連する同種のコンテナーにグループ化されます。その後、各コンテナーは、それぞれのコンテナーのデータ型に最適となるように特化したコンプレッサーを使用して個々に圧縮されます。このグループ化の処理は反復を局所化するのに役立つため、圧縮率がさらに高まります。

最新バージョンの XMill ソース・ディストリビューションでは、圧縮された XML 文書の中間バイナリーをバックエンドの 3 つの汎用コンプレッサー、gzip、bzip2、PPM のいずれかに渡せるようになっています。図 4 に、XML パーサー、構造およびデータ・コンテナー、1 つ以上の圧縮方式、および圧縮 XML ファイル (圧縮された構造と圧縮データが含まれます) を使用した XMill コンプレッサーのアーキテクチャー全体の概要を示します。

図 4. XMill コンプレッサーのアーキテクチャー全体
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 ファイルを構造コンテナーとデータ・コンテナーに分割する例
XML ファイルを構造コンテナーとデータ・コンテナーに分割する例を示す図

図 6 に、XMill コンプレッサーのコマンドライン・オプションを示します。

図 6. XMill コンプレッサーのコマンドライン・オプション
XMill コンプレッサーのコマンドライン・オプションを示すスクリーン・キャプチャー

図 7 に、XML 文書 (tpc.xml、サイズ 282 KB) を XMill コンプレッサーで圧縮した場合の成果を示します。出力された圧縮ファイル (tpc.xmi、サイズ 41 KB) のサイズは、圧縮前のサイズの 15 パーセントに相当します。

図 7. XMill コンプレッサーを使用した XML ファイルの圧縮結果
XMill コンプレッサーを使用した XML ファイルの圧縮結果を示すスクリーン・キャプチャー

XMLPPM は、MHM という多重化した階層型 PPM モデルを利用したストリーミング方式の XML コンプレッサーです。XMLPPM は汎用 PPM (Prediction by Partial Matching) 圧縮方式の適応型と見なされます。XMLPPM は、最初に XML ファイルを SAX パーサーで構文解析して一連の SAX イベントを生成し、これらのイベントのそれぞれを ESAX (Encoded SAX) と呼ばれるバイト・コード表現で符号化します。そして、複数の多重化 PPM モデルのなかから、ESAX バイト・コードの構文上の構造 (要素、文字、属性、および各種のシンボル) に応じたモデルを使って、ESAX バイト・コードを符号化するという方法です。XMLPPM コンプレッサーのバリエーションとしては、SCMPPM コンプレッサーが提案されています。SCMPPM は SCM (Structure Context Modeling) と呼ばれる手法を PPM 圧縮方式と組み合わせ、要素シンボルごとに個別のモデルを使用してテキストのコンテンツを圧縮するため、XMLPPM よりも多くの PPM モデルを使用します。

XMill と XMLPPM の圧縮率および圧縮/圧縮解除時間を大きく左右するのは、そのバックエンドである汎用コンプレッサー (gzip、bzip2、または PPM) です。したがって、これらのコンプレッサーには汎用のバックエンド・コンプレッサーと同じトレードオフが伴います。

スキーマに依存する圧縮方式

このクラスのコンプレッサーは、符号化プロセスおよび復号化プロセスに XML 文書のスキーマ情報を必要とします。例えば、XAUST XML コンプレッサーは、DTD のスキーマ情報を DTD に含まれる要素ごとに 1 つの決定性有限オートマトン (DFA) に変換し、その上で、各遷移に要素のラベルを付けます。遷移に関連付けられたアクションは、その遷移のラベルとなっている要素に対して DFA のシミュレーターを呼び出すことです。XAUST は同じ要素のデータをまとめて 1 つのコンテナーにグループ化し、算術的な次数が 4 次の (order-4) コンプレッサーを対象とした単一モデルを用いて、そのコンテナーをインクリメンタルに圧縮します。DTD スキーマ情報を使用することで、XAUST は文書の構造を追跡することも、期待されるシンボルの出現予測を正確に立てることも可能になります。予測されるシンボルが他の場所で出現しなければ、そのシンボルを符号化する必要はありません。というのも、デコーダーは同じモデルを DTD から生成することから、その唯一の期待されるシンボルを生成することができるためです。

RNGzip XML ツールは、特定の Relax NG スキーマに従った XML 文書を圧縮します。RNGzip では、送信側と受信側が、まったく同じスキーマを使うことを事前に合意しておく必要があります。その意味で、スキーマは暗号化と暗号解読の共有鍵と同じような役割を果たします。RNGzip は Relax NG スキーマ・バリデーターを使用して、指定されたスキーマから決定木オートマトンを作成します。XML 文書が提供されると、その XML がオートマトンで受け入れられるかどうかをチェックします。このオートマトンを前提に、受信側は極めて少量の情報を送信することによって、XML 文書全体を組み立てなおすことができます。オートマトンに分岐点がある場合には、RNGzip は単にどの遷移が取られたかを送信し、そのテキスト遷移を検出した場合には、一致するテキストを送信します。

理論的には、スキーマに依存するコンプレッサーは、スキーマに依存しないコンプレッサーよりも多少高い圧縮率を達成する可能性があります。けれども XML 文書のスキーマ情報は常に使用できるとは限らないため、スキーマに依存するコンプレッサーは優先して選択されることはなく、通常は使用されません。このため半構造化データを表現できる XML の柔軟性のメリットが失われてしまいます。このタイプのコンプレッサーが効果を発揮するのは、事前にスキーマが定義された XML 文書を圧縮する場合だけです。


問い合わせ処理が可能な XML コンプレッサー

問い合わせ処理が可能な XML コンプレッサーの主な焦点は、XML 文書全体を圧縮解除せずに、圧縮された XML 文書に対して直接問い合わせ処理を評価できることにあります。このグループに属するコンプレッサーの圧縮率は、一般にアーカイブ XML コンプレッサーの圧縮率よりも劣りますが、モバイル機器や GPS システムなどといったリソースの限られたコンピューター機器でホストされる多くのアプリケーションにとっては、このタイプのコンプレッサーが非常に重要です。このセクションでは、このグループの以下の 2 つの主要なクラスを代表するコンプレッサーについて説明します。

  • 同型コンプレッサー
  • 非同型コンプレッサー

問い合わせ処理が可能な同型 XML コンプレッサー

このクラスのコンプレッサーは、圧縮後の XML 文書でも、元の XML 文書の構造が維持されるため、圧縮された XML 文書に圧縮前の XML 文書と同じようにアクセスして構文解析することができます。圧縮された XML 文書を完全に圧縮解除することなく問い合わせ処理をすることができ、しかも XML を認識する最初の圧縮方式として登場したのは XGrind です。XGrind はデータを構造から切り離すことなく、XML 文書の元の構造を維持します。

XGrind によって圧縮された XML 文書が持つ同型の性質は、XGrind に多くの興味深い特性をもたらしています。

  • 圧縮後の XML 文書は、圧縮前の XML 文書のタグと要素/属性値をそれぞれに対応する符号で置き換えたものと見なすことができます。したがって、XGrind は拡張 SAX パーサーであると考えられます。
  • 通常の XML 文書に対して索引付けを行うのと同じような方法で、圧縮された XML 文書に対しても索引付けをすることができます。XGrind では、要素名と属性名は辞書ベースの符号化方式で符号化され、文字データは準適応型ハフマン符号化によって圧縮されます。XGrind のクエリー・プロセッサーが圧縮された値に対して処理できるのは、完全一致とプレフィックス一致のクエリーだけですが、圧縮解除された値に対しては、部分一致クエリーと範囲クエリーを処理することができます。ただし、圧縮されたドメインでの非等価選択など、XGrind ではサポートされていない処理もあります。したがって、XGrind は結合、集約、ネストされたクエリー、作成などの処理を実行することができません。

XPress も問い合わせ処理が可能な同型 XML コンプレッサーの 1 つです。XPress は、XML データを効率的に圧縮し、効率的に取得するという 2 つの特徴を併せ持っています。XPress は XML 文書のラベルおよびパスを符号化するために、個々に異なる間隔で逆算術符号化方式を使用します。そして、これらの間隔同士の包含関係を使用して、圧縮された XML データに対してパス式を評価します。XPress の圧縮方式は、入力ファイルを事前にスキャンして統計情報を収集するという準適応型であり、データに適用する符号化規則はデータの場所には依存しません。また、自動的に推測されたデータ型情報に基づき、データの値に適切なエンコーダーを適用します。

問い合わせ処理が可能な非同型 XML コンプレッサー

このクラスのコンプレッサーは、XML 文書の符号化プロセス中に構造部分をデータ部分から切り離します。同型コンプレッサーとは異なり、圧縮された XML 文書の構造は元の XML 文書の構造と異なってくるため、圧縮解除プロセスでは別の方法で文書を構文解析する必要があります。ただし、圧縮率は同型コンプレッサーよりも勝っています。例えば、文法ベースで問い合わせ処理が可能な XML 圧縮方式、XSeq は、有名な文法ベースのテキスト・ストリング圧縮アルゴリズム、Sequitur の適応型と考えられています。

XSeq では、入力 XML ファイルのトークンが一連のコンテナーに分けられて、これらのコンテナーのそれぞれが Sequitur を用いて圧縮されます。Sequitur 圧縮アルゴリズムは、特定のストリング入力に対して文脈自由文法を形成する線形時間オンライン・アルゴリズムです。定義された文脈自由文法を使用することにより、XSeq は関係のない圧縮データを順次スキャンすることなく、特定のクエリーで突き合わせられるデータ値だけを処理します。さらに、文脈自由文法は、XSeq が文書を完全に、あるいは部分的にも圧縮解除することなく、圧縮されたファイルに対して直接クエリーを処理することを可能にします。さまざまなコンテナーに保管されたデータ値を相関させて、クエリーの評価時間を短縮するために、XSeq は一連の索引を使用します。これらの索引は圧縮ファイル内に保管されており、ルール・コンテンツを処理する前にメモリーにロードされます。例えば、XSeq は構造に関する索引を使用して、コンテナーに保管されたデータ値を圧縮解除することなく素早く見つける一方、ヘッダー索引に、ファイル内の各コンテナーの入り口を指すポインターのリストを含めます。

TREECHOP XML コンプレッサーも同じく問い合わせ処理が可能な XML コンプレッサーです。TREECHOP の圧縮プロセスではまず、XML 文書に対して SAX ベースの構文解析を行い、構文解析されたトークンを深さ優先順で圧縮ストリームに書き込みます。各ノードのコード名には、プレフィックスとしてその親のコード名が追加されるため、XML 文書ツリー内の 2 つのノードが同じパスを持つ場合には、これらのノードは同じコード名を共有することになります。CDATA セクション、コメント、処理命令、およびリーフではないノードのそれぞれには、バイナリー・コード名が割り当てられます。このコード名は、ツリー・ノードのパスを基準に一意に割り当てられます。ツリー・ノードの符号は深さ優先順で圧縮ストリームに書き込まれるので、デコンプレッサーは適応型符号化情報を使用して、元の XML 文書をインクリメンタルに再生成していくことができます。TREECHOP では、圧縮ストリームを 1 回スキャンすることによって、完全一致クエリーおよび範囲クエリーを実行することができます。

XQuec システムは、XML 文書内の構造とコンテンツの分離に基づき、圧縮された XML 文書にフラグメント化とストレージ・モデルを適用します。さらに、コンテナーをグループ化する方法を適切に選択することによって、同じグループに属するコンテナーがクエリー述部にも一緒に現れるようにします。また、圧縮ドメイン内で述部の評価を行うために、該当する述部に関係するすべてのコンテナーが同じグループに属すること、そして圧縮ドメインではその述部をサポートするアルゴリズムによってコンテナーが圧縮されることを確実にします。述部に関する情報は、使用可能なクエリーのワークロードを使用して推測されます。XQueC は、クエリーのワークロード情報を利用して、コンテナーをソース・モデルに応じたセットに区分化し、各セットに最も適した圧縮アルゴリズムを適切に割り当てます。XQueC では XML クエリーを評価するための代数も設計しています。この代数は、通常の演算子と圧縮対応の演算子を自由に混在させることができる、コスト・ベースのオプティマイザーが利用します。


まとめ

この記事では、最先端の XML 圧縮手法を概説しました。XML 圧縮メカニズムにおける主要な技術革新が提示されたのは、この分野で最初に実装された XMill です。XMill は、XML 文書の構造部分をデータ部分から切り離し、関連するデータ項目を別々に圧縮可能な同種のコンテナーにグループ化するという構想を導入しました。構造部分とデータ部分を分離することで、重複するデータを見つけやすくなるため、同種のコンテナーにグループ化した後のステップ (つまり、これらの同種のコンテナーを汎用コンプレッサーやその他の圧縮メカニズムによって圧縮するステップ) は改善されます。

XMill 以外の XML コンプレッサーのほとんどは、XMill のこの構想をさまざまな方法で模倣しました。さまざまな XML 圧縮手法の違いを区別する上では、圧縮時間と圧縮解除時間という測定基準が重要な役割を果たします。基本的に、スキーマに依存する XML コンプレッサーは優先されないか、実用では使用されていないのが通常です。それは、XML 文書のスキーマ情報がいつでも使用できるとは限らず、要求する形式 (DTD、XML Schema、RElaxNG) になっているわけでもないからです。問い合わせ処理が可能な XML コンプレッサーは多くのアプリケーションにとって非常に重要ですが、文法ベースの XML 圧縮手法と問い合わせ処理が可能な XML コンプレッサーの信頼できる実装は公開されていません。この 2 つの領域には、さらに研究開発を進める上で興味深いさまざまな可能性があります。

参考文献

学ぶために

  • XML 1.0 仕様 (W3C): XML 機能の具体的詳細に関する情報源にアクセスしてください。
  • XML FAQ (Peter Flynn 編集): XML に関するよくある質問の答えを見つけるには、このサイトも絶好の XML の情報源となります。
  • W3schools.com による XML DOM Tutorial: XML 文書にアクセスして操作する標準手段、DOM について詳しく調べてください。このチュートリアルでは、ブラウザーで使用可能な XML ベースのインターフェース (そして各インターフェースをサポートしているブラウザー) を紹介しています。
  • Understanding 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年): 部分的ストリング一致が高次マルコフ・モデル間の競合、そしてこれらのモデルを素早く形成する必要を解決する仕組みを調べてください。
  • Merging prediction by partial matching with structural contexts model」(Joaquin Adiego、Pablo de la Fuente、Gonzalo Navarro 他による共著、米国ワシントン DC での Data Compression Conference 議事録 (DCC)、2004年): 圧縮された構造化文書のテキスト構造を検討し、基本的な SCM 手法の圧縮率を改善する方法を学んでください。
  • Compressing XML documents using recursive finite state automata」(Hariharan Subramanian、Priti Shankar 共著、フランス・ソフィア・アンティポリスでの第 10 回国際 CIAA (Conference on Implementation and Application of Automata 議事録、2005年): DTD 仕様から自動的に XML 文書のコンプレッサーを生成する方法について読んでください。
  • XGRIND: A query-friendly XML compressor」(Pankaj M. Tolani、Jayant R. Haritsa 共著、米国ワシントン DC での第 18 回 ICDE (International Conference on Data Engineering) の議事録、2002年): 標準 XML 手法のクエリーおよび再利用をサポートする圧縮ツールの詳細を学んでください。
  • TREECHOP: A tree-based query-able compressor for XML, Technical report」(Gregory Leighton、Tomasz Muldner、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、Jun Yang 共著、米国ニューヨークでの ACM SAC (Symposium on Applied Computing) 議事録、2005年): Sequitur 圧縮アルゴリズムをベースとした XML 圧縮方式について読んでください。
  • XPRESS: A queriable compression for XML data」(Jun-Ki Min、Myung-Jae Park、Chin-Wan Chung 共著、米国カリフォルニアでのACM SIGMOD International Conference on Management of Data 議事録、2003年): 圧縮された XML データで、逆算術符号化方式をベースに直接効率的な問い合わせ処理が可能な XML コンプレッサーについて調べてください。
  • Compression and explanation using hierarchical grammars」(Craig G. Nevill-Manning、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、および Andrea Pugliese 共著、ドイツ・ベルリンでの第 29 回国際 VLDB (Very Large Data Bases) コンファレンス議事録、2003年): XML データを圧縮して、その圧縮フォームで可能な限りデータの問い合わせを行う XQueC システムの詳細を学んでください。
  • XML compression techniques: A survey and comparison」(Sherif Sakr、Journal of Computer System Science (JCSS) 75(5)、2009年): この XML 圧縮方式に関する調査を熟読してください。
  • New to XML: XML を学ぶために必要なリソースを入手してください。
  • developerWorks の XML エリア: DTD、スキーマ、XSLT を含め、XML 分野でのスキルを磨くための資料を見つけてください。広範な技術に関する記事とヒント、チュートリアル、標準、そして IBM Redbooks については、XML 技術文書一覧を参照してください。
  • IBM XML 認定: XML や関連技術の IBM 認定技術者になる方法について調べてください。
  • developerWorks の Technical events and webcasts: これらのセッションで最新情報を入手してください。
  • Twitter での developerWorks: 今すぐ登録して developerWorks のツイートをフォローしてください。
  • developerWorks podcasts: ソフトウェア開発者向けの興味深いインタビューとディスカッションを聞いてください。
  • developerWorks オンデマンド・デモ: 初心者向けの製品のインストールおよびセットアップから熟練開発者向けの高度な機能に至るまで、さまざまに揃ったデモを見てください。

製品や技術を入手するために

  • gzip の Web サイト: compress に置き換わる圧縮ユーティリティー、gzip (GNU zip) をダウンロードして使ってみてください。
  • bzip2 の Web サイト: この無料で入手できる高品質のデータ・コンプレッサーをダウンロードして試してください。
  • XMill プロジェクトの Web サイト: ユーザーが構成可能な XML コンプレッサーをダウンロードして試してみてください。このコンプレッサーは、構造、レイアウト、データを切り離し、データ要素を個別のデータ・ストリームに配信します。
  • XMLPPM プロジェクトの Web サイト: テキスト圧縮のPPM アルゴリズムとツリー構造の MHM データを組み合わせたデータ圧縮プログラムをダウンロードして試してみてください。
  • RNgzip プロジェクトの Web サイト: Relax NG スキーマとして表現された文書タイプをベースとした圧縮手法をダウンロードして試してみてください。
  • IBM 製品の評価版: DB2、Lotus、Rational、Tivoli、および WebSphere のアプリケーション開発ツールとミドルウェア製品を体験するには、評価版をダウンロードするか、IBM SOA Sandbox のオンライン試用版を試してみてください。

議論するために

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=XML, Open source
ArticleID=753240
ArticleTitle=最先端の XML 圧縮手法の調査
publish-date=08262011