2回続いて情報のやりとりの符号化についてみてきたが、情報を伝達する際には様々な 資源の有効活用のために圧縮という物も必要になる。
以前紹介したモールス信号をもう一度見てみよう。「トン」と「ツー」を・と−で表す と、
A ・− B −・・・ C −・−・ D −・・ E ・ F ・・−・ G −−・ H ・・・・ I ・・ J ・−−− K −・− L ・−・・ M −− N −・ O −−− P ・−−・ Q −−・− R ・−・ S ・・・ T − U ・・− V ・・・− W ・−− X −・・− Y −・−− Z −−・・
このような固定のコード化は圧縮効果が状況により変わってくるため、出現頻度を調べ てデータによりどのように符号化するかを変えることでどのようなデータであっても圧 縮効果が出せる必要がある。圧縮そのものは可逆圧縮と非可逆圧縮とあり、前者の場合 はデータの損失はなく、後者の場合は圧縮後のデータからは元の内容の一部が失われて しまう。
可逆圧縮または損失無し圧縮で有名なのはハフマン符号化で、出現頻度を調べて良く出 てくる物に短い符号を割り当て、出現頻度が低くなるに従い長い符号を割り当てて全体 のサイズを圧縮する。
例をあげると、簡略化のためにa,b,c,d,e,f,gの7文字だけで作成された文書があると し、その文書内でのそれぞれの文字の出現頻度が
a=0.20, b=0.10, c=0.30, d=0.05, e=0.10, f=0.20, g=0.05とすると、それぞれに割り当てられる符号はハフマン符号化法(アルゴリズムの説明は 省く)で符号化すると2進数で、
f:00 a:01 c:11 b:101 e:1001 d:10000 g:10001
のようになる。それぞれの符号の長さが可変長となるため、ビット列を先頭から見てい ったときに一意に判別できなくてはならないが、どの符号も他の符号の先頭の一部と同 じにならないように符号化されるため圧縮されたデータを復元するときにも元通りに復 号出来ることが保証される。この例では"abc"という文字列は"0110111"というビット列 に変換できる。このビット列を先頭からマッチする物を探していけば復号できるのがわ かると思う。
ところで、非可逆圧縮では情報が失われてしまうが、元のデータに戻せない圧縮に意味 はあるのだろうか。このタイプの圧縮はたとえば画像や音に対する圧縮でよく使われて おり、人間の感覚で感じにくい部分の情報を省くことでデータのサイズを大幅に圧縮す ることを可能にしている。音や画像に対しては離散コサイン変換:DCT(Discrete Cosine Transform )というものが使われるが、目や耳が良い人以外はその差になかなか気がつ かない。MP3などで使われる心理聴覚モデルとか圧縮技術もなかなか興味深いので、興 味がある方は調べてみてほしい。