5分でわかる(かもしれない)圧縮の基本
大規模データを日常的に扱う人にとって、データ圧縮は基本。絶対ないと困るわけではないけど、あると格段に世界が広がる。ドラクエで言うところのルカニみたいなもの。
でも圧縮というとデータをバイナリで持たないといけないとか、なんとなく面倒なので目を背けがち。そこで5分でわかるような感じで説明を書いておく。
基本的な圧縮の方法は差分圧縮というのがある。今回はこれを説明する。
char型のデータが8つ並んでいると考える。
6 3 2 1 7 5 4 8
とりあえずバイナリにしてみる。便宜上、縦に書く。
6 3 2 1 7 5 4 8
===============
1の位:0 1 0 1 1 1 0 0
2の位:1 1 1 0 1 0 0 0
4の位:1 0 0 0 1 1 1 0
8の位:0 0 0 0 0 0 0 1
16の位:0 0 0 0 0 0 0 0
32の位:0 0 0 0 0 0 0 0
64の位:0 0 0 0 0 0 0 0
128の位:0 0 0 0 0 0 0 0char型は8bitなので二進数で1の位から128の位まである。ここで下の方にすごい勢いで0が並んでいて無駄っぽい。消してしまいたい。つまり
6 3 2 1 7 5 4 8
===============
1の位:0 1 0 1 1 1 0 0
2の位:1 1 1 0 1 0 0 0
4の位:1 0 0 0 1 1 1 0
8の位:0 0 0 0 0 0 0 1
===============
4桁使ったよこうしたい。のでそうする。とりあえず4桁使ったよ、とメモっておけばOK。
char型より小さい型なんてないのにどうやってプログラミングするの？と思うかもしれない。実はこのためにchar型の変数を8個並べた。つまり、1の位の8bit分、2の位の8bit分・・・をそれぞれchar型で持てばよい。
すると同様に
0 3 2 1 2 2 0 1
===============
1の位:0 1 0 1 0 0 0 1
2の位:0 1 1 0 1 1 0 0
===============
2桁使ったよ 96 48 6 70 2 99 54 9
=======================
1の位: 0 0 0 0 0 1 0 1
2の位: 0 0 1 1 1 1 1 0
4の位: 0 0 1 1 0 0 1 0
8の位: 0 0 0 0 0 0 0 1
16の位: 0 1 0 0 0 0 1 0
32の位: 1 1 0 0 0 1 1 0
64の位: 1 0 0 1 0 1 0 0
=======================
7桁使ったよというのができる。見てわかる通り、大きな数が出てくるほど使う桁数が大きい。のでできるだけ小さい数で済ませたい。
そこで差分をとる。つまり
1 3 5 8 11 12 15 19
=======================
1の位: 1 1 1 0 1 0 1 1
2の位: 0 1 0 0 1 0 1 1
4の位: 0 0 1 0 0 1 1 0
8の位: 0 0 0 1 1 1 1 0
16の位: 0 0 0 0 0 0 0 1
=======================
5桁使ったよというデータがあったら
1 3 5 8 11 12 15 19 => 1 2 2 3 3 1 3 4
とすれば
1 2 2 3 3 1 3 4
=======================
1の位: 1 0 0 1 1 1 1 0
2の位: 0 1 1 1 1 0 1 0
4の位: 0 0 0 0 0 0 0 1
=======================
3桁使ったよとなる。5桁から3桁に減った。8個の数に5桁使えば、40bit、3桁なら24bitなので16bit分圧縮された。これが差分圧縮。簡単便利すばらしい。
