ＣＧＩＦ：ＬＺＷ圧縮法１

ＬＺＷ圧縮法（ＬＺＷ辞書）

左の３×３のＧＩＦ画像がどのように圧縮されているか見てみましょう。
ＧＩＦファイルはカラーテーブルを持っていて、そのテーブルのインデックスを使って色を格納しています。
インデックス ０１・・・９ａ・・・ｆ・・・
色 BLACKMAROON REDLIME WHITE

ピクセルは左から右、上から下の順で
０ -> ｆ -> ｆ -> ｆ -> ｆ -> ｆ -> ｆ -> ｆ -> ｆ
上のように配置されます。

ａｂｃｄ９ｃａのようなデータ列がある時、
最後のデータを除いた部分（この場合ａｂｃｄ９ｃ）をｐｒｅｆｉｘ、
最後のデータ（この場合ａ）をｓｕｆｆｉｘと呼ぶことにします。

上で作成した「０ｆｆｆｆｆｆｆｆ」というようなデータを頭から順に見てゆき、長さが２以上の新しい順列が現れるたびに、新しいコード(0x102番から)を、その順列に割り当てていきます。
（１×１のＧＩＦファイルの時は、長さ２以上の順列を取り出すことができませんが、このときはprefixのないsuffixだけの新しいコードを割り当てます。）

具体的には、まず０ｆが新しい順列なので、この順列にコード0x102を割り当てます。
prefixが0x0、suffixが0xfとなります。

次に、前回取り出した順列のsuffixから、新しい順列を調べていきます。
すると、ｆｆが新しい順列として見つかりますので、この順列にコード0x103を割り当てます。
prefixが0xf、suffixが0xfとなります。

次はｆｆという順列はすでに登場しているので、ｆｆｆが新しい順列となります。
この順列にコード0x104を割り当て、prefixを0x103、suffixを0xfとします。
ここで、以前割り当てられたｆｆというデータ列のコードをprefixに使用することで、圧縮が起こりました。

次は、ｆｆｆの順列のコードもすでに割り当てられているので、ｆｆｆｆが新しい順列となります。
この順列にコード0x105を割り当て、prefixが0x104、suffixが0xfとなります。

最後は、ｆｆの順列にコード0x106を割り当て、prefixを0xf、suffixを0xfとします。

この様子を表に示すと、以下のようになります。
コードに割り当てられた内容 コード prefixの中身suffixの中身
カラーテーブルのindex 0x0
0x1
0x2
・
・
・
0xff
クリアコード 0x100
終了コード 0x101
新しく作成されたコード 0x1020x00xf
0x1030xf0xf
0x1040x1030xf
0x1050x1040xf
0x1060xf0xf

０ -> ｆ -> ｆ -> ｆ -> ｆ -> ｆ -> ｆ -> ｆ -> ｆ だったものを
prefixを登録した順に並べ、最後に登録したsuffixをその後部に付け足したものが、
０ -> ｆ -> １０３ -> １０４ -> ｆ -> ｆ のように圧縮できているのが分かります。
この圧縮は可逆圧縮です。

次は、prefix、suffixに登録されたコードをＧＩＦファイルの中でどのように格納しているかについて説明したいと思います。
ＴＯＰ ＬＺＷ圧縮について ＬＺＷ圧縮法２（イメージデータ） 戻る