TOP > カテゴリ > 数学・アルゴリズム >

LZW圧縮アルゴリズム[実践的なGIFファイルの作成]

LZ78を改良した辞書式圧縮である「LZW圧縮アルゴリズム」の解説です。主にLZWを使用して画像を圧縮してGIFファイルを作成する方法をご紹介します。

第一章「LZWのアルゴリズム」、第二章で「GIFファイルのフォーマット」。そして、第三章で実践的な「LZWを使用してGIFファイルを作成する」となります。

はじめに

LZWの圧縮アルゴリズムは難しくはありません。困難と思われる箇所はGIFファイルの生成におけるビット操作です。このビット操作には「ビット長の変化」(3bitから12bitまで可変)や「ビットの右詰」や「ビットからバイト単位に変換」がありますので、その時のビットの確認作業が大変です。

1.LZWのアルゴリズム

辞書の初期化

LZWの辞書サイズは3bit(8種類)から12bit(4096種類)までの可変長です。

LZW圧縮をする前には必ず「辞書を初期化」します。辞書を初期化するには最初に「辞書のサイズ」を決めます。圧縮対象の文字列(数字)が0-3の2bitの範囲(01230123...など)だと「2bit」に「+1bit」を加算して3bitの辞書サイズになります。

辞書のサイズが確定したら、次に圧縮対象の文字列の全ての種類を辞書に登録します。0-3の2bitの範囲だと辞書の0ページ目は「0」、1ページ目には「1」、2ページ目には「2」、3ページ目には「3」となります。4ページはクリアコードの「4」、5ページにエンドコードの「5」、6/7ページ目は未登録です。最終的に3bitの辞書は0-7の範囲となり8ページとなります。

[3bitの辞書] - 文字列が2bitの範囲(0-3) 2色/4色

辞書番号辞書内容備考
0ページ0
1ページ1
2ページ2
3ページ3
4ページ4クリアコード
5ページ5エンドコード
6ページ未登録
7ページ未登録

文字列が1bitの範囲(0-1)は仕様上、3bitの辞書で初期化します。

この辞書にLZW圧縮で発見された文字列を「エンドコード」の次のページ以降にどんどん追加していきます。そして、辞書のサイズが満タンになったら、1bit分の辞書のサイズを大きくします。最大で12bitとなります。

クリアコードとエンドコードは、LZW圧縮の開始に「クリアコード」を出力して圧縮の終わりに「エンドコード」を出力する為に必要なコードとなります。

また、辞書が12bitで満タンになった場合に「辞書を初期化」(最初の状態にクリア)します。その初期化の際にもクリアコードを出力します。※クリアコードはクリア符号と翻訳される場合もあります。

次は「4bitの辞書」と「5bitの辞書」、「9bitの辞書」のサンプルとなります。

[4bitの辞書] - 文字列が3bitの範囲(0-7) 8色

辞書番号辞書内容備考
0ページ0
1ページ1
2ページ2
3ページ3
4ページ4
5ページ5
6ページ6
7ページ7
8ページ8クリアコード
9ページ9エンドコード
10ページ未登録
11ページ未登録
12ページ未登録
13ページ未登録
14ページ未登録
15ページ未登録

[5bitの辞書] - 文字列が4bitの範囲(0-15) 16色

辞書番号辞書内容備考
0ページ0
1ページ1
2ページ2
... 省略 ...
14ページ14
15ページ15
16ページ16クリアコード
17ページ17エンドコード
18ページ18未登録
19ページ19未登録
... 省略 ...
30ページ未登録
31ページ未登録

[9bitの辞書] - 文字列が8bitの範囲(0-255) 256色

辞書番号辞書内容備考
0ページ0
1ページ1
2ページ2
... 省略 ...
254ページ254
255ページ255
256ページ256クリアコード
257ページ257エンドコード
258ページ未登録
259ページ未登録
... 省略 ...
510ページ未登録
511ページ未登録

圧縮アルゴリズムの流れ

順序内容
1クリアコードの出力
2圧縮対象の文字列(数字)から一文字を読み込みprefix変数に格納する
3次の一文字を読み込んでsuffix変数に格納する
4prefix変数 + suffix変数を連結した文字列をcom1変数に格納する。次にcom1の内容が辞書に登録されているかを確認をする
  [登録済]
5  次の一文字をsuffixに格納する。com1 + suffixを連結した文字列を
  com2変数に格納する。次にcom2が辞書に登録されているかを確認をする
     [登録済]
6     com2をcom1に格納して5に戻る
     [未登録]
