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


コメント

  1. 王 飛 より:

    TIFF のLZW圧縮アルゴリズムについて勉強中のものです。この資料を読ませていただいて有難うございました。たいへん勉強になりました。
    LZW圧縮/解凍の練習として、Photoshopを使い、横10x縦1pxの空白画像(画素値=FFh)を作って、LZWで保存したデータを机上で解凍して、元の画像になるかを確認したら、理解できない問題がありました。たいへん申し訳ないですが、ご教授いただければ有り難いです。
    【問題点の纏め】
    photoshop画像:10x1px 画素値=ffh (グレースケールの白)
    圧縮しない場合の保存データ:ffh ffh ffh ffh ffh ffh…10バイト
    LZW圧縮データ:80h 3fh c0h 10h 38h 24h 12h 02h (8バイト)
    机上解凍:
     ①上記LZW圧縮データを9bitに直した後の10進数データ
      256(クリア) 255 0 259 260 260 257(終了)
     ②上記①のLZWデータ解凍すると、次の結果になります。
      255 0 0 0 0 0 0 0 0 0 (10バイト)
      ※前記圧縮しない場合の保存データと異なってしまいます。

    お手数をかけてすみません。よろしくお願いいたします。

タイトルとURLをコピーしました