データ圧縮入門

データ表現の理論と戦略

この記事は基本的なデータ圧縮についての入門記事で、圧縮技術に関する数学的な内容とアルゴリズムを初心者向けに解説しています。そして自分が作成するアプリケーションにはどのタイプの圧縮ツールと技術が適しているかを評価できるように、簡単な考察と例が示されています。また、より高度な理論的検討を行っているサイトや、簡単に使える圧縮ツールと圧縮ライブラリーを紹介しているサイトへのリンクも記載してあります。[更新情報: 表のフォーマットの問題を修正するために表 1 と表 2 を更新しました。― 編集者より]

David Mertz, President, Gnosis Software, Inc.

David MertzDavid Mertz は多くの分野で活躍しています。ソフトウェア開発や、それについて著述もしています。その他、学術政策理念について分野を問わず、関係する雑誌に記事も書いています。かなり以前には、超限集合論、ロジック、モデル理論などを研究していました。その後、労働組合組織者として活動していました。そして、David Mertz 自身は人生の半ばにもまだ達していないと思っているので、これから何かほかの仕事をするかもしれません。



2012年 2月 10日 (初版 2001年 5月 01日)

データ圧縮は、プログラミングのさまざまな状況で広く使われています。普及しているオペレーティング・システムとプログラミング言語はすべて、さまざまな種類のデータ圧縮を扱える多数のツールとライブラリーを備えています。個々のアプリケーションに対してどの圧縮ツールとライブラリーを選択するのが適切であるかは、対象がストリーミングなのかファイルなのか、データにどんなパターンと規則性が予想されるのか、CPU 使用率/メモリー使用率/チャネル要求/ストレージ要件において相対的にどれが重要であるのかなど、対象のデータとアプリケーションの特性によって異なります。

では、データ圧縮とはいったい何でしょうか。簡単に言えば、データ圧縮とはデータから「冗長性」を除去することです。情報理論用語で言えば、圧縮とは圧縮テキストの「エントロピー」を増大させることですが、基本的にこれらの表現は、定義として正しいというにすぎません。冗長性は多くの形を取ります。例えば、繰り返しビット・シーケンス (11111111) は冗長性の 1 つのタイプであり、繰り返しバイト・シーケンス (XXXXXXXX) はそれとは別の冗長性のタイプです。しかし大抵の場合、冗長性はデータ・セット全体での規則性か、相対的に共通性があるさまざまな長さからなるシーケンスのいずれかとして、より大きなスケールで現れる傾向にあります。基本的に、データ圧縮の目的は、「一般的な」データ・セットが与えられたときに、よりコンパクトな表現を生成するデータ表現アルゴリズム変換法を見つけることです。この説明ではちょっと難しいと思われた方も、この後でさらに具体的な例をいくつか説明するので、このまま読み進めてください。

可逆圧縮と非可逆圧縮

実際に、可逆 (lossless) 圧縮と非可逆 (lossy) 圧縮という 2 つの根本的に異なるデータ圧縮「方式」があります。この記事では、主に可逆圧縮技術について説明しますが、まず始めに両者の違いについて理解しておくと、後で可逆圧縮技術を理解する助けになります。「可逆圧縮」とは、データ・セットの表現を変換する 1 つの方法であり、この方法による変換後のデータ・セット表現に対して復元変換を実行すると「正確に」元のデータ・セットを復元することができます。一方の「非可逆圧縮」も、データ・セットの表現を変換する 1 つの方法ですが、非可逆圧縮の場合は復元変換を実行すると元のデータ・セットに「きわめてよく似た」データ・セットが復元されます。非可逆圧縮技術の利点は、生成するデータ表現が可逆圧縮技術よりもはるかにコンパクトになるケースが多いことです。非可逆圧縮技術は多くの場合、画像、音声、動画を圧縮するために使われます。非可逆圧縮は、視聴者がデジタルの画像や音声の 1 つひとつのビットパターンを認識するのではなく、その画像や音声の全体的な形態としての特徴を認識する場合においては適切であると言えるでしょう。

