画像を保存しようとしたとき、その保存形式に迷うことは少なくないと思います。それぞれのフォーマットがどのような圧縮技術を用いているのか、そしてその長所、短所を知っていれば、判断を下しやすくなります。ここでは画像の保存形式としてメジャーなGIF形式とJPEG形式について、そのアルゴリズムをできるだけ分かりやすく説明しようと思います。

　自分はプログラマでもなんでもないので、間違いや不正確な部分があるかもしれません(^^;。ここでの記述は参考程度にお考えください。また、もしそうした個所を見つけましたら、ぜひご教示ください。

　GIF形式は「Graphics Interchange Format」の略で、アメリカのパソコン通信ネットワーク「CompuServe」で提唱されたフォーマットです。65535×65535ドット、256色までの画像を扱うことができます。現在、GIFにはGIF87、GIF87a、GIF89aという３つのバージョンがあります。GIF87は通常の静止画像のみを、GIF87aは静止画像とインタレース表示（インタレースGIF）をサポートしています。GIF89aはこれに加えて透明色指定（透化GIF）とアニメーション（GIFアニメーション）を可能にしたものです。

　このフォーマットではデータの圧縮に「LZW(Lempel-Ziv Welch)圧縮法」という技術を使っています。これはごく大雑把に言えば、ある決まったデータ列に名前を割り当て、その名前だけを保存しようという方法です。

　例えば「ＹＹＹＹＹ」というデータを保存するときに、「ＹＹＹＹＹ」とそのまま保存するより「Ｙ５」という風に表したほうがデータ量が小さくて済みます。この方法を「ランレングス(Run length)圧縮法」といいますが、「LZW圧縮法」はこれをさらに巧妙に発展させたものです。

cf.
　「LZW圧縮法」はアメリカのUnisys社が特許を持っています。詳しくは「ＧＩＦの特許問題」をご参照下さい

　今、簡単のためにＡ，Ｂ，Ｃ，Ｄという４色からなる、以下のようなデータを考えます。

　ＡＢＡＢＡＢＡＢＢＢＡＢＡＢＡＡＣＤＡＣＤＡＤＣＡＢＡＡＡＢＡＢ.....

　このデータを頭から順に見てゆき、新しい順列が現れるたび、新しいコードをその順列に割り当てていくのです。ただし例外として、この場合０～５番までのコードは予約されます。０～３まではＡ，Ｂ，Ｃ，Ｄそれぞれの色が割り当てられます。また、４番はクリアコード、５番はエンドコードという特別のコードとなります。そこで、データの表記は６番以降のコードを用いて行います。

　さて、始める前に新しい言葉を導入します。「ＡＢＣＤ」というデータ列があった場合、最後のデータを除いた部分を「プレフィックスストリング（prefix string）」、最後のデータを「サフィックス（suffix）」と呼びます。この場合、プレフィックスストリングは「ＡＢＣ」、サフィックスは「Ｄ」ということになります。

　この「プレフィックスストリング」とか「サフィックス」という呼び方は、多分正式なものではありません（分からないけど）。でもこう呼ぶと分かりやすいので、ここでは便宜的にこれらの用語を使います。

　以上のことを頭においておいて、実際にやってみましょう。頭から見ていくと、最初に「ＡＢ」というデータの並びがあります。これに６番のコードを割り当てます。そして、このデータ列のプレフィックスストリングを記録します。この場合、プレフィックスストリングは「Ａ」、すなわちコード「０」です。

　そうしたら次は、今処理したデータ列（「ＡＢ」）のサフィックス（「Ｂ」）から読み始めます。すると「ＢＡ」というデータ列が出てきました。これに７番のコードを割り当てます。そしてこのデータ列のプレフィックスストリング「Ｂ」、すなわちコード「１」を記録します。

　どんどん進めていきましょう。続くデータを読んでいきます。「ＡＢＡ」という並びが出てきました。８番のコードを割り当てます。そしてこのデータ列のプレフィックスストリング「ＡＢ」、すなわちコード「６」を記録します。以下同様にして、コードをデータ列に割り当て、プレフィックスストリングを記録していきます。

　これを続けていくと、最終的に下の表のようになります。

色	コード	プレフィックス	サフィックス	データ列	出力
Ａ	０
Ｂ	１
Ｃ	２
Ｄ	３
Clear	４
End	５
Ａ		Ａ	Ａ		－
Ｂ	６	Ａ	Ｂ	ＡＢ	０
Ａ	７	Ｂ	Ａ	ＢＡ	１
Ｂ
Ａ	８	６	Ａ	ＡＢＡ	６
Ｂ
Ａ
Ｂ	９	８	Ｂ	ＡＢＡＢ	８
Ｂ	10	Ｂ	Ｂ	ＢＢ	１
Ｂ
Ａ	11	10	Ａ	ＢＢＡ	10
Ｂ
Ａ
Ｂ
Ａ	12	９	Ａ	ＡＢＡＢＡ	９
Ａ	13	Ａ	Ａ	ＡＡ	０
Ｃ	14	Ａ	Ｃ	ＡＣ	０
Ｄ	15	Ｃ	Ｄ	ＣＤ	２
Ａ	16	Ｄ	Ａ	ＤＡ	３
Ｃ
Ｄ	17	14	Ｄ	ＡＣＤ	14
Ａ
Ｄ	18	16	Ｄ	ＤＡＤ	16
Ｃ	19	Ｄ	Ｃ	ＤＣ	３
Ａ	20	Ｃ	Ａ	ＣＡ	２
Ｂ
Ａ
Ａ	21	８	Ａ	ＡＢＡＡ	８
Ａ
Ｂ	22	13	Ｂ	ＡＡＢ	13
Ａ
Ｂ	23	７	Ｂ	ＢＡＢ	７

　以上の操作によって、
　ＡＢＡＢＡＢＡＢＢＢＡＢＡＢＡＡＣＤＡＣＤＡＤＣＡＢＡＡＡＢＡＢ.....
というデータ列は
　０１６８１10９００２３1416４２８13７.....
というコード列に変換されます（分かりにくかったら、実際に紙と鉛筆使ってやってみてください。雰囲気がつかめると思います）。

　データ列の長さとコード列の長さを比べてみてください。短くなっています・・・ということは、データが圧縮されたということです。以上のような圧縮方式を考えれば、どのような画像がGIFに向いているのかはおのずと明らかです。

　GIFは、アニメの絵のように１つの色の面積が広かったり、規則的な図形が繰り返されるような絵で最大の圧縮効果を発揮します。

　逆に、違う色のドットが不規則に並んでいたりするような画像では、圧縮の効果が下がりファイルサイズが大きくなりがちです。また、写真などでは256色という色数の制限から、きれいに再現するのはなかなか難しいです。さらにこうした画像では256色以内に色数を押さえるために「減色」をしますが、このとききれいに再現しようとして誤差拡散法などを使うと、上記の理由でファイルサイズが大きくなってしまいます。

　さて、ここからはオマケですが、圧縮したままじゃ気持ち悪いという方もおられるかと思うので、次は圧縮されたデータを展開してみましょう。

　展開の仕方は一見難しそうですが、実はそれほどでもありません。展開するためには上に示したようなコードとデータ列との対照表を、コード列から復元する必要があります。０～５番までのコードは割当があらかじめ決まっていますから、復元する必要があるのは６番以降です。

　０１６８１10９００２３1416４２８13７.....

　まず、コード列の頭から順番にコードのペアを作っていきます。そして、できてきたペアのそれぞれから、６番以降のコードを順次求めることができます。今回の場合、最初のペアは（０１）です。すると、こうして作ったペアの左側のコードが６番のコードのプレフィックスストリングを、右側のコードの最初の１文字が６番のコードのサフィックスを表します。

　と、言葉で説明しても分かりにくいでしょうから、実際にやってみましょう。

　まず最初のペアは上記のように（０１）です。ですから、６番のコードのプレフィックスストリングは「Ａ」、サフィックスは「Ｂ」となります。つまり、６番のコードは「ＡＢ」を表します。

　次のペアは（１６）です。ここから、７番のコードのプレフィックスストリングは「Ｂ」。そしてサフィックスは「コード６番＝ＡＢ」の最初の１文字、 「Ａ」です。つまり、７番のコードは「ＢＡ」を表します。

　３番目のペアは（６８）です。よって８番のコードのプレフィックスストリングは「コード６番」すなわち「ＡＢ」です。そしてサフィックスは・・・といきたいところですが、これを埋めるためには今求めようとしているコード８番のプレフィックスストリングが必要です。おっと、８番のコードのプレフィックスストリングはたった今、求めたばかりでしたね。そう、「ＡＢ」です。ですから、コード８番のサフィックスは「ＡＢ］の最初の１文字「Ａ」となり、コード８番は「ＡＢＡ」というデータ列を表すことが分かります。

　後はもうこれを繰り返していくだけです。４番目のペアは（８１）ですから、コード９番のプレフィックスストリングは「コード８番＝ＡＢＡ 」、サフィックスはＢです。すなわち、コード９番は「ＡＢＡＢ」を表すということになります。

　これを続けていけば、すべてのコードについてデータ列を割り当てることができ、データを復元することができます。