>LZW圧縮アルゴリズム[実践的なGIFファイルの作成]LZWで画像を圧縮してGIFファイルを作成する方法をご紹介します。LZWを使用してGIFファイルを作成するはじめにLZWの圧縮アルゴリズムは難しくはありません。困難と思われる箇所はGIFファイルの生成におけるビット操作です。このビット操作には「ビット長の変化」(3bitから12bitまで可変)や「ビットの右詰」や「ビットからバイト単位に変換」がありますので、その時のビットの確認作業が大変です。辞書の初期化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ページとなります。文字列が1bitの範囲(0-1)は仕様上、3bitの辞書で初期化します。この辞書にLZW圧縮で発見された文字列を「エンドコード」の次のページ以降にどんどん追加していきます。辞書のサイズが満タンになったら、1bit分の辞書のサイズを大きくします。最大で12bitとなります。クリアコードとエンドコードは、LZW圧縮の開始に「クリアコード」を出力して圧縮の終わりに「エンドコード」を出力する為に必要なコードとなります。辞書が12bitで満タンになった場合に「辞書を初期化」(最初の状態にクリア)します。その初期化の際にもクリアコードを出力します。※クリアコードはクリア符号と翻訳される場合もあります。次は「4bitの辞書」と「5bitの辞書」、「9bitの辞書」のサンプルとなります。suffix変数を連結した文字列をcom1変数に格納する。次の一文字をsuffixに格納する。suffixを連結した文字列をcom2変数に格納する。com2を辞書に登録する。com1の辞書番号を出力する。prefixにsuffixを格納して3に戻る[未登録]com1を辞書に登録して、prefixの辞書番号を出力する。全ての文字列を圧縮した後にエンドコードを出力する※文字列の終端の扱いは次のサンプルで確認して下さい。※辞書のページ数が4096になると辞書を初期化する必要があります。プログラムみたいな文章になりましたね。このような文章だとプログラムのコードを提示した方が早いですが、この記事を見てる方は自力で圧縮をしたい方だと思いますので今回はコードは提示しませんのでご了承ください。追記:オープンソースでGIF.jsを公開しました。文字列が0と1しかありませんので「3bitの辞書」で初期化する。クリアコードの「4」を出力する。1と0を連結した文字列「10」が辞書に登録されていないので6ページ目の辞書に登録する。0と0を連結した文字列「00」が辞書に登録されていないので7ページ目の辞書に登録する。0と1を連結した文字列「01」が辞書に登録されていないので8ページ目の辞書に登録する。1と0を連結した文字列「10」が辞書に登録されているので、10と0を連結して100とする。この100は辞書に登録されていないので9ページ目の辞書に登録する。10の辞書番号の「6」を出力する。0と1を連結した文字列「01」が辞書に登録されているので、01と0を連結して010とする。この010は辞書に登録されていないので10ページ目の辞書に登録する。01の辞書番号の「8」を出力する。文字列の終端の0の辞書番号の「0」を出力する。文字列が0と1しかありませんので「3bitの辞書」で初期化する。クリアコードの「4」を出力する。0と1を連結した文字列「01」が辞書に登録されていないので6ページ目の辞書に登録する。1と0を連結した文字列「10」が辞書に登録されていないので7ページ目の辞書に登録する。0と1を連結した文字列「01」が辞書に登録されているので、01と0を連結して010とする。この010は辞書に登録されていないので8ページ目の辞書に登録する。01の辞書番号の「6」を出力する。0と1を連結した文字列「01」が辞書に登録されているので、01と0を連結して010とする。この010は辞書に登録されているので、010と0を連結して0101とする。この0101は辞書に登録されていないので9ページ目の辞書に登録する。010の辞書番号の「8」を出力する。1と0を連結した文字列「10」が辞書に登録されているので、10の辞書番号の「7」を出力する。文字列が0と1しかありませんので「3bitの辞書」で初期化する。クリアコードの「4」を出力する。0と0を連結した文字列「00」が辞書に登録されていないので6ページ目の辞書に登録する。0と0を連結した文字列「00」が辞書に登録されているので、00と0を連結して000とする。この000は辞書に登録されていないので7ページ目の辞書に登録する。00の辞書番号の「6」を出力する。0と1を連結した文字列「01」が辞書に登録されていないので8ページ目の辞書に登録する。1と1を連結した文字列「11」が辞書に登録されていないので9ページ目の辞書に登録する。1と1を連結した文字列「11」が辞書に登録されているので、11と0を連結して110とする。この110は辞書に登録されていないので10ページ目の辞書に登録する。11の辞書番号の「9」を出力する。0と0を連結した文字列「00」が辞書に登録されているので、00と0を連結して000とする。この000は辞書に登録されているので、000と0を連結して0000とする。この0000は辞書に登録されていないので11ページ目の辞書に登録する。000の辞書番号の「7」を出力する。文字列の終端の0の辞書番号の「0」を出力する。ビット長LZWには圧縮した値のビットの長さがあります。ビット長は辞書の登録数と連動して3bitから12bitまで自動的に増加していきます。ビット長が増えるタイミングは辞書が登録されて満タンになった「次のコード」から1bit増えます。次は3つのサンプルのビット長になります。圧縮データの保存LZWの圧縮データはビット長のサイズを元に全てbit単位にします。次にbyte単位にするのですが、そのときはbitを「右詰」で埋めていきます。画像ファイルをGIFファイルに変換する際には画像をあらかじめ256色以下に減色して、その画像の左から右、上から下の1ピクセル毎のパレットインデックスを取得してそのデータをLZWで圧縮します。GIFファイルのフォーマットGIFファイルの色数は「2色/4色/8色/16色/32色/64色/128色/256色」でサイズは「1x1」から「65535x65335」となります。※名称や用語は私の独自の名前になってる箇所があります。値:0-7共通パレットのパレット数と同じ値が多い。※ここの値はあまり重要ではない。常に0(000)や7(111)の場合がある。仕様書には「この値はオリジナル・パレットの豊富さを表すように設定されるべきです。