LZW 圧縮アルゴリズム

gif を生成するクラスを自作するために、今回は LZW 圧縮アルゴリズムの勉強。

LZW アルゴリズムは辞書式圧縮であり、gif や tiff の圧縮に利用されています。

LZW アルゴリズムの概要

LZW 圧縮アルゴリズムは次の手順で実行されます。

 手順0: 文字(数字)列に現れる文字の種類の数だけ、それぞれ辞書に登録しておく。
 (文字列が 0~255 の範囲であれば、辞書は 256 ページになる)

 手順1: 先頭の一文字を読み込んで、変数 w に格納する。

 手順2: 次の文字を読み込んで、変数 k に格納する。

 手順3: 2つの変数 w と k をつなげた wk が、辞書に登録されていないかを確認する。

 [登録されていたら]

  → 手順4: wk を w に代入し、手順2 に戻って何度でも繰り返す。

 [登録されていなかったら]

  → 手順4: wk を辞書に登録し、w の辞書番号を出力する。

 手順5: 全ての読み込むが終わるまで、繰り返す。

私の解釈も入った文章となっており、若干間違っているかもしれません。
しかしながら、とにかく文章ではわかりづらいので、以下では実例を示していきます。
また、今回の内容は gif を作成するための学習であるため、解凍方法については触れないことにします。

LZW アルゴリズムの例 その1

ここでは 0, 1, 2, 3 の数字から成る列の圧縮を考えていきます。
例えば 「012321001」 や 「00011122333」 などです。

圧縮の前に、まず辞書の初期化が行われます。
0 ページ目には 0
1 ページ目には 1
2 ページ目には 2
3 ページ目には 3
を登録します。
圧縮の過程で新たに辞書を登録する場合は、4 ページ目からになります。

それでは、次の列を圧縮することを考えてみましょう。

|\ 0\ |\ 1\ |\ 0\ |\ 1\ |\ 0\ |\ 1\ |\ 0\ |\ 1\ |\ 0\ |

まず、先頭と 2 番目の |\ 0\ |\ 1\ | が辞書に登録されているかを確認します。
辞書に登録されていないので、|\ 0\ |\ 1\ | を 4 ページ目に辞書登録し、
|\ 0\ | を出力します。

次に、2 番目と 3 番目の |\ 1\ |\ 0\ | が辞書に登録されていないかを確認します。
辞書に登録されていないので、|\ 1\ |\ 0\ | を 5 ページ目に辞書登録し、
|\ 1\ | を出力します。

次に、3 番目と 4 番目の |\ 0\ |\ 1\ | が辞書に登録されているかを確認します。
4 ページ目に登録されているので、5 番目を含めた |\ 0\ |\ 1\ |\ 0\ | が辞書に登録されていないかを確認します。
これは辞書に登録されていないので、|\ 0\ |\ 1\ |\ 0\ | を 6 ページ目に辞書登録し、
|\ 4\ | を出力します。

次に、5 番目と 6 番目の |\ 0\ |\ 1\ | が辞書に登録されているかを確認します。
4 ページ目に登録されているので、7 番目を含めた |\ 0\ |\ 1\ |\ 0\ | が辞書に登録されていないかを確認します。
6 ページ目に登録されているので、8 番目を含めた |\ 0\ |\ 1\ |\ 0\ |\ 1\ | が辞書に登録されていないかを確認します。
これは辞書に登録されていないので、|\ 0\ |\ 1\ |\ 0\ |\ 1\ | を 7 ページ目に辞書登録し、
|\ 6\ | を出力します。

次に、8 番目と 9 番目の |\ 1\ |\ 0\ | が辞書に登録されていないかを確認します。
5 ページ目に登録されており、これで列は終了するので、
|\ 5\ | を出力します。

このようにして、はじめの数字の列は以下のように圧縮されます。

|\ 0\ |\ 1\ |\ 4\ |\ 6\ |\ 5\ |

他にも、LZW 圧縮を理解するのを手助けする簡単な例を示していきます。

LZW アルゴリズムの例 その2

先ほどと同様の条件で、次の数字の列を圧縮することを考えてみましょう。

|\ 0\ |\ 1\ |\ 2\ |\ 3\ |\ 0\ |\ 1\ |\ 2\ |\ 3\ |\ 0\ |\ 1\ |\ 2\ |

まず、先頭と 2 番目の |\ 0\ |\ 1\ | が辞書に登録されているかを確認します。
辞書に登録されていないので、|\ 0\ |\ 1\ | を 4 ページ目に辞書登録し、
|\ 0\ | を出力します。

次に、2 番目と 3 番目の |\ 1\ |\ 2\ | が辞書に登録されていないかを確認します。
辞書に登録されていないので、|\ 1\ |\ 2\ | を 5 ページ目に辞書登録し、
|\ 1\ | を出力します。

次に、3 番目と 4 番目の |\ 2\ |\ 3\ | が辞書に登録されていないかを確認します。
辞書に登録されていないので、|\ 2\ |\ 3\ | を 6 ページ目に辞書登録し、
|\ 2\ | を出力します。

次に、4 番目と 5 番目の |\ 3\ |\ 0\ | が辞書に登録されていないかを確認します。
辞書に登録されていないので、|\ 3\ |\ 0\ | を 7 ページ目に辞書登録し、
|\ 3\ | を出力します。

