プログラムやデータなど変化しては困るものは可逆圧縮をする。
様々な方法があるが、基本的なアイディアは3つほどである。そのアイディアをどのように具体的にするか(実装)、またどう組み合わせるか、それぞれ欠点・弱点があるのでどのように対策をとるのかなどで様々な方式があり、これからも発展があるかもしれない分野である。
基本的なアイディア | 特徴 |
---|---|
ランレングス | 繰り返しがあるとき、一つのデータとその繰返し数を記録する |
LZ法 | 既に出てきたデータの並びと同じ部分がある時に「どこから」「どれだけの長さ」と一致しているのかのデータに置き換えて記録する |
ハフマン圧縮 | 出現回数の多いデータを短い記号に置き換える。一般に変換表が必要 |
よく目にするZIPはDeflate(デフレート)と呼ばれる圧縮アルゴリズムが使われている。これはLZ法とハフマン圧縮を組み合わせたものである。
たとえば次のデータは24バイトの文字データである。
AAAABBBBBBBCCCAAAABBBBDD
繰り返しているので繰り返しの数を書くことで短くすることができる。
A4B7C3A4B4D2
12バイトで済む。
(上記では数を文字として書いているが、数値として1バイトの符号なし整数を使えば255回の繰り返しまで表現できる)
繰り返していないときにどうするかを対策しないと、データ量がかえって増加することがある。
たとえば
ABCDB
は
A1B1C1D1B1
となってしまう。
たとえばランレングスで用いた24バイトの文字データで考える。
AAAABBBBBBBCCCAAAABBBBDD
強調した部分は前に一度出てきたパターンである。この場合前に出てきた位置と長さをそれぞれそれぞれ記録することにする。記録方法はいろいろな方法が考えられるが、符号なし整数1バイトで表現すれば255までは表現できて次の様になる。
*で前に出てきたパターンの繰り返しであることを示し、1は1文字目からの意味で、8は8文字の長さであることを表す。
AAAABBBBBBBCCC*18DD
実際のデータは文字をASCIIで表すとすれば1、8が文字コードでなく整数になっていることが分かる。
文字 | A | A | A | A | B | B | B | B | B | B | B | C | C | C | * | 1 | 8 | D | D |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
ASCII | 41 | 41 | 41 | 41 | 42 | 42 | 42 | 42 | 42 | 42 | 42 | 43 | 43 | 43 | 2A | 01 | 08 | 44 | 44 |
文章が255文字よりも多いことは十分に考えられるのでバイト数を増やすとか、位置の基準を現在処理中の文字にして何文字前から何文字という指定のしかたにするなどの工夫がある。似た文字のパターンは近くにあるだろうという予測である。
今の場合は14文字前なので次の様になる。
文字 | A | A | A | A | B | B | B | B | B | B | B | C | C | C | * | 14 | 8 | D | D |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
ASCII | 41 | 41 | 41 | 41 | 42 | 42 | 42 | 42 | 42 | 42 | 42 | 43 | 43 | 43 | 2A | 0E | 08 | 44 | 44 |
*を文字そのものとして使うためには工夫が必要となる。たとえば*0と0を続けて書くことにする。「0文字前から」は使うことのないからこれが出てきたら普通の文字のあつかいをすると決めておくのである。
たとえばランレングスで用いた24バイトの文字データで考え、各文字の出現回数を表にする。
AAAABBBBBBBCCCAAAABBBBDD
文字 | 出現回数 | コード | 出現回数×コード長 |
---|---|---|---|
B | 11 | 0 | 11 |
A | 8 | 10 | 16 |
C | 3 | 110 | 9 |
D | 2 | 111 | 6 |
計 | 24 | 42 |
多く出てくる文字に短いコードを割り当てる。コードはビット単位の可変長である。
このコードで書き出すと
101010100000000110110110101010100000111111
つまり全部で42ビットで済むことになる。
この場合、文字がABCDの4種類しかないので新たにこの文字のために固定長の文字コードをつくるとしたら1文字につき2ビット。24文字では48ビット必要になるので6ビット圧縮されたことになる。
2ビットの文字コードは、例えば次のようなもの
文字 | 出現回数 | コード | 出現回数×コード長 |
---|---|---|---|
A | 8 | 00 | 16 |
B | 11 | 01 | 22 |
C | 3 | 10 | 6 |
D | 2 | 11 | 4 |
計 | 24 | 48 |
もしこの24文字がASCIIコードで保存されるとしたら8×24=192ビット必要である。
文字 | 出現回数 | ASCIIコード | 出現回数×コード長 |
---|---|---|---|
A | 8 | 01000001 | 64 |
B | 11 | 01000010 | 88 |
C | 3 | 01000011 | 24 |
D | 2 | 01000200 | 16 |
計 | 24 | 192 |
ASCIIコードは標準規格で固定されているから文字コード表は不要だが、ハフマン法ではデータの出現頻度に合わせてデータごとに異なるコードを作るので、実際の使用ではコードと文字の対応表も記録しなければならない。したがってある程度長いデータでないと圧縮の効果が出ない。また、この対応表も短くする方法も考えられている。