gif を生成するクラスを自作するために、今回は LZW 圧縮アルゴリズムの勉強。
LZW アルゴリズムは辞書式圧縮であり、gif や tiff の圧縮に利用されています。
LZW 圧縮アルゴリズムは次の手順で実行されます。
手順0: 文字（数字）列に現れる文字の種類の数だけ、それぞれ辞書に登録しておく。
（文字列が 0～255 の範囲であれば、辞書は 256 ページになる）
手順1: 先頭の一文字を読み込んで、変数 w に格納する。
手順2: 次の文字を読み込んで、変数 k に格納する。
手順3: 2つの変数 w と k をつなげた wk が、辞書に登録されていないかを確認する。
[登録されていたら]
→ 手順4: wk を w に代入し、手順2 に戻って何度でも繰り返す。
[登録されていなかったら]
→ 手順4: wk を辞書に登録し、w の辞書番号を出力する。
手順5: 全ての読み込むが終わるまで、繰り返す。
私の解釈も入った文章となっており、若干間違っているかもしれません。
しかしながら、とにかく文章ではわかりづらいので、以下では実例を示していきます。
また、今回の内容は gif を作成するための学習であるため、解凍方法については触れないことにします。
ここでは 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 圧縮を理解するのを手助けする簡単な例を示していきます。
先ほどと同様の条件で、次の数字の列を圧縮することを考えてみましょう。
$$|\ 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\ |$$
私は実例がいくつか無いとなかなか理解・実装が進まない人間なので、
くどいようですがもう一つだけ例示しておきます。
先ほどと同様の条件で、次の数字の列を圧縮することを考えてみましょう。
$$|\ 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
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バイト)
※前記圧縮しない場合の保存データと異なってしまいます。
お手数をかけてすみません。よろしくお願いいたします。