7     com2を辞書に登録する。com1の辞書番号を出力する。
     prefixにsuffixを格納して3に戻る
  [未登録]
  com1を辞書に登録して、prefixの辞書番号を出力する。
  suffixをprefixに格納して3に戻る
8全ての文字列を圧縮した後にエンドコードを出力する

※文字列の終端の扱いは次のサンプルで確認して下さい。
※辞書のページ数が4096になると辞書を初期化する必要があります。

いきなりプログラムみたいな文章になりましたね。このような文章だとプログラムのコードを提示した方が早いですが、この記事を見てる方は自力で圧縮をしたい方だと思いますので今回はコードは提示しませんのでご了承ください。

2017/3/4 追記:オープンソースでGIF.jsを公開しました。

サンプル 1

10010010 を圧縮すると「4, 1, 0, 0, 6, 8, 0, 5」となります。

[解説]

順序内容
1文字列が0と1しかありませんので「3bitの辞書」で初期化する。
2クリアコードの「4」を出力する。
31と0を連結した文字列「10」が辞書に登録されていないので6ページ目の辞書に登録する。「1」を出力する。
40と0を連結した文字列「00」が辞書に登録されていないので7ページ目の辞書に登録する。「0」を出力する。
50と1を連結した文字列「01」が辞書に登録されていないので8ページ目の辞書に登録する。「0」を出力する。
61と0を連結した文字列「10」が辞書に登録されているので、10と0を連結して100とする。 この100は辞書に登録されていないので9ページ目の辞書に登録する。10の辞書番号の「6」を出力する。
70と1を連結した文字列「01」が辞書に登録されているので、01と0を連結して010とする。 この010は辞書に登録されていないので10ページ目の辞書に登録する。01の辞書番号の「8」を出力する。
8文字列の終端の0の辞書番号の「0」を出力する。
9エンドコードの「5」を出力する

[辞書]

辞書番号辞書内容備考
0ページ0
1ページ1
2ページ2
3ページ3
4ページ4クリアコード
5ページ5エンドコード
6ページ10LZWで登録されたページ
7ページ00LZWで登録されたページ
8ページ01LZWで登録されたページ
9ページ100LZWで登録されたページ
10ページ010LZWで登録されたページ

サンプル 2

010101010 を圧縮すると「4, 0, 1, 6, 8, 7, 5」となります。

[解説]

順序内容
1文字列が0と1しかありませんので「3bitの辞書」で初期化する。
2クリアコードの「4」を出力する。
30と1を連結した文字列「01」が辞書に登録されていないので6ページ目の辞書に登録する。「0」を出力する。
41と0を連結した文字列「10」が辞書に登録されていないので7ページ目の辞書に登録する。「1」を出力する。
50と1を連結した文字列「01」が辞書に登録されているので、01と0を連結して010とする。 この010は辞書に登録されていないので8ページ目の辞書に登録する。01の辞書番号の「6」を出力する。
60と1を連結した文字列「01」が辞書に登録されているので、01と0を連結して010とする。 この010は辞書に登録されているので、010と0を連結して0101とする。 この0101は辞書に登録されていないので9ページ目の辞書に登録する。010の辞書番号の「8」を出力する。
71と0を連結した文字列「10」が辞書に登録されているので、10の辞書番号の「7」を出力する。
8エンドコードの「5」を出力する

[辞書]

辞書番号辞書内容備考
0ページ0
1ページ1
2ページ2
3ページ3
4ページ4クリアコード
5ページ5エンドコード
6ページ01LZWで登録されたページ
7ページ10LZWで登録されたページ
8ページ010LZWで登録されたページ
9ページ0101LZWで登録されたページ

サンプル 3

00001110000 を圧縮すると「4, 0, 6, 0, 1, 9, 7, 0, 5」となります。

[解説]

順序内容
1文字列が0と1しかありませんので「3bitの辞書」で初期化する。
2クリアコードの「4」を出力する。
30と0を連結した文字列「00」が辞書に登録されていないので6ページ目の辞書に登録する。「0」を出力する。
40と0を連結した文字列「00」が辞書に登録されているので、00と0を連結して000とする。 この000は辞書に登録されていないので7ページ目の辞書に登録する。00の辞書番号の「6」を出力する。
50と1を連結した文字列「01」が辞書に登録されていないので8ページ目の辞書に登録する。「0」を出力する。
61と1を連結した文字列「11」が辞書に登録されていないので9ページ目の辞書に登録する。「1」を出力する。
71と1を連結した文字列「11」が辞書に登録されているので、11と0を連結して110とする。 この110は辞書に登録されていないので10ページ目の辞書に登録する。11の辞書番号の「9」を出力する。
80と0を連結した文字列「00」が辞書に登録されているので、00と0を連結して000とする。 この000は辞書に登録されているので、000と0を連結して0000とする。 この0000は辞書に登録されていないので11ページ目の辞書に登録する。000の辞書番号の「7」を出力する。
9文字列の終端の0の辞書番号の「0」を出力する。
10エンドコードの「5」を出力する