次に、5 番目と 6 番目の |\ 0\ |\ 1\ | が辞書に登録されているかを確認します。
4 ページ目に登録されているので、7 番目を含めた |\ 0\ |\ 1\ |\ 2\ | が辞書に登録されていないかを確認します。
これは辞書に登録されていないので、|\ 0\ |\ 1\ |\ 2\ | を 8 ページ目に辞書登録し、
|\ 4\ | を出力します。

次に、7 番目と 8 番目の |\ 2\ |\ 3\ | が辞書に登録されているかを確認します。
6 ページ目に登録されているので、9 番目を含めた |\ 2\ |\ 3\ |\ 0\ | が辞書に登録されていないかを確認します。
これは辞書に登録されていないので、|\ 2\ |\ 3\ |\ 0\ | を 9 ページ目に辞書登録し、
|\ 6\ | を出力します。

次に、9 番目と 10 番目の |\ 0\ |\ 1\ | が辞書に登録されているかを確認します。
4 ページ目に登録されているので、11 番目を含めた |\ 0\ |\ 1\ |\ 2\ | が辞書に登録されていないかを確認します。
8 ページ目に登録されており、これで列は終了するので
|\ 8\ | を出力します。

このようにして、はじめの数字の列は以下のように圧縮されます。

|\ 0\ |\ 1\ |\ 2\ |\ 3\ |\ 4\ |\ 6\ |\ 8\ |

私は実例がいくつか無いとなかなか理解・実装が進まない人間なので、
くどいようですがもう一つだけ例示しておきます。

LZW アルゴリズムの例 その3

先ほどと同様の条件で、次の数字の列を圧縮することを考えてみましょう。

|\ 0\ |\ 0\ |\ 0\ |\ 0\ |\ 1\ |\ 1\ |\ 1\ |\ 0\ |\ 0\ |\ 0\ |\ 0\ |

まず、先頭と 2 番目の |\ 0\ |\ 0\ | が辞書に登録されているかを確認します。
辞書に登録されていないので、|\ 0\ |\ 0\ | を 4 ページ目に辞書登録し、
|\ 0\ | を出力します。

次に、2 番目と 3 番目の |\ 0\ |\ 0\ | が辞書に登録されていないかを確認します。
4 ページ目に登録されているので、4 番目を含めた |\ 0\ |\ 0\ |\ 0\ | が辞書に登録されていないかを確認します。
これは辞書に登録されていないので、|\ 0\ |\ 0\ |\ 0\ | を 5 ページ目に辞書登録し、
|\ 4\ | を出力します。

次に、4 番目と 5 番目の |\ 0\ |\ 1\ | が辞書に登録されていないかを確認します。
辞書に登録されていないので、|\ 0\ |\ 1\ | を 6 ページ目に辞書登録し、
|\ 0\ | を出力します。

次に、5 番目と 6 番目の |\ 1\ |\ 1\ | が辞書に登録されていないかを確認します。
辞書に登録されていないので、|\ 1\ |\ 1\ | を 7 ページ目に辞書登録し、
|\ 1\ | を出力します。

次に、6 番目と 7 番目の |\ 1\ |\ 1\ | が辞書に登録されていないかを確認します。
7 ページ目に登録されているので、8 番目を含めた |\ 1\ |\ 1\ |\ 0\ | が辞書に登録されていないかを確認します。
これは辞書に登録されていないので、|\ 1\ |\ 1\ |\ 0\ | を 8 ページ目に辞書登録し、
|\ 7\ | を出力します。

次に、8 番目と 9 番目の |\ 0\ |\ 0\ | が辞書に登録されていないかを確認します。
4 ページ目に登録されているので、10 番目を含めた |\ 0\ |\ 0\ |\ 0\ | が辞書に登録されていないかを確認します。
5 ページ目に登録されているので、11 番目を含めた |\ 0\ |\ 0\ |\ 0\ |\ 0\ | が辞書に登録されていないかを確認します。
これは辞書に登録されていないので、|\ 0\ |\ 0\ |\ 0\ |\ 0\ | を 9 ページ目に辞書登録し、
|\ 5\ | を出力します。

最後に、残った |\ 0\ | を出力します。

このようにして、はじめの数字の列は以下のように圧縮されます。

|\ 0\ |\ 4\ |\ 0\ |\ 1\ |\ 7\ |\ 5\ |\ 0\ |

うーん・・わかりにくいかもしれませんが、こんな感じであっていると思います。
一応この考え方で、gif 画像出力のコードをなんとか書くことができました。
ただ、gif の出力には幾つか考えるべき要素が増えるため、なかなか大変でした。

次回は、gif の出力に必要な知識などを整理したいと思います。


参考にさせて頂いたサイト
・プログラムdeタマゴ – GIFフォーマット講座
http://d.hatena.ne.jp/nodamushi/20090531/1243775161
・M.Hiroi’s Home Page – Algorithms with Python – LZ78 符号 (LZW 符号)
http://www.geocities.jp/m_hiroi/light/pyalgo34.html
・烏賊と電脳のホームページ – プログラミング資料 – データ圧縮 – LZW圧縮
http://www.geocities.co.jp/NatureLand/2023/reference/Compression/lzw.html



コメントを残す

メールアドレスが公開されることはありません。

次のHTML タグと属性が使えます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">