GIFの構造についてこれから何回かに分けて解説しましょう。
まず、最初は細かい構造とかは抜きにして、いきなりGIFがどうやって画像データを圧縮しているか、というところからはじめましょう。
GIFではLZWという圧縮方式で画像データが圧縮されています。
LZWで重要なのは「辞書」を理解することです。
辞書
LZWでは圧縮する際 「辞書」 という物を使います。この辞書は0P目から始まります。辞書には１Pに一つの単語しか登録できません。
辞書は圧縮を開始する前にいくつかの単語で初期化されています。例として、「100100100……」という1と0のみから構成された数列を圧縮する場合をここでは考えます。今回はでてくる数が0と1の二つなので、この二つを辞書に0P目から登録しておきます。順番はどうでも良いんですけどプログラム的には0Pに0 を、1P目に1を登録した方が分かりやすいですね。
辞書の初期化がすんだらまず、圧縮する数列（100100100……）の最初の二つの数を取り出します。
正式な名前は忘れてしまったので、一つ目を出力数、二つ目を待機数とでもここでは名付けておきます。（別にまぁ、細かいことは気にしない）
次に出力数と待機数を並べた数列が（今は １０ ）辞書に登録されているかどうか調べます。まだ辞書には0と１しか登録されてないので当然10は登録されていません。
登録されていない場合は辞書の新しいページにその値を登録します。今回は2p目に10を登録します。
そして、出力数を出力します。これで、最初のルーチンは終わりです。
次に出力数はもう処理し終わったので待機数を出力数に入れます。待機数には次の数字をいれます。（今回は０）
新しい出力数と待機数でも同様のことをし、これをくり返します。
その中で辞書に登録しようとすると、既に辞書に単語登録されている事があります。
その時は何も出力せずに、その数列が登録されているページ数を出力数に入れて、次に進みます。
分かりにくいと思うので一連の流れを書き並べてみました。
（左が出力数、右が待機数です）
ここまでの処理で出力された結果を並べると「10024……」となります。
一番最後まで行くと、必ず最後の数が余ってしまうので、その数を出力したら終わりです。
つまり、「10010010」を圧縮すると100240になるわけです。8文字から6文字に圧縮できました。
GIFでの圧縮方法
GIFでも理論はこれと同じように圧縮していますが、データ量を減らすためにもうちょっと複雑なことをしたり、特殊な数などが存在します。
GIFでは圧縮、展開するさいに作る辞書のページ数を最大で2の12乗（＝4096個）に制限しています。
辞書の登録数が4096個になると辞書を初期化した状態に戻します。
この時、初期化する合図として「クリアナンバー」という数が出力されます。（ただし、仕様書によると必ずしもクリアナンバーが出力される訳ではないらしい……）
その、クリアナンバーはLZWで普通に初期化した際、その次のページの数に相当します。
256色を扱うGIFだったらまず、0~255Pに0~255を登録しますので、256P目に256を辞書に登録しておきます。
さらに、終了コードという数も存在しています。これは、GIFの画像の圧縮が終わったら必ず出力される数で、クリアナンバーの次の数です。
256色扱うGIFだったら257P目に257を登録しておきます。
ですので、実際に辞書を初期化する際には、登録する色数＋２個分登録するわけですね。
このやり方で再び「10010010」を出力してみます。
まず、基本的に圧縮を開始するときに一番最初にクリアコードを出力しておきます。なお、クリアコードが出したら、辞書を初期化するので、クリアコードと待機数を辞書に登録する必要はありません
まずはクリアコードの2を出力します。
次に出力数に1を、待機数に０を入れて、10を辞書の４P目に登録し１を出力します。以下、繰り返し。
最後に終了コードの3を出力して終わります。
結果は「21004603」になります。短いから減ってないけどこれで、GIF風の圧縮完了となります
可変ビット
さて、Byte単位のお話から、bit単位のお話にここから変わります。
ちょっと話が難しくなるので、GIFがどうやって圧縮されてるのか知れたらな〜、てなぐらいの方なら回れ右をした方がよろしいかも知れません。
GIFではファイル容量を減らすために書き込みビット長が変わります。
範囲は3〜12bitです。
今までは1と0の二つの場合で考えていましたが、逆に説明が面倒になるので、色の数が256色の場合を考えます。
256色の場合は0〜257Pまで辞書を初期化します。
さて、一番最初にクリアコードの256を出力することになりますが、256を表すには最低何ビット必要でしょうか？
256は2進数で100000000ですので9bit必要です。
よって、最初は9bitの書き込み長からスタートします。
圧縮を勧めていくとそのうち辞書の登録数が512個に達します。さて、今まで9bitで出力してきましたが、ここから先も9bitで良いのでしょうか？
512は2進数で1000000000ですので、9bitでは512以上の数が出てきたとき対応できません。よって、辞書の登録数が512個になったら書き込みbit長を10bitに増やします。
同様に1024個に達したら11bitに、2048に達したら12bitに増やします。
4096個に達したら辞書を初期化するので再び9bitに戻ります。(この時クリアコードが発行されます。)
また、値を書き出すとき、その値はbyte単位では右端を詰めて、下位ビットから書き込まれます。書き込めなかった上位ビットは次のバイトに書き出します。
最後の値を書き込んで余ったビットは0で埋めます。
例として 255 0 255 0の数列を圧縮してみましょう。
圧縮結果は「256 255 0 258 257」になります。
これを書き込むとこうなります
よって、ファイルをバイナリエディタとかで開くと（要するに16進数に直すと）「00 FF 01 10 18 10」と表示されます。
これで、圧縮の説明はほとんど終わりましたが、最後に一つ注意しなくてはならないことがあります。
画像が2階調の時（つまり、白黒とかの時） 色の数は２色ですが、適当な2色を加えて4色扱いにします。
何故かというと辞書を初期化する際最初に登録する色が二色しかないとクリアコードと終了コードを書き込んだ時点で辞書の登録数は４。圧縮しはじめたときから、いきなり書き込み長を3bitに増やさなくてはなりません。その為、2色しか必要なくても、4色扱いにするのです。
お疲れ様です。ここまでついて来れた方はもうほとんどＧＩＦを自作することが出来るところまで来ました
あとは、細かい記述のルールだけです。
次画像ブロックの使用について
