データ圧縮について

by　だうぴ

１．なぜデータを圧縮するのか。
データの圧縮を行う理由は、電話網などのネットワークでは使用時間に応じて課金されるので、送受信されるデータの量が少ないほど課金が少なくて済むためで、パソコン通信時代からオンラインでソフトウェア流通させるために必要なものとして発達してきました。
また、オンラインソフトウェアを流通させるためには複数のファイルを一つにまとめる機能がある方が便利なため、以上の２つの機能を持つソフトウェア（＝アーカイバ）として有名なのが、「ＬＨＡ」と「PKZIP」で、それぞれで圧縮したときのファイルの拡張子はｌｚｈ（何故lzhになるのかは後述します）、ｚｉｐになることで知られています。

２．どのようにデータを圧縮しているのか。
（Ａ）ランレングス符号化法
ファイルの圧縮、解凍の操作方法に関しては、lhasa特集などの初心者向けサイトにまかせることにして、実際にどのようにしてデータを圧縮しているのかについて触れていきます。
例えば、普通の紙をスキャナで読み込んだ以下のようなデータがあったとします。なお、先頭は必ず白から始まることがわかっていると仮定します。

白白白白白黒黒黒白白黒黒黒黒黒黒黒黒黒

ここで、白を1，黒を0として符号化すると

1111100011000000000　　　　・・・（１）

と合計19ビットの情報量が必要になります。しかし、白が５個、黒が３個、白が２個、黒が９個続いているので、「5329」と表現してあげれば情報量が少なくなるはずです。コンピュータでは２進数しか扱えないので、単純に5329を２進数にすると、10111101001となりますが、どこが切れ目かわからないのでこのままでは元に戻せません。101　11　10　1001と分ければ「5329」になりますが、10　11　110　1001と分けてしまうと「2369」になってしまいます。つまり、符号化する場合は元に戻せるような体系になっていなければなりません。
ここで、以下のような符号化表を用意します。

（１）の情報を上の符号化表に従って符号化すると

1000010001110000　　　　　・・・（１）’

となり、合計16ビットの情報量で済むので３ビット分圧縮されたことになります。
（１）’を（１）に上の表を使って戻せるか（復号できるか）どうかをやってみます。
（１）’の先頭ビットは　1　ですが、上の符号化表の符号項目に　1　はありません。先頭２ビットまで見ると、　10　ですが、やはりありません。先頭３ビットまでみると　100　ですが、やはりありません。先頭４ビットまでみると、　1000　ですが、符号項目に　1000　があり、対応するランレングス（連続数）は　５　になります。つまり最初は５ビット連続であることがわかります。
次に、５ビット目から同様のことを行うと、010　まで見た時点で、ランレングスが３になっていることがわかります。
そして、その次は同様に、001　でランレングスが２、最後が110000となるのでランレングスが９となります。
先頭は白から始まることがわかっているので、1111100011000000000　となり、元に戻すことが出来ます。

以上のように同じデータの連続数（ランレングス）に注目して圧縮する符号化法を、ランレングス符号化法といいます
ランレングス符号化法は、同じデータが連続している場合は高圧縮率が期待できますが、世の中には同じデータが連続しているということはあまりありません。使用例としては静止画フォーマットＲＬＥ形式等に利用されています。

（Ｂ）ハフマン符号化法
今度は、以下のようなデータがあったとします。

最近１０日間の天気
晴れ　晴れ　曇り　晴れ　雨　晴れ　曇り　雪　晴れ　晴れ

ここで単純に、晴れ　00　、曇り　01　、雨　10　、雪　11　、として符号化すると、

00 00 01 00 10 00 01 11 00 00　　　　　　・・・（２）

と情報量は20ビットになります。このデータの場合はランレングス符号化法では同一連続データがないため、ほとんど圧縮されません。
そこで、符号化表を以下のようなものにします。

以上の表で最初の天気を符号化すると

0 0 10 0 110 0 10 111 0 0　　　　　　・・・(2)'

となり、（２）と（２）’を比べると情報量が４ビット少なくなります。

以上のように、出現頻度の高いデータに短いビット数を使い、出現頻度の低いデータに長いビット数を割り当てて、全体としてデータの圧縮を行う符号化法をハフマン符号化法といいます。ハフマン符号化法は、Huffmanという人が、発明した方法のためそのように呼ばれています。また、（２）のようにデータによって符号長が変わらない場合をＦＬＣ（Fixed　Length　Code、可変長コード）、（２）’のようにデータによって符号長が変わる場合をＶＬＣ（Variable　Length　Code、可変長コード）と言います。
ハフマン符号化法は基本的な圧縮方法として、ＬＨＡやＰＫＺＩＰなどのアーカイバ、MNP5、MNP7等のプロトコルをはじめとして広い範囲で利用されています。

（Ｃ）Lempel-Ziv符号化法
ハフマン符号化法では、出現頻度を求めるのに１回、圧縮に１回、合計２回データの読み込みを行うため、処理速度が遅いという欠点があります。そこで、Abraham　Lempelと、Jacob　Zivの２人は、別の圧縮方法を考案しました。
Lempel-Ziv符号化法では、なるべく長い文字列が繰り返し現れるパターンを見つけだして、短い文字列に置き換えていくための辞書を作成します。
例えば、

