データの圧縮

１．基本的な考え方

　（参考）データ圧縮とは若干異なりますが、通信に使われるモールス符号も同様の考え方に基づいています。英文でよく使われるE,Tなどには短い符号が使われ、あまり使用されない文字には長い符号が割り当てられているため、効率のよい通信が可能になっています。

２．具体的な例

1. 次のような文字列データを圧縮すると考えます。
   
   　　FADACFADADGCACFDBABA
   
   
2. まず文字の現れる確率を求めます。
   

   文字	出現回数	出現確率
   A	7	0.35
   B	2	0.10
   C	3	0.15
   D	4	0.20
   F	3	0.15
   G	1	0.05

   
   
3. 現れる確率の大きな順に並べ替えます。
   

   文字	出現回数	出現確率
   A	7	0.35
   D	4	0.20
   C	3	0.15
   F	3	0.15
   B	2	0.10
   G	1	0.05

   
   
4. 現れる確率の大きなものには短い符号、小さなものには長い符号を割り当てます。ここでは0,1からなる２進数の符号を割り当てます。ここで割り当てる符号は、特に区切りの記号を入れなくても、先頭から順に見ていくだけで必ず一意に決まるように工夫されています。
   

   文字	出現回数	出現確率	符号
   A	7	0.35	11
   D	4	0.20	01
   C	3	0.15	00
   F	3	0.15	101
   B	2	0.10	1001
   G	1	0.05	1000

   
   
5. 上記の符号割り当て表に基づいて元データを圧縮します
   
   　　FADACFADADGCACFDBABA
   　　→1011101110010111011101100000110010101100111100111
   
   ふつう計算機では英文字１文字8bit(bitとは２進数の一桁のことです)で表しますので、元データは20文字×8bit=160bit使用します。圧縮後は合計49bitになりました。従って、元データの約30%まで圧縮することができました。
   
   
6. 圧縮データを元に戻すときは、上記の逆の手順を行えば元データが完全に復元されます。
   
   　　1011101110010111011101100000110010101100111100111
   　　→101 11 01 11 00 101 11 01 11 01 1000 00 11 00 101 01 1001 11 1001 11
   　　　（先頭から順番に見て符号の区切りを見つけます）
   　　→FADACFADADGCACFDBABA
   　　　（符号対応表をもちいて元の文字に戻します。）
   

３．実際に利用されている手法

　上記で述べた基本的な考え方の手法は、D.A.Huffmanにより考案されたHuffman符号化法と呼ばれるもので、理論上最短の符号化を実現できるものとして知られていますが、あらかじめ元データをすべて調べて出現確率を求めて対応表を作る必要があり、実用上効率がよいとはいえません。また、実際のデータでは英語１文字＝8bit単位での圧縮ではそれほど効率よく圧縮できるとは限りません。

　現在広く用いられている方法には、A.LempelおよびJ.Zivによって考案されたLZ法、およびそれをT.Welchが改良したLZW法に基づくものが多いようです。
　たとえば日本で広く用いられている圧縮ソフトウエアLHaは、吉崎栄泰氏がLZ法のあるバリエーションを参考にしてさらに改良されたものです。
　また、F.KatzによってLZ法の変形として開発されたZIPアルゴリズムは、Windows、およびUNIX(GNU zip)などで広く使用されています。

　なお、LZW法は特許(Unisysが有している)の問題があり、たとえばこれを利用している画像圧縮フォーマットのGIF(Graphics Interchange Format)という形式がありますが、近年GIFを利用する際にはUnisysがライセンス料金を要求するようになったため画像処理のフリーソフトウエアではGIFが利用できなくなっています。

画像の圧縮（その１）に進む
もどる

参考文献

• 瀧　保夫、情報論I、岩波書店、1978
  (ISBN 4-00-021236-2)