第2章へ
Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)
コンピュータ分野、特にコンピュータ通信分野では、通信時間と電話料金を節約するためにデータを圧縮してファイルサイズを小さくすることが常識となっています。 我々ネットサーファーがいつもお世話になっているこのデータ圧縮について、その種類と原理を簡単に説明してみましょう。
| データ圧縮 | 可逆圧縮 (無雑音圧縮) | 静的符号化 | シャノン・ファノ符号化 | |
|---|---|---|---|---|
| ハフマン符号化 | ||||
| 算術符号化 | ||||
| 動的符号化 | 連長符号化 | |||
| 動的ハフマン符号化 | ||||
| ユニバーサル符号化 | LZ符号化 | |||
| BSTW符号化 | ||||
| インターバル符号化 | ||||
| 非可逆圧縮 (有雑音圧縮) | 画像符号化 | JPEG圧縮法 | ||
| 音声符号化 | ||||
データ圧縮には大きく分けて「可逆圧縮(reversible compression)」と「非可逆圧縮(inreversible compression)」の２種類があります。 可逆圧縮は元のデータを完全に復元することができる圧縮法で、圧縮／展開(解凍)処理によってデータに雑音が入らないため「無雑音圧縮(noiseless coding)」と呼ばれることもあります。 テキストデータやプログラムファイルを圧縮する場合は、元のデータを完全に復元する必要がありますので可逆圧縮が用いられます。 それに対して非可逆圧縮は元のデータを完全には復元することができない圧縮法で、圧縮／展開処理によってデータに多少雑音が入るため「有雑音圧縮(noisy coding)」と呼ばれることもあります。 画像データや音声データを圧縮する場合、多少の雑音は入ってもだいたい元のデータに近いデータを復元すれば良い時があり、そのような場合には非可逆圧縮が用いられます。
可逆圧縮はデータについてあらかじめある種のモデル(法則)を作成し、それに基づいてデータを符号化していく「静的符号化(static coding)」と、データを符号化していく過程で動的にモデルを作成・更新していく「動的符号化(adaptive coding)」とに大別できます。 静的符号化では最初に全データをスキャンしてモデルを作成し、次に符号化するという２パスで圧縮することが多く、展開過程に比べて圧縮過程に時間がかかるのが普通です。 それに対して動的符号化ではデータを符号化しながら動的にモデルを作成・更新していくため、圧縮過程にあまり時間がかかりません。
以上のような観点から各種の圧縮法を分類しますと、上表のようになります。
基本的に、データ圧縮とは元のデータを別の符号に変換することにより全体のバイト数を減らす方法です。 その際、元データが持つ冗長性(繰り返し性)、法則性(予測可能性)、不要性という性質を上手に利用してデータを圧縮します。
一番単純な圧縮法である連長符号化(Run Length Encoding、RLE)は、コードの冗長性を利用して元データをコードの繰り返し数とそのコードという２バイトの符号に変換します。
例えば「すもももももももものうち」というデータは「１す８も１の１う１ち」と符号化することができ、これによって12バイトの元データを10バイトに圧縮することができます(説明の都合上、コードとして日本語を用いていますが、これは１バイトコードと考えてください。(^_-))。 符号化された「１す８も１の１う１ち」から元データを復元するには、１バイト目の数だけ２バイト目のコードを出力するだけですから非常に簡単です。
この方法は同じコードが３個以上連続して続く場合にしか圧縮効果がありませんので、テキストデータよりも画像データの圧縮に向いています。
連長符号化はコードの冗長性を利用したものですが、コードそのものではなく、コードの組み合わせパターン(語句)の冗長性を利用して、元データを「ここからのデータは何文字前の何文字分と同じである」ということを表す符号に変換する手法がLZ符号化です。
例えば「カエルピョコピョコミピョコピョコアワセテピョコピョコムピョコピョコ」は「カエルピョコ３３ミ７６アワセテ10６ム７６」と符号化することができ、これによって33バイトの元データを20バイトに圧縮することができます。 符号化された「カエルピョコ３３ミ７６アワセテ10６ム７６」から元データを復元するには、次のようにします。
この方法は元データ中のコードの組み合わせパターンとその位置を記憶し、元データを辞書のように参照しながらコード化しますので、「スライド辞書法」と呼ばれることもあります。 この方法ですと、同じコードが連続していなくてもコードの組み合わせパターンの同じのものがあれば圧縮できますので、連長符号化よりも大きな圧縮効果が期待できます。
データの法則性を利用した圧縮法の代表的なものが、古典的な圧縮法として有名なハフマン符号化です。 この方法は色々な記号を一定のビット数で符号化する通常の固定長符号ではなく、記号ごとにビット長が異なる可変長符号(Variable Length Code、VLC)を用い、頻繁に出てくる記号は短いビット数で符号化し、あまり出てこない記号は長いビット数で符号化することにより、全体としてデータを圧縮する手法です。 その際、元データ中に存在する記号の出現率という法則性を利用して符号化しますので、あらかじめ元データをスキャンして全ての記号の出現率を求めておく必要があります。
例えば前例の「カエルピョコピョコミピョコピョコアワセテピョコピョコムピョコピョコ」では、各記号(ここでは文字)の出現頻度と出現率は次のようになります。
| ピ：８個(8/33) | ョ：８個(8/33) | コ：８個(8/33) | カ：１個(1/33) | エ：１個(1/33) | ル：１個(1/33) |
| ミ：１個(1/33) | ア：１個(1/33) | ワ：１個(1/33) | セ：１個(1/33) | テ：１個(1/33) | ム：１個(1/33) |
この11種類の記号に対して、次のような可変長符号を割り当てます。
| ピ＝0 | ョ＝1 | コ＝00 | カ＝01 | エ＝10 | ル＝11 |
| ミ＝000 | ア＝001 | ワ＝010 | セ＝011 | テ＝100 | ム＝101 |
これらの符号は可変長符号ですから、連続しますと符号と符号の区切りがわからなくなってしまいます。 そこで符号の前に(符号長−１)を表す２ビットの整数を付け加えて、符号の区切りがわかるようにします。
| ピ＝000 | ョ＝001 | コ＝0100 | カ＝0101 | エ＝0110 | ル＝0111 |
| ミ＝10000 | ア＝10001 | ワ＝10010 | セ＝10011 | テ＝10100 | ム＝10101 |
この符号を用いて元データを符号化しますと、次のようになります。
| カ 0101 | エ 0110 | ル 0111 | ピ 000 | ョ 001 | コ 0100 | ピ 000 | ョ 001 | コ 0100 | ミ 10000 | ピ 000 | ョ 001 | コ 0100 | ピ 000 | ョ 001 | コ 0100 | |
| ア 10001 | ワ 10010 | セ 10011 | テ 10100 | ピ 000 | ョ 001 | コ 0100 | ピ 000 | ョ 001 | コ 0100 | ム 10101 | ピ 000 | ョ 001 | コ 0100 | ピ 000 | ョ 001 | コ 0100 |
このようにして符号化したデータは122ビット＝16バイトとなり、元のデータの半分ほどのサイズになります。 ただしこのデータの場合、記号の種類が12個しかありませんから４ビットの固定長符号でも表現することができ、その場合は33×４＝132ビットとなりますので、実質的な圧縮効果は10ビットと考えた方が適当でしょう。
符号化されたデータから元データを復元するには、元の記号と可変長符号との対応表を記憶しておき、それを参照しながら可変長符号を元の記号に逆変換します。 通常、元の記号はASCIIなどの固定長符号で符号化されていますから、この場合は固定長符号を可変長符号に変換していることになります。
このように、固定長符号を可変長符号に変換するものを「FV符号(Fixed-to-Variable code)」といいます。 それに対して、連長符号化のように固定長符号を別の固定長符号に変換するものを「FF符号(Fixed-to-Fixed code)」といいます。
不要性を利用した圧縮法はデータ中の不要なデータあるいは重要度の低いデータを削除してしまう手法で、たいていは元データを完全には復元できない非可逆的圧縮になります。
例えば「祇園精舎の鐘の声、諸行無常の響きあり。 娑羅双樹の花の色、盛者必衰の理をあらはす。 おごれる人も久しからず、唯春の夜の夢のごとし」を、「祇園精舎鐘声有諸行無常響。 娑羅双樹花色表盛者必衰理。 奢人不久唯如春夜夢」と要約したり、「諸行無常・盛者必衰」あるいは「平家物語の冒頭部分(^^;)」と要約したりするようなものです。
また非可逆的圧縮の代表的な手法であるJPEG圧縮は、元データの色相データを間引くと同時に、輝度関数を三角関数で近似し、画像の細かい部分を表現する高周波成分をカットしてしまう、不要性を利用した圧縮法です。
一般に非可逆圧縮は可逆圧縮よりも大きな圧縮効果がありますが、圧縮されたデータから元データを正確に復元することができないため、画像データや音声データの圧縮にしか用いられません。 このため、ここではより一般的な可逆圧縮を中心にして説明することにします。
データを圧縮すれば、当然のことながらその圧縮効果を評価したくなるのが人情というものですが、それには次のような評価尺度を用いるのが一般的です。
圧縮されたデータのビット長(またはバイト長)と、元データのビット長(またはバイト長)の比として定義される値で、次のような式で表されます。
| 圧縮率(％)＝ | 圧縮後(符号化後)データのビット長 ─────────────── 圧縮前データのビット長 | ×100 |
例えば前節の「すもももももももものうち」を連長符号化で圧縮した例の圧縮率は、以下のようになります。
| 圧縮率＝ | 10×8 ─── 12×8 | ＝ | 80 ── 96 | ≒0.833(83.3％) |
なお、この値は圧縮効果が大きいほど小さな値になりますので、「圧縮率が高い」という表現は注意して使う必要があります。
元データの記号が平均何ビットで符号化されるかを表す値で、圧縮されたデータのビット長を元データの記号数で割った値として定義されます。
| 平均符号長(ビット)＝ | 圧縮後(符号化後)データのビット長 ─────────────── 圧縮前データの記号数 |
例えば前節の「カエルピョコピョコミピョコピョコアワセテピョコピョコムピョコピョコ」をハフマン符号化で圧縮した例の平均符号長は、以下のようになります。
| 平均符号長＝ | 122 ── 33 | ≒3.7ビット |
この値も圧縮効果が大きいほど小さな値になります。 そして元データが通常の８ビット固定長符号を用いている場合、圧縮率との間には次のような関係があります。
| 平均符号長(bit)＝ | 圧縮率 ─── 100 | ×８ |
| 圧縮率(％)＝ | 平均符号長 ───── ８ | ×100 |