通常のデータという観点から見れば、非可逆圧縮は選択肢とはなり得ません。自分が作成したプログラムと「大体同じような」ことをするプログラムや、自分が入力した情報と「大体同じような」情報が入っているデータベースは必要ありません。少なくともほとんどの目的には非可逆圧縮は必要ありません (実際のものに似せた模倣表現が既に使われているところ (画像や音声など) を除いて、非可逆圧縮が実用されている例を私はほとんど知りません)。


データ・セットの例

まず、この記事の例で使用するための仮想データを具体的に表現することから始めましょう。理解しやすい例を以下に示します。マサチューセッツ州グリーンフィールドの町では、電話の市内局番は、772-773-774- となっています (米国以外の読者のために: 米国では市内番号は 7 桁で、一般に ###-#### という形式で表され、先頭 3 桁の市内局番は地理的ブロック単位で割り当てられます)。市内番号の先頭 3 桁には、これら 3 つの市内局番が同じように広く割り当てられているものとし、末尾 4 桁は任意の番号がかなり均等に分布しているものとします。検討対象のデータ・セットは、「現在実際に使われている全電話番号のリスト」です。このリストがプログラミングする上でなぜ検討する価値があると考えられるのかは、さまざまな理由が挙げられますが、それについてはここでは問題にしないことにします。

検討対象のデータ・セットの初期状態は、ある特定のデータ表現形式、つまり複数コラム形式によるレポート (おそらく何らかのクエリーあるいはコンパイル・プロセスの出力として生成されたもの) として表示されています。このレポートの最初の数行が以下のようになっていると仮定します。

表 1. 複数コラム形式によるレポート

=============================================================
772-7628     772-8601     772-0113     773-3429     774-9833
773-4319     774-3920     772-0893     772-9934     773-8923
773-1134     772-4930     772-9390     774-9992     772-2314
[...]

ホワイトスペースの圧縮

ホワイトスペースの圧縮というのは、ごく一般的には、「興味のないものを除去する」方法と見なすことができます。このホワイトスペースの圧縮技術が技術的には非可逆圧縮技術だとしても、実際に使われている多くのデータ表現形式にとっては依然として有効なものです。たとえば、HTML をテキスト・エディターで読むにはインデントや行送りがあった方がはるかに読みやすいとしても、それらの「ホワイトスペース」は、その HTML 文書を Web ブラウザーで表示したときの見た目には何の影響も与えないはずです。HTML 文書が Web ブラウザー (あるいは Web ロボット/スパイダー) 用だけに作られていると知ったら、その文書がより速く送信され、ストレージ内で占めるスペースが少なくなるように、文書からホワイトスペースをすべて取り除くのが賢明かもしれません。実際、ホワイトスペースの圧縮で除去されるものには、最初からいかなる機能もありません。

この記事で先ほど挙げた電話番号の例では、表示されたレポートからかなりのものを除去することができます。1 行目の「=」行にも、電話番号内の「-」にも、電話番号間の空白にも機能は何もありません。これらはすべて、本来のレポートを人間が読むのには役立ちますが、レポートをいったん「データ」と考えてしまうと重要なものではなくなります。除去されるものは、正確には昔ながらの用語でいう「ホワイトスペース」ではありませんが、意味するところは同じです。

ホワイトスペースの圧縮は、きわめて簡単に実行することができ、データ・ストリームを読み込んで、出力ストリームからいくつかの特定の値を取り除くだけの作業です。多くの場合、「復元」手順はまったく必要になりません。データ・ストリームのどこかで元のデータに近いものを再構築する場合でも、復元に CPU やメモリーをほとんど必要としないはずです。復元されるものは、圧縮前のものと正確に同じものかもしれませんし、正確には同じでないかもしれません。どちらになるかは、元のデータにどのような規則と制約が関係していたかによります。テキスト・エディターで人間が入力した HTML ページには、おそらく、ちょっと変わったスペーシングがあるはずです。自動化ツールは大抵の場合、HTML に「妥当な」インデントとスペーシングを挿入します。電話番号の例のようにレポートのフォーマットが固定している場合は、「復元用フォーマッター」によって必ず元の表現が復元されます。


ランレングス符号化

ランレングス符号化 (RLE) は、最も簡単で広く使われている可逆圧縮技術です。RLE は、復号する場合はなおさらのこと、ホワイトスペースの圧縮と同じように簡単です。RLE の背景となっている考え方は、データ表現の多くは大体において繰り返されるバイトから成るストリングで構成されているというものです。具体例に挙げた電話番号のレポートは、そのようなデータ表現の一例です。レポートは、「=」の繰り返しから成るストリングで始まっており、レポート中にスペースから成るストリングが散らばっています。RLE では 1 つひとつの文字を、その文字を表す固有のバイトのみで表現するのではなく、(ところどころで、もしくは常に) 文字が繰り返される回数に文字を表すバイトを続けて表現します。

想定されるデータ表現の中に繰り返されるバイトがかなり多く含まれている場合には、1 バイト以上繰り返されている回数とそれに続く 1 文字を常に指定するアルゴリズムは、適切かつ効率的かもしれませんが、1 文字長のストリングに対してこのアルゴリズムを適用すると、ストリング符号化に 2 バイト (あるいはそれ以上) が必要となります。具体例を挙げると、入力ストリームのたった 1 個の ASCII 文字「X」に対して、00000001 01011000 という出力ビット・ストリームが必要になるわけです。その反面、1 行に 100 個の「X」があった場合は、出力は 01100100 01011000 となり、非常に効率が良くなります。

RLE のバリエーションでよく使われている手法は、繰り返し回数を表すためと、バイトの値そのものを表すためとでバイトを選択的に使い分けるというものです。この手法では繰り返し回数を表すためのバイトを最低 1 バイトを確保しておかなければなりませんが、必要であれば、繰り返し回数を出力しないようにすることができます。この手法の例を挙げると、先ほどの電話番号レポートの例では、入力ストリームのすべてが単なる ASCII 文字であることがわかっています。しかも、それらの文字はすべて、ASCII 値の最上位ビットが 0 となっているため、この ASCII 最上位ビットを、通常の文字ではなく、繰り返し回数を表していることを示すために利用することができます。繰り返し回数を表すバイトの場合、残り 7 ビットは繰り返し回数を表すために使うことができます。そして、それに続くバイトは繰り返される文字を表します。したがって、たとえば、ストリング “YXXXXXXXX” は以下のように表現することができます。

"Y" Iter(8)  "X"
01001111 10001000 01011000

この例では、繰り返し回数を表すバイト値を省略する方法は示していません。また、同じ文字が 127 個を超えて連続している場合には利用できません。しかし、RLE のバリエーションでは必要に応じてこのような問題に対応します。


ハフマン符号化

ハフマン符号化では、データ・セット全体のシンボル・テーブルを参照します。圧縮は、データ・セットの各シンボルの「重み」を見出すことによって実現されます。つまり、ハフマン符号化ではシンボルによって出現頻度が異なることを利用して、出現頻度の高いシンボルは、出現頻度の低いシンボルが使うビット数よりも少ないビット数で符号化するという方法を提唱しています。ハフマン形式の符号化にはバリエーションがいくつかありますが、元々の (そして頻繁に利用される) バリエーションでは、最もよく使われているシンボルを探し、1 ビットだけ使って (例えば 1 として) 符号化するという方法が採られています。0 が現れた場合は、もっと長いビット長の符号で表すシンボルを符号化していることがわかるわけです。

例として、グリーンフィールドの町の電話帳にハフマン符号化を適用してみましょう (レポートはすでにホワイトスペースが圧縮されているものとします)。その結果、以下に示すものが得られるとします。

表 2. ハフマン符号化の結果

Encoding   Symbol
 1           7
 010         2
 011         3
 00000       4
 00001       5
 00010       6
 00011       8
 00100       9
 00101       0
 00111       1

データ・セットの最初の電話番号のシンボル・セットは、すでに 4 ビット・シーケンス (ニブル) として (圧縮なしで) 直接符号化してあります。上記のハフマン符号化は、最悪のケース (最も頻度の低いシンボル) に対して最大 5 ビットを使うことになり、明らかにニブル符号化よりもビット効率が悪くなっています。しかし、最良のケースではたった 1 ビットしか使うことにならず、しかも最良のケースはデータ・セットをスキャンした結果、最も頻度の高かったケースです。従って、ハフマン符号化を使って最初の電話番号を符号化すると、以下のように符号化できるはずです。

772 7628 --> 1 1 010 1 00010 010 00011

この電話番号を表現するのに、ニブル符号化では 28 ビット必要になりますが、このハフマン符号化では 19 ビットで済みます。上記の例では、見やすくするために空白を挿入してありますが、符号化したものをアンパックする際には空白は必要ありません。符号化テーブルによって、符号化されたシンボルの最後に達したかどうかを判別できるからです (ただし、ビット・シーケンス内でどのビットを対象としているかを追跡する必要はあります)。

ハフマン符号化では、復号化サイクルは依然としてかなり簡単な処理ですが、テーブル・ルックアップが必要なため、RLE ほど軽くはありません。ハフマンの符号化についてはかなり手間がかかります。全データ・セットをスキャンして、頻度テーブルを作成する必要があるからです。ハフマン符号では「近道」が適当な場合があります。標準のハフマン符号は、符号化が行われている特定のデータ・セットに対し、出力データ・ストリームの先頭にデータ・セット固有のシンボル・テーブルを追加して適用されます。しかし、1 つのデータ・セットだけでなく、符号化された全タイプのデータが同じ規則性を持っている場合は、グローバルなハフマン・テーブルを選ぶことができます。このグローバル・ハフマン・テーブルがあれば、ルックアップを実行可能プログラムにハード・コーディングすることができます。こうして、圧縮と復元の両方の処理をかなり軽減することができます (ただし、最初のグローバル・サンプリングとハード・コーディングは除きます)。たとえば、データ・セットが英語の散文であることがわかっている場合は、文字頻度テーブルはよく知られており、データ・セット全体にわたってよく合致します。


Lempel-Ziv 圧縮

最も重要であると思われる可逆圧縮技術は Lempel-Ziv です。この記事で説明するのは LZ78 ですが、LZ77 やその他のバリエーションも似たような方法で動作します。LZ78 の考え方は、動的なテーブルを使ってストリーミング・バイト・シーケンスを符号化するというものです。ビット・ストリームの圧縮を開始するに当たり、LZ テーブルには実際のシンボル・セットといくつかの空のスロットが格納されます。さまざまな大きさのテーブルが使われますが、上記電話番号の例 (ホワイトスペースは圧縮済み) では 32 個の番号が登録されているテーブルを使うものと想定します (電話番号以外のほとんどのタイプのデータの場合、32 個ではエントリー数があまりにも少なすぎますが、上記例では問題ありません)。最初にやることは、先頭の 10 個のスロットにアルファベット (数字) を格納することです。新しいバイトが入ってきたときには、バイト・シーケンスと一致する最も長いシーケンス (シーケンス長を N とします) を格納している既存のエントリーを出力し、その後で一致したバイト・シーケンスに次のバイトを追加した N+1 の長さのシーケンスを次の空きスロットに格納します。最悪のケースでは、1 つのシンボルに対して 4 ビットではなく 5 ビットを使っていますが、最終的には多くのケースで複数シンボルに対して 5 ビットを使うようになります。例えば、マシンが以下のような結果を出力するものとします (テーブル・スロットは角カッコでくくられています)。

7 --> Lookup: 7 found       --> nothing to add    --> keep looking
7 --> Lookup: 77 not found  --> add '77' to [11]  --> output [7]=00111
2 --> Lookup: 72 not found  --> add '72' to [12]  --> output [7]=00111
7 --> Lookup: 27 not found  --> add '27' to [13]  --> output [2]=00010
6 --> Lookup: 76 not found  --> add '76' to [14]  --> output [7]=00111
2 --> Lookup: 62 not found  --> add '62' to [15]  --> output [6]=00110
8 --> Lookup: 28 not found  --> add '28' to [16]  --> output [2]=00010

ここまでは、取り立てて説明するほどのことはありませんが、続けて次の電話番号に進むと以下のような結果が得られます。

7 --> Lookup: 87 not found  --> add '87 to [17]   --> output [8]=00100
7 --> Lookup: 77 found      --> nothing to add    --> keep looking
2 --> Lookup: 772 not found --> add '772' to [18] --> output [11]=01011
8 --> Lookup: 28 found      --> nothing to add    --> keep looking
6 --> Lookup: 286 not found --> add '286' to [19] --> output [16]=10000
....

パターンを示すには、ここまでの手順で十分です。最終的な圧縮はまだ何も実現していませんが、すでにスロット 11 とスロット 16 を使うことによって、それぞれ 2 つのシンボルを 1 つの出力としていることに注意してください。また、スロット 18 には非常に有用なバイト・シーケンス 772 が格納されています。このスロット 18 は、ストリームの後の方で有用になることがわかります。

LZ78 が行っていることは、1 つのシンボル・テーブルを (希望としては) 有用なエントリーで満たした後、それを書き出し、クリアし、新たなテーブルを始めることです。この点で、エントリーが 32 個のシンボル・テーブルは、おそらくまだ小さすぎるでしょう。それは、772 などの再利用があまり行われないうちにシンボル・テーブルがクリアされてしまうからです。しかし小さなシンボル・テーブルは、説明するのが簡単です。

通常のデータ・セットにおいては、Lempel-Ziv 圧縮のバリエーションはハフマン符号化や RLE よりはるかに優れた圧縮率を実現します。その一方で、Lempel-Ziv 圧縮のバリエーションは、サイクル全体を通じて非常に高価なものとなり、メモリー内で大きなテーブルを使う可能性があります。実際には、ほとんどの圧縮ツールとライブラリーでは、Lempel-Ziv 技術とハフマン技術が組み合わされて使われています。


正しい問題を解く

正しいアルゴリズムを選択することで、間違ったアルゴリズムを大幅に最適化するよりも桁違いに大きな改善が図れることがよくあるのとまったく同様に、大抵は正しいデータ表現を選択することの方が、どの圧縮方法を選択するかよりも (どの圧縮方法も求められる特徴を後から最適化するようなものです) はるかに重要です。この記事で使った簡単なデータ・セットの例は、問題の概念化をやり直した方が、ここで説明されているどの圧縮技術を使うよりも実際のところはるかに優れた方法となる完全なケースです。

もう一度この記事で取り上げたデータが何を表しているか考えてみましょう。このデータはあまり一般的なデータの集合ではなく、厳格な事前の制約によって問題全体を再構成することができます。私達が抱えているのは、最大で 3 万件の電話番号 (7720000 から 7749999) で、使われているものもあれば、使われていないものもあります。そこで今度は、ここまでのように使われている各電話番号を完全に表現するのではなく、それが確かに使われているという 2 進法的な事実を示してみます。この問題については次のように考えます。単にメモリーとストレージを 3 万ビット割り当てることで、それぞれのビットに対応する電話番号が使われているか否かを「はい」か「いいえ」で各ビットによって示すことができます。ビット配列におけるビットの順番は、その電話番号の範囲内で最小の番号から最大の番号までの単純な昇順とすることができます。

このビット配列ソリューションは、ほぼあらゆる点で最良のソリューションです。このデータ・セットを表すには、正確に 3750 バイトを要します。さまざまな圧縮技術で使われるストレージ容量は、データ・セットの電話番号の数と圧縮効率の両方によって変わってきます。もし、最大で 3 万件の電話番号のうち 1 万件が使われており、非常に効率の良い圧縮技術でも電話番号 1 件につき数バイト必要な場合には、ビット配列は桁違いに良い方法です。CPU 要件の面では、ビット配列は検討した圧縮方式のどれよりも優れているだけでなく、数字をすべてストリングとして一覧表示する単純な非圧縮方法よりも優れている可能性がきわめて高くなります。ビット配列を通じて処理を実行し、「現在使われている電話番号」カウンターのインクリメントをきわめて効率的にすることができ、大部分は最新の CPU のオンチップ・キャッシュ内で行えます。

この非常に簡単な例から学ぶべき教訓は、(この問題がそうであるように) あらゆる問題に必ず何らかの魔法の近道があるということではありません。多くの問題は実際にかなりのメモリー、帯域幅、ストレージ、CPU リソースを必要とします。そうしたケースの多くで圧縮技術がこれらの負担を軽減する、あるいはシフトする一助となります。しかし、もっと適切な教訓を示すことができます。それは、圧縮技術を適用する前にデータ表現の概念化を開始し、その概念化が適切なものであることを確認するのが賢明であるという教訓です。

Claude Shannon 氏に敬意を表します。

参考文献

コメント

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=Linux
ArticleID=226656
ArticleTitle=データ圧縮入門
publish-date=02102012