[辞書]

辞書番号辞書内容備考
0ページ0
1ページ1
2ページ2
3ページ3
4ページ4クリアコード
5ページ5エンドコード
6ページ00LZWで登録されたページ
7ページ000LZWで登録されたページ
8ページ01LZWで登録されたページ
9ページ11LZWで登録されたページ
10ページ110LZWで登録されたページ
11ページ0000LZWで登録されたページ

ビット長

LZWには圧縮した値のビットの長さがあります。ビット長は辞書の登録数と連動して3bitから12bitまで自動的に増加していきます。ビット長が増えるタイミングは辞書が登録されて満タンになった「次のコード」から1bit増えます。

次は3つのサンプルのビット長になります。

元の文字列LZW圧縮ビット長
100100104, 1, 0, 0, 6, 8, 0, 53, 3, 3, 3, 4, 4, 4, 4
0101010104, 0, 1, 6, 8, 7, 53, 3, 3, 3, 4, 4, 4
000011100004, 0, 6, 0, 1, 9, 7, 0, 53, 3, 3, 3, 4, 4, 4, 4, 4

圧縮データの保存

LZWの圧縮データはビット長のサイズを元に全てbit単位にします。次にbyte単位にするのですが、そのときはbitを「右詰」で埋めていきます。

画像ファイルの変換

画像ファイルをGIFファイルに変換する際には画像をあらかじめ256色以下に減色して、その画像の左から右、上から下の1ピクセル毎のパレットインデックスを取得してそのデータをLZWで圧縮します。

2.GIFファイルのフォーマット

GIFファイルの色数は「2色/4色/8色/16色/32色/64色/128色/256色」でサイズは「1x1」から「65535x65335」となります。

※名称や用語は私の独自の名前になってる箇所があります。

全体図

名称バイト数備考
GIF Header13byte
(共通パレット)可変省略可能
Block可変複数のBlockを設定可能
Trailer1byte

2.1 GIF Header(13byte)

名称バイト数内容
シグネチャ3byteGIF(0x47 0x49 0x46)
バージョン3byteGIF87a : 0x38 0x37 0x61 アニメサポート
GIF89a : 0x38 0x39 0x61 アニメ/透過色サポート
画像の横幅2byte
画像の縦幅2byte
共通パレット1bit0:存在しない 1:存在する
1画素のビット数3bit値:0-7
共通パレットのパレット数と同じ値が多い。

※ここの値はあまり重要ではない。常に0(000)や7(111)の場合がある。仕様書には「この値はオリジナル・パレットの豊富さを表すように設定されるべきです。」と記載されている。
共通パレットのソートフラグ1bit0:未ソート 1:ソート済み(色の重要度順に整列)
共通パレットのパレット数3bit0-7
0:2色/1:4色/2:8色/3:16色/4:32色/5:64色/6:128色/7:256色
背景色の共通パレットインデックス1byte今回は0で良い。
ここの背景色はGIF Headerで定義されているイメージサイズとImage Dataブロックで定義されているイメージサイズが異なる場合のみ有効となります。(背景色は余白の色)
ピクセルの縦横比1byte0:比率情報なし 1-255:この値をNとして(N+15)/64と縦横比が算出される。
※常に0で良い

「共通パレット」「1画素のビット数」「共通パレットのソートフラグ」「共通パレットのパレット数」はこの順番で左詰にして1byteにします。

「1画素のビット数」の値が3の場合は「+1」されて実際は4bitとなります。「共通パレットのパレット数」の値が3の場合は「+1」されて4bitとなり、「2^4」で16色となります。また、「1画素のビット数」と「共通パレットのパレット数」は同じ値になる事が多いです。

2.2 共通パレット

GIF Headerの「共通パレット」が「1」の場合に存在する。

色はRGB順に並び「2^(共通パレットのパレット数 + 1)」個格納される。「共通パレットのパレット数」が0の場合は2色で「RGBRGB」の6byteのパレットが書き込まれます。

2.3 Block

