可逆圧縮

3つの基本的なアイディア

プログラムやデータなど変化しては困るものは可逆圧縮をする。

様々な方法があるが、基本的なアイディアは3つほどである。そのアイディアをどのように具体的にするか(実装)、またどう組み合わせるか、それぞれ欠点・弱点があるのでどのように対策をとるのかなどで様々な方式があり、これからも発展があるかもしれない分野である。

基本的なアイディア 特徴
ランレングス 繰り返しがあるとき、一つのデータとその繰返し数を記録する
LZ法 既に出てきたデータの並びと同じ部分がある時に「どこから」「どれだけの長さ」と一致しているのかのデータに置き換えて記録する
エントロピー符号化
(ハフマン圧縮)
出現回数の多いデータを短い記号に置き換える。一般に変換表が必要

よく目にするZIPはDeflate(デフレート)と呼ばれる圧縮アルゴリズムが使われている。これはLZ法とハフマン圧縮を組み合わせたものである。

ランレングス

たとえば次のデータは24バイトの文字データである。

AAAABBBBBBBCCCAAAABBBBDD

繰り返しているので繰り返しの数を書くことで短くすることができる。

A4B7C3A4B4D2

12バイトで済む。

(上記では数を文字として書いているが、数値として1バイトの符号なし整数を使えば255回の繰り返しまで表現できる)

繰り返していないときにどうするかを対策しないと、データ量がかえって増加することがある。

たとえば

ABCDB

A1B1C1D1B1

となってしまう。

LZ法

たとえばランレングスで用いた24バイトの文字データで考える。

AAAABBBBBBBCCCAAAABBBBDD

強調した部分は前に一度出てきたパターンである。この場合前に出てきた位置と長さをそれぞれそれぞれ記録することにする。記録方法はいろいろな方法が考えられるが、符号なし整数1バイトで表現すれば255までは表現できて次の様になる。

*で前に出てきたパターンの繰り返しであることを示し、1は1文字目からの意味で、8は8文字の長さであることを表す。

AAAABBBBBBBCCC*18DD

実際のデータは文字をASCIIで表すとすれば18が文字コードでなく整数になっていることが分かる。

文字 AAAA BBBB BBBC CC*1 8 DD
ASCII 41414141 42424242 42424243 43432A01 08 4444

文章が255文字よりも多いことは十分に考えられるのでバイト数を増やすとか、位置の基準を現在処理中の文字にして何文字前から何文字という指定のしかたにするなどの工夫がある。似た文字のパターンは近くにあるだろうという予測である。

今の場合は14文字前なので次の様になる。

文字 AAAA BBBB BBBC CC*14 8 DD
ASCII 41414141 42424242 42424243 43432A0E 08 4444

*を文字そのものとして使うためには工夫が必要となる。たとえば*0と0を続けて書くことにする。「0文字前から」は使うことのないからこれが出てきたら普通の文字のあつかいをすると決めておくのである。

ハフマン圧縮

たとえばランレングスで用いた24バイトの文字データで考え、各文字の出現回数を表にする。

AAAABBBBBBBCCCAAAABBBBDD
文字出現回数コード出現回数×コード長
B11011
A81016
C31109
D21116
2442

多く出てくる文字に短いコードを割り当てる。コードはビット単位の可変長である。

このコードで書き出すと

101010100000000110110110101010100000111111

つまり全部で42ビットで済むことになる。

この場合、文字がABCDの4種類しかないので新たにこの文字のために固定長の文字コードをつくるとしたら1文字につき2ビット。24文字では48ビット必要になるので6ビット圧縮されたことになる。

2ビットの文字コードは、例えば次のようなもの

文字出現回数コード出現回数×コード長
A80016
B110122
C3106
D2114
2448

もしこの24文字がASCIIコードで保存されるとしたら8×24=192ビット必要である。

文字出現回数ASCIIコード出現回数×コード長
A80100000164
B110100001088
C30100001124
D20100020016
24192

ASCIIコードは標準規格で固定されているから文字コード表は不要だが、ハフマン法ではデータの出現頻度に合わせてデータごとに異なるコードを作るので、実際の使用ではコードと文字の対応表も記録しなければならない。したがってある程度長いデータでないと圧縮の効果が出ない。また、この対応表も短くする方法も考えられている。