情報の圧縮

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 −−・・ 

となる。ダッシュ(−)はドット(・)の三倍の長さの信号を送るので、−は・の3倍の時 間が必要となる。このためEの送信が一番時間がかからず、続いてI、S、Tとなる。 なぜこのような符号化になっているかというと、英文のアルファベットの出現頻度を調 べ効率よく送信できる=短い時間でより多くの情報を送ることが出来るように工夫した 結果だ。すべての文字の送信に要する時間を同じにするよりも良く出てくる文字に短い 信号を、あまり出てこない物ほど長い信号を割り当てることで、送信者の入力を楽にし、 送信時間を短縮することが出来た。 このモールス信号は、特定の分野の英文を元にしていたため、新聞の文章だとか、口語 の場合などではアルファベットの出現頻度も変わってくるし、なにより同じアルファベ ットを利用する他の言語では逆効果の場合もありえる。これは固定でコードを割り当て る以上仕方がないだろう。

このような固定のコード化は圧縮効果が状況により変わってくるため、出現頻度を調べ てデータによりどのように符号化するかを変えることでどのようなデータであっても圧 縮効果が出せる必要がある。圧縮そのものは可逆圧縮と非可逆圧縮とあり、前者の場合 はデータの損失はなく、後者の場合は圧縮後のデータからは元の内容の一部が失われて しまう。

可逆圧縮または損失無し圧縮で有名なのはハフマン符号化で、出現頻度を調べて良く出 てくる物に短い符号を割り当て、出現頻度が低くなるに従い長い符号を割り当てて全体 のサイズを圧縮する。

例をあげると、簡略化のために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などで使われる心理聴覚モデルとか圧縮技術もなかなか興味深いので、興 味がある方は調べてみてほしい。


前へ| 次へ
コンピュータの部屋
トップページ