Blockには「画像ブロック」と「拡張ブロック」がありますが、今回はシンプルなGIFファイルを作成しますので画像ブロックのみを解説します。

[画像ブロック]
Image Data (0x2c)

[拡張ブロック]
・Graphic Control Extension (0x21,0xf9) 透過色など
・Comment Extension (0x21,0xfe) 画像のコメントを設定
・Plain Text Extension (0x21,0x01) テキストデータの設定(未使用に近い)
・Application Extension (0x21,0xff) アプリ独自の情報を設定

<Image Data(0x2c)の全体図>

名称バイト数備考
Image Data Header10byte
(固有パレット)可変省略可能
LZW最小コードサイズ1byte
Blocks
・Block Size(1byte)
・Image Data(可変)
※このブロックは繰り返し
可変
Block Terminator1byte

<Image Data Header (10byte)>

名称バイト数内容
固定値1byte常に0x2C
画像のLeft位置2byte今回は0で良い
画像のTop位置2byte今回は0で良い
画像の横幅2byte
画像の縦幅2byte
固有パレット1bit0:存在しない 1:存在する
インタレース1bit0:なし 1:あり
固有パレットのソートフラグ1bit0:未ソート 1:ソート済み(色の重要度順に整列)
予約2bit未使用
固有パレットのパレット数3bit0-7

ビットの扱いなどはGIF Headerと同様です。

<固有パレット>
共有パレットと同様

<LZW最小コードサイズ>
最初の辞書サイズの事で「LZW圧縮の最小ビット数」と呼ばれます。(2-8)

基本的にGIF Headerの「1画素のビット数」に「+1」を加算した値と同じになる。また、LZWのアルゴリズムの仕様上、2色の場合は「1」ではなく値を 「2」と設定する。

実際のbit数はGIF Headerの「1画素のビット数」や「共通パレットのパレット数」のようにこの値に「+1」を加算したbit数となる。

なので、2色の場合は3bit(2)の辞書となる。2色の場合が2bit(1)だと「0、1、クリアコード、エンドコード」の4種類になっていきなり辞書が満タンになるので、それを回避する為です。

<Blocks>

名称バイト数内容
Block Size1byteImage Dataのサイズ
Image Data可変LZW圧縮した画像データ

LZWで圧縮したデータを全て書き込む為には繰り返し出力します。

<Block Terminator>
常に0

2.4 Trailer

ファイルの終端で常に「0x3b」となる。

3.LZWを使用してGIFファイルを作成する

いよいよ、GIFファイルの生成に突入します。

LZWとGIFファイルのフォーマットはもう解説済みですので、サンプルを提示したいと思います。このサンプルデータがあるとなしでは、作業効率が全然違うと思います。

3x3 2色 白黒

3x3で2色の白黒のGIFファイルです。

種類画像備考
3x3ダウンロードはこちら
拡大3x3のGIFファイルをペイントで拡大したものです
 

GIFファイルをバイナリエディタで開くとこうなります。

元のピクセルデータ(パレットインデックス)

0,0,0,1,0,1,1,0,1

圧縮後のデータ

4,0,6,1,0,1,8,1,5

圧縮データのビット長

3,3,3,3,4,4,4,4,4

後は圧縮データをビットに変換して右詰にして出力するだけです。

3x3 2色 カラフル

3x3で2色のカラフルのGIFファイルです。

種類画像備考
3x3ダウンロードはこちら
拡大3x3のGIFファイルをペイントで拡大したものです
 

GIFファイルをバイナリエディタで開くとこうなります。

元のピクセルデータ(パレットインデックス)

0,1,0,1,0,1,0,1,0

圧縮後のデータ

4,0,1,6,8,7,5

圧縮データのビット長

3,3,3,3,4,4,4

メモ

サンプルのGIFファイルは「画像の減色」のページで作成できます。

クリアコードは仕様書によるとGIFエンコーダーの好きな時点で出力可能です。
ですが、今回、解説した箇所にクリアコードを出力しないと、生成したGIFファイルを読み込めないアプリがありますので注意してください。

以上となります。長時間、お疲れ様でした。

仕様書

GIF87a仕様書 (英語)
GIF89a仕様書 (英語)
GIF89a仕様書 (日本語) ※リンク切れ

参考リンク

GIFフォーマットの詳細
LZW 圧縮アルゴリズムの概要
LZW 圧縮アルゴリズム
画像データの圧縮(LZWについて)





関連記事



公開日:2016年03月12日 最終更新日:2017年03月04日
記事NO:01830