というような感じの辞書データを作っていきます。パソコンを少々使い込んでいる人は、よく入力する長い単語に対して、短い名前で単語登録をしていると思いますが、それと同じ原理です。Lempel-Ziv符号化法では、辞書データが付加されるため、小さいデータでは逆にファイルサイズが大きくなってしまうことがあります。

LHAでは、圧縮符号化法にLempel-Ziv符号化法とハフマン符号化法を併用しています。拡張子がlzhとなっているのは、Lempel-ZivとHuffmanの頭文字から取られています。

Lempel-Ziv符号化法は、ＬＨＡやPKZIPなどのアーカイバ、ＧＩＦ静止画フォーマット、V42.bisなどのプロトコル、といった広い範囲で利用されています。

３．エントロピーと平均符号長

ときどき、「ＬＨＡで圧縮を繰り返せば、どんどんファイルサイズが小さくなっていくのですか？」という質問を受けることがあります。この質問に対する解答は、「２度目以降は圧縮してもファイルサイズは小さくならない」ということになります。では、何故そうなるのでしょうか？

オリジナルデータには、「本来の情報」部分と「冗長部分」から構成されています。LHAによる圧縮符号化では、「冗長部分」を省いて、「本来の情報」だけを残すということを行います。以下の図に示します


　冗長部分除去による情報圧縮

「本体の情報」だけにしたときの理論上の情報量は以下の式で求められます。


ただし、Ｐｉはデータiの出現確率、Σは全ての事象の和を取ることを意味しています。このＨのことをエントロピーといい、キャラクター当たりの符号長はＨより小さく出来ないという限界値を意味します。

それでは、ハフマン符号化法で使った例のデータで、エントロピーを求めてみます。

以上のデータでは、晴れ：６０％、曇り：２０％、雨１０％、雪１０％の確率になるのでエントロピーは

Ｈ＝−（０．６×log₂０．６＋０．２×log₂０．２＋０．１×log₂０．１＋０．１×log₂０．１）＝１．５７

データが合計１０個あるので、圧縮できる限界は
１．５７×１０＝１５．７
小数点は切り上げるので、データ全体では１６ビットになります。
もし、晴れ、曇り、雨、雪がそれぞれ確率２５％ずつだったとすると、キャラクター当たりの限界ビット数は２ビットになりますが、
それと比べるとかなり圧縮できることがわかります。これが冗長部分除去、すなわち圧縮の効果になります。

全体のビット数をデータ個数で割ったものを、平均符号長と呼びます。
上の例の場合、ハフマン符号化する前は、各データに２ビット固定長をを割り当てているので、平均符号長＝２ビット／シンボルになります。
ハフマン符号化した場合は、１６／１０＝１．６ビット／シンボルになります。

情報処理技術者試験（２種、１種、高度午前）を受験する予定の人は、エントロピーも出題範囲なので理解しておいて下さい

４．不可逆圧縮、離散コサイン変換（ＤＣＴ）

今までに述べてきたような方法で圧縮は出来ますが、エントロピーと呼ばれる圧縮限界があることがわかりました。
画像などでは、「本来の情報」だけでも大きいので、さらにデータを小さくするために「本来の情報」を削ってしまうということを行います。
「本来の情報」を削る場合は、人間の目をごまかせるような範囲で行います。そして、完全には元に戻らなくなります。
このような、不可逆圧縮を行っている例としては、ＪＰＥＧ静止画像フォーマットやＭＰＥＧ動画像フォーマットやＭＰ３音声フォーマットなどがあります。以上のフォーマットでは離散コサイン変換（Ｄiscrete　Ｃｏｓｉｎｅ　Ｔransform）ということを行っています。
これに対して、データを完全に元に戻すことが出来る圧縮方法を可逆圧縮といいます。

離散コサイン変換（ＤＣＴ）の演算式

画素数Ｎｘ×Ｎｙのデジタル画像情報が以下の図のように与えられたとき、ＤＣＴの演算式は以下のようになります。
ＤＣＴ、逆ＤＣＴの演算式を見れば気付く人もいると思いますが、ＤＣＴ、逆ＤＣＴは可逆演算です。
ＤＣＴ係数の量子化を行った時点で始めて不可逆圧縮となります。


逆に、ＤＣＴ係数Ｆ（ｕ，ｖ）が与えられたとき、画素値ｆ(x,y)を求める逆ＤＣＴの演算式は以下のようになります





JPEG画像の符号化は以下のような手順になります。
（１）画像を８×８のブロックに分割して、１ブロックの画像を得ます。
（２）0〜255の値をレベルシフトして-128〜127に変換します。
（３）ＤＣＴによって、ＤＣＴ係数を得る
（４）量子化テーブルを用いて、ＤＣＴ係数を量子化、すなわちデータの省略をする。このとき、視覚に対応して周波数の高い成分（表では右下の部分）の省略を大きくする。
（５）ハフマン符号化を行い、圧縮データが得られる。

JPEGデータを元に戻す場合は、
（１）ハフマン復号化を行う。
（２）量子化テーブルを用いて、逆量子化を行う。
（３）逆ＤＣＴを行う
（４）逆レベルシフトを行う。
（５）ブロックの結合を行い、復号画像を得る。
という手順になります。
以下に例を示します。