Rails + Vue.jsで作るSPAのブログシステム (管理画面)
ホーム(SPA)
記事
画像
カテゴリ
編集 - 記事
カテゴリ
選択して下さい。
プログラミング
Windows
政治・経済・生活
タイトル
キーワード(keywords)
※半角カンマで区切る
解説(description)
本文
※HTMLで記述する
<h1>LZW圧縮アルゴリズム[実践的なGIFファイルの作成]</h1> <style> table{ margin: 0 8px 0 12px; border: 1px solid #1e90ff; border-collapse: collapse; } table th{ padding:5px; font-size:14px; border: 1px solid #1e90ff; background:#f0f8ff; } table td{ padding:5px; font-size:14px; border:1px solid silver; } </style> <p>LZWで画像を圧縮してGIFファイルを作成する方法をご紹介します。</p> <h2>目次</h2> <p> 1. LZWのアルゴリズム<br /> 2. GIFファイルのフォーマット<br /> 3. LZWを使用してGIFファイルを作成する<br /> </p> <p></p> <h2>はじめに</h2> <p>LZWの圧縮アルゴリズムは難しくはありません。困難と思われる箇所はGIFファイルの生成におけるビット操作です。このビット操作には「ビット長の変化」(3bitから12bitまで可変)や「ビットの右詰」や「ビットからバイト単位に変換」がありますので、その時の<span style="color:red;">ビットの確認作業</span>が大変です。</p> <a name="contents1" id="contents1"></a> <h2>1. LZWのアルゴリズム</h2> <p></p> <h3>1-1. 辞書の初期化</h3> <p>LZWの辞書サイズは3bit(8種類)から12bit(4096種類)までの可変長です。</p> <p>LZW圧縮をする前には必ず「辞書を初期化」します。辞書を初期化するには最初に「辞書のサイズ」を決めます。圧縮対象の文字列(数字)が0-3の2bitの範囲(01230123...など)だと「2bit」に<span style="color:red;">「+1bit」</span>を加算して3bitの辞書サイズになります。</p> <p>辞書のサイズが確定したら、次に圧縮対象の文字列の全ての種類を辞書に登録します。0-3の2bitの範囲だと辞書の0ページ目は「0」、1ページ目には「1」、2ページ目には「2」、3ページ目には「3」となります。4ページはクリアコードの「4」、5ページにエンドコードの「5」、6/7ページ目は未登録です。最終的に3bitの辞書は0-7の範囲となり8ページとなります。</p> <p>[3bitの辞書] - 文字列が2bitの範囲(0-3) 2色/4色</p> <table> <tr><th>辞書番号</th><th>辞書内容</th><th>備考</th></tr> <tr><td>0ページ</td><td>0</td><td></td></tr> <tr><td>1ページ</td><td>1</td><td></td></tr> <tr><td>2ページ</td><td>2</td><td></td></tr> <tr><td>3ページ</td><td>3</td><td></td></tr> <tr><td>4ページ</td><td>4</td><td>クリアコード</td></tr> <tr><td>5ページ</td><td>5</td><td>エンドコード</td></tr> <tr><td>6ページ</td><td></td><td>未登録</td></tr> <tr><td>7ページ</td><td></td><td>未登録</td></tr> </table> <p></p> <div class="box">文字列が1bitの範囲(0-1)は仕様上、<span style="color:red;">3bitの辞書</span>で初期化します。</div> <p></p> <p>この辞書にLZW圧縮で発見された文字列を「エンドコード」の次のページ以降にどんどん追加していきます。そして、辞書のサイズが満タンになったら、1bit分の辞書のサイズを大きくします。最大で12bitとなります。</p> <p>クリアコードとエンドコードは、LZW圧縮の開始に「クリアコード」を出力して圧縮の終わりに「エンドコード」を出力する為に必要なコードとなります。</p> <p>また、辞書が12bitで満タンになった場合に「辞書を初期化」(最初の状態にクリア)します。その初期化の際にもクリアコードを出力します。※クリアコードはクリア符号と翻訳される場合もあります。</p> <p>次は「4bitの辞書」と「5bitの辞書」、「9bitの辞書」のサンプルとなります。</p> <p>[4bitの辞書] - 文字列が3bitの範囲(0-7) 8色</p> <table> <tr><th>辞書番号</th><th>辞書内容</th><th>備考</th></tr> <tr><td>0ページ</td><td>0</td><td></td></tr> <tr><td>1ページ</td><td>1</td><td></td></tr> <tr><td>2ページ</td><td>2</td><td></td></tr> <tr><td>3ページ</td><td>3</td><td></td></tr> <tr><td>4ページ</td><td>4</td><td></td></tr> <tr><td>5ページ</td><td>5</td><td></td></tr> <tr><td>6ページ</td><td>6</td><td></td></tr> <tr><td>7ページ</td><td>7</td><td></td></tr> <tr><td>8ページ</td><td>8</td><td>クリアコード</td></tr> <tr><td>9ページ</td><td>9</td><td>エンドコード</td></tr> <tr><td>10ページ</td><td></td><td>未登録</td></tr> <tr><td>11ページ</td><td></td><td>未登録</td></tr> <tr><td>12ページ</td><td></td><td>未登録</td></tr> <tr><td>13ページ</td><td></td><td>未登録</td></tr> <tr><td>14ページ</td><td></td><td>未登録</td></tr> <tr><td>15ページ</td><td></td><td>未登録</td></tr> </table> <p></p> <p>[5bitの辞書] - 文字列が4bitの範囲(0-15) 16色</p> <table> <tr><th>辞書番号</th><th>辞書内容</th><th>備考</th></tr> <tr><td>0ページ</td><td>0</td><td></td></tr> <tr><td>1ページ</td><td>1</td><td></td></tr> <tr><td>2ページ</td><td>2</td><td></td></tr> <tr><td>... 省略 ...</td><td></td><td></td></tr> <tr><td>14ページ</td><td>14</td><td></td></tr> <tr><td>15ページ</td><td>15</td><td></td></tr> <tr><td>16ページ</td><td>16</td><td>クリアコード</td></tr> <tr><td>17ページ</td><td>17</td><td>エンドコード</td></tr> <tr><td>18ページ</td><td>18</td><td>未登録</td></tr> <tr><td>19ページ</td><td>19</td><td>未登録</td></tr> <tr><td>... 省略 ...</td><td></td><td></td></tr> <tr><td>30ページ</td><td></td><td>未登録</td></tr> <tr><td>31ページ</td><td></td><td>未登録</td></tr> </table> <p></p> <p>[9bitの辞書] - 文字列が8bitの範囲(0-255) 256色</p> <table> <tr><th>辞書番号</th><th>辞書内容</th><th>備考</th></tr> <tr><td>0ページ</td><td>0</td><td></td></tr> <tr><td>1ページ</td><td>1</td><td></td></tr> <tr><td>2ページ</td><td>2</td><td></td></tr> <tr><td>... 省略 ...</td><td></td><td></td></tr> <tr><td>254ページ</td><td>254</td><td></td></tr> <tr><td>255ページ</td><td>255</td><td></td></tr> <tr><td>256ページ</td><td>256</td><td>クリアコード</td></tr> <tr><td>257ページ</td><td>257</td><td>エンドコード</td></tr> <tr><td>258ページ</td><td></td><td>未登録</td></tr> <tr><td>259ページ</td><td></td><td>未登録</td></tr> <tr><td>... 省略 ...</td><td></td><td></td></tr> <tr><td>510ページ</td><td></td><td>未登録</td></tr> <tr><td>511ページ</td><td></td><td>未登録</td></tr> </table> <p></p> <h3>1-2. 圧縮アルゴリズムの流れ</h3> <p></p> <table> <tr><th style="width:30px;">順序</th><th>内容</th></tr> <tr><td>1</td><td><span style="color:green;">クリアコードの出力</span></td></tr> <tr><td>2</td><td>圧縮対象の文字列(数字)から一文字を読み込みprefix変数に格納する</td></tr> <tr><td><span style="color:red;">3</span></td><td>次の一文字を読み込んでsuffix変数に格納する</td></tr> <tr><td>4</td><td>prefix変数 + suffix変数を連結した文字列をcom1変数に格納する。次にcom1の内容が辞書に登録されているかを確認をする</td></tr> <tr><td></td><td> [登録済]</td></tr> <tr><td><span style="color:red;">5</span></td><td> 次の一文字をsuffixに格納する。com1 + suffixを連結した文字列を<br /> com2変数に格納する。次にcom2が辞書に登録されているかを確認をする</td></tr> <tr><td></td><td> [登録済]</td></tr> <tr><td>6</td><td> com2をcom1に格納して<span style="color:red;">5に戻る</span></td></tr> <tr><td></td><td> [未登録] </td></tr> <tr><td>7</td><td> com2を<span style="color:blue;">辞書に登録</span>する。com1の<span style="color:green;">辞書番号を出力</span>する。<br /> prefixにsuffixを格納して<span style="color:red;">3に戻る</span></td></tr> <tr><td></td><td> [未登録]</td></tr> <tr><td></td><td> com1を<span style="color:blue;">辞書に登録</span>して、prefixの<span style="color:green;">辞書番号を出力</span>する。<br /> suffixをprefixに格納して<span style="color:red;">3に戻る</span></td></tr> <tr><td>8</td><td>全ての文字列を圧縮した後に<span style="color:green;">エンドコードを出力</span>する</td></tr> </table> <p></p> <div class="box"> ※文字列の終端の扱いは次のサンプルで確認して下さい。<br /> ※辞書のページ数が4096になると辞書を初期化する必要があります。</div> <p>いきなりプログラムみたいな文章になりましたね。このような文章だとプログラムのコードを提示した方が早いですが、この記事を見てる方は自力で圧縮をしたい方だと思いますので今回はコードは提示しませんのでご了承ください。</p> <p>2017/3/4 追記:オープンソースで<a href="https://github.com/TakeshiOkamoto/GIF.js">GIF.js</a>を公開しました。</p> <h3>1-3. サンプル 1</h3> <p><span style="font-size:18px;">10010010</span> を圧縮すると「4, 1, 0, 0, 6, 8, 0, 5」となります。</p> <p><span style="font-weight:bold;">[解説]</span></p> <table> <tr><th style="width:30px;">順序</th><th>内容</th></tr> <tr><td>1</td><td>文字列が0と1しかありませんので「3bitの辞書」で初期化する。</td></tr> <tr><td>2</td><td>クリアコードの<span style="color:green;">「4」を出力</span>する。</td></tr> <tr><td>3</td><td>1と0を連結した文字列「10」が辞書に登録されていないので<span style="color:blue;">6ページ目の辞書に登録</span>する。<span style="color:green;">「1」を出力</span>する。</td></tr> <tr><td>4</td><td>0と0を連結した文字列「00」が辞書に登録されていないので<span style="color:blue;">7ページ目の辞書に登録</span>する。<span style="color:green;">「0」を出力</span>する。</td></tr> <tr><td>5</td><td>0と1を連結した文字列「01」が辞書に登録されていないので<span style="color:blue;">8ページ目の辞書に登録</span>する。<span style="color:green;">「0」を出力</span>する。</td></tr> <tr><td>6</td><td>1と0を連結した文字列「10」が辞書に登録されているので、10と0を連結して100とする。 この100は辞書に登録されていないので<span style="color:blue;">9ページ目の辞書に登録</span>する。10の辞書番号の<span style="color:green;">「6」を出力</span>する。 </td></tr> <tr><td>7</td><td>0と1を連結した文字列「01」が辞書に登録されているので、01と0を連結して010とする。 この010は辞書に登録されていないので<span style="color:blue;">10ページ目の辞書に登録</span>する。01の辞書番号の<span style="color:green;">「8」を出力</span>する。</td></tr> <tr><td>8</td><td><span style="color:red;">文字列の終端</span>の0の辞書番号の<span style="color:green;">「0」を出力</span>する。</td></tr> <tr><td>9</td><td>エンドコードの<span style="color:green;">「5」を出力</span>する</td></tr> </table> <p></p> <p><span style="font-weight:bold;">[辞書]</span></p> <table> <tr><th>辞書番号</th><th>辞書内容</th><th>備考</th></tr> <tr><td>0ページ</td><td>0</td><td></td></tr> <tr><td>1ページ</td><td>1</td><td></td></tr> <tr><td>2ページ</td><td>2</td><td></td></tr> <tr><td>3ページ</td><td>3</td><td></td></tr> <tr><td>4ページ</td><td>4</td><td>クリアコード</td></tr> <tr><td>5ページ</td><td>5</td><td>エンドコード</td></tr> <tr><td>6ページ</td><td>10</td><td>LZWで登録されたページ</td></tr> <tr><td>7ページ</td><td>00</td><td>LZWで登録されたページ</td></tr> <tr><td>8ページ</td><td>01</td><td>LZWで登録されたページ</td></tr> <tr><td>9ページ</td><td>100</td><td>LZWで登録されたページ</td></tr> <tr><td>10ページ</td><td>010</td><td>LZWで登録されたページ</td></tr> </table> <p></p> <h3>1-4. サンプル 2</h3> <p><span style="font-size:18px;">010101010</span> を圧縮すると「4, 0, 1, 6, 8, 7, 5」となります。</p> <p><span style="font-weight:bold;">[解説]</span></p> <table> <tr><th style="width:30px;">順序</th><th>内容</th></tr> <tr><td>1</td><td>文字列が0と1しかありませんので「3bitの辞書」で初期化する。</td></tr> <tr><td>2</td><td>クリアコードの<span style="color:green;">「4」を出力</span>する。</td></tr> <tr><td>3</td><td>0と1を連結した文字列「01」が辞書に登録されていないので<span style="color:blue;">6ページ目の辞書に登録</span>する。<span style="color:green;">「0」を出力</span>する。</td></tr> <tr><td>4</td><td>1と0を連結した文字列「10」が辞書に登録されていないので<span style="color:blue;">7ページ目の辞書に登録</span>する。<span style="color:green;">「1」を出力</span>する。</td></tr> <tr><td>5</td><td>0と1を連結した文字列「01」が辞書に登録されているので、01と0を連結して010とする。 この010は辞書に登録されていないので<span style="color:blue;">8ページ目の辞書に登録</span>する。01の辞書番号の<span style="color:green;">「6」を出力</span>する。 </td></tr> <tr><td>6</td><td>0と1を連結した文字列「01」が辞書に登録されているので、01と0を連結して010とする。 この010は辞書に登録されているので、010と0を連結して0101とする。 この0101は辞書に登録されていないので<span style="color:blue;">9ページ目の辞書に登録</span>する。010の辞書番号の<span style="color:green;">「8」を出力</span>する。 </td></tr> <tr><td>7</td><td>1と0を連結した文字列「10」が辞書に登録されているので、10の辞書番号の<span style="color:green;">「7」を出力</span>する。</td></tr> <tr><td>8</td><td>エンドコードの<span style="color:green;">「5」を出力</span>する</td></tr> </table> <p></p> <p><span style="font-weight:bold;">[辞書]</span></p> <table> <tr><th>辞書番号</th><th>辞書内容</th><th>備考</th></tr> <tr><td>0ページ</td><td>0</td><td></td></tr> <tr><td>1ページ</td><td>1</td><td></td></tr> <tr><td>2ページ</td><td>2</td><td></td></tr> <tr><td>3ページ</td><td>3</td><td></td></tr> <tr><td>4ページ</td><td>4</td><td>クリアコード</td></tr> <tr><td>5ページ</td><td>5</td><td>エンドコード</td></tr> <tr><td>6ページ</td><td>01</td><td>LZWで登録されたページ</td></tr> <tr><td>7ページ</td><td>10</td><td>LZWで登録されたページ</td></tr> <tr><td>8ページ</td><td>010</td><td>LZWで登録されたページ</td></tr> <tr><td>9ページ</td><td>0101</td><td>LZWで登録されたページ</td></tr> </table> <p></p> <h3>1-5. サンプル 3</h3> <p><span style="font-size:18px;">00001110000</span> を圧縮すると「4, 0, 6, 0, 1, 9, 7, 0, 5」となります。</p> <p><span style="font-weight:bold;">[解説]</span></p> <table> <tr><th style="width:30px;">順序</th><th>内容</th></tr> <tr><td>1</td><td>文字列が0と1しかありませんので「3bitの辞書」で初期化する。</td></tr> <tr><td>2</td><td>クリアコードの<span style="color:green;">「4」を出力</span>する。</td></tr> <tr><td>3</td><td>0と0を連結した文字列「00」が辞書に登録されていないので<span style="color:blue;">6ページ目の辞書に登録</span>する。<span style="color:green;">「0」を出力</span>する。</td></tr> <tr><td>4</td><td>0と0を連結した文字列「00」が辞書に登録されているので、00と0を連結して000とする。 この000は辞書に登録されていないので<span style="color:blue;">7ページ目の辞書に登録</span>する。00の辞書番号の<span style="color:green;">「6」を出力</span>する。 </td></tr> <tr><td>5</td><td>0と1を連結した文字列「01」が辞書に登録されていないので<span style="color:blue;">8ページ目の辞書に登録</span>する。<span style="color:green;">「0」を出力</span>する。</td></tr> <tr><td>6</td><td>1と1を連結した文字列「11」が辞書に登録されていないので<span style="color:blue;">9ページ目の辞書に登録</span>する。<span style="color:green;">「1」を出力</span>する。</td></tr> <tr><td>7</td><td>1と1を連結した文字列「11」が辞書に登録されているので、11と0を連結して110とする。 この110は辞書に登録されていないので<span style="color:blue;">10ページ目の辞書に登録</span>する。11の辞書番号の<span style="color:green;">「9」を出力</span>する。 </td></tr> <tr><td>8</td><td>0と0を連結した文字列「00」が辞書に登録されているので、00と0を連結して000とする。 この000は辞書に登録されているので、000と0を連結して0000とする。 この0000は辞書に登録されていないので<span style="color:blue;">11ページ目の辞書に登録</span>する。000の辞書番号の<span style="color:green;">「7」を出力</span>する。 </td></tr> <tr><td>9</td><td><span style="color:red;">文字列の終端</span>の0の辞書番号の<span style="color:green;">「0」を出力</span>する。</td></tr> <tr><td>10</td><td>エンドコードの<span style="color:green;">「5」を出力</span>する</td></tr> </table> <p></p> <p><span style="font-weight:bold;">[辞書]</span></p> <table> <tr><th>辞書番号</th><th>辞書内容</th><th>備考</th></tr> <tr><td>0ページ</td><td>0</td><td></td></tr> <tr><td>1ページ</td><td>1</td><td></td></tr> <tr><td>2ページ</td><td>2</td><td></td></tr> <tr><td>3ページ</td><td>3</td><td></td></tr> <tr><td>4ページ</td><td>4</td><td>クリアコード</td></tr> <tr><td>5ページ</td><td>5</td><td>エンドコード</td></tr> <tr><td>6ページ</td><td>00</td><td>LZWで登録されたページ</td></tr> <tr><td>7ページ</td><td>000</td><td>LZWで登録されたページ</td></tr> <tr><td>8ページ</td><td>01</td><td>LZWで登録されたページ</td></tr> <tr><td>9ページ</td><td>11</td><td>LZWで登録されたページ</td></tr> <tr><td>10ページ</td><td>110</td><td>LZWで登録されたページ</td></tr> <tr><td>11ページ</td><td>0000</td><td>LZWで登録されたページ</td></tr> </table> <p></p> <h3>1-6. ビット長</h3> <p>LZWには圧縮した値のビットの長さがあります。ビット長は辞書の登録数と連動して3bitから12bitまで自動的に増加していきます。ビット長が増えるタイミングは辞書が登録されて満タンになった<span style="color:red;">「次のコード」</span>から1bit増えます。</p> <p>次は3つのサンプルのビット長になります。</p> <table> <tr><th>元の文字列</th><th>LZW圧縮</th><th>ビット長</th></tr> <tr><td>10010010</td><td>4, 1, 0, 0, 6, 8, 0, 5</td><td>3, 3, 3, 3, 4, 4, 4, 4</td></tr> <tr><td>010101010</td><td>4, 0, 1, 6, 8, 7, 5</td><td>3, 3, 3, 3, 4, 4, 4</td></tr> <tr><td>00001110000</td><td>4, 0, 6, 0, 1, 9, 7, 0, 5</td><td>3, 3, 3, 3, 4, 4, 4, 4, 4</td></tr> </table> <p></p> <h3>1-7. 圧縮データの保存</h3> <p>LZWの圧縮データはビット長のサイズを元に全てbit単位にします。次にbyte単位にするのですが、そのときはbitを<span style="color:red;">「右詰」</span>で埋めていきます。</p> <h3>1-8. 画像ファイルの変換</h3> <p>画像ファイルをGIFファイルに変換する際には画像をあらかじめ256色以下に減色して、その画像の左から右、上から下の1ピクセル毎のパレットインデックスを取得してそのデータをLZWで圧縮します。</p> <a name="contents2" id="contents2"></a> <h2>2. GIFファイルのフォーマット</h2> <p>GIFファイルの色数は「2色/4色/8色/16色/32色/64色/128色/256色」でサイズは「1x1」から「65535x65335」となります。</p> <p>※名称や用語は私の独自の名前になってる箇所があります。</p> <h3>2-1. 全体図</h3> <p></p> <table> <tr><th>名称</th><th>バイト数</th><th>備考</th></tr> <tr><td>GIF Header</td><td>13byte</td><td></td></tr> <tr><td>(共通パレット)</td><td>可変</td><td>省略可能</td></tr> <tr><td>Block</td><td>可変</td><td>複数のBlockを設定可能</td></tr> <tr><td>Trailer</td><td>1byte</td><td></td></tr> </table> <p></p> <h3>2-2. GIF Header(13byte)</h3> <p></p> <table> <tr><th>名称</th><th>バイト数</th><th>内容</th></tr> <tr><td>シグネチャ</td><td>3byte</td><td>GIF(0x47 0x49 0x46)</td></tr> <tr><td>バージョン</td><td>3byte</td><td>GIF87a : 0x38 0x37 0x61 アニメサポート<br />GIF89a : 0x38 0x39 0x61 アニメ/透過色サポート </td></tr> <tr><td>画像の横幅</td><td>2byte</td><td></td></tr> <tr><td>画像の縦幅</td><td>2byte</td><td></td></tr> <tr><td>共通パレット</td><td><span style="color:red;">1bit</span></td><td>0:存在しない 1:存在する</td></tr> <tr><td>1画素のビット数</td><td><span style="color:red;">3bit</span></td><td>値:0-7<br />共通パレットのパレット数と同じ値が多い。<br /><br />※ここの値はあまり重要ではない。常に0(000)や7(111)の場合がある。仕様書には「この値はオリジナル・パレットの豊富さを表すように設定されるべきです。」と記載されている。</td></tr> <tr><td>共通パレットのソートフラグ</td><td><span style="color:red;">1bit</span></td><td>0:未ソート 1:ソート済み(色の重要度順に整列)</td></tr> <tr><td>共通パレットのパレット数</td><td><span style="color:red;">3bit</span></td><td>0-7<br />0:2色/1:4色/2:8色/3:16色/4:32色/5:64色/6:128色/7:256色</td></tr> <tr><td>背景色の共通パレットインデックス</td><td>1byte</td><td>今回は0で良い。<br />ここの背景色はGIF Headerで定義されているイメージサイズとImage Dataブロックで定義されているイメージサイズが異なる場合のみ有効となります。(背景色は余白の色)</td></tr> <tr><td>ピクセルの縦横比</td><td>1byte</td><td>0:比率情報なし 1-255:この値をNとして(N+15)/64と縦横比が算出される。<br />※常に0で良い</td></tr> </table> <p>「共通パレット」「1画素のビット数」「共通パレットのソートフラグ」「共通パレットのパレット数」はこの順番で<span style="color:red;">左詰</span>にして1byteにします。 </p> <p>「1画素のビット数」の値が3の場合は「+1」されて実際は4bitとなります。「共通パレットのパレット数」の値が3の場合は「+1」されて4bitとなり、「2^4」で16色となります。また、「1画素のビット数」と「共通パレットのパレット数」は同じ値になる事が多いです。</p> <h3>2-3. 共通パレット</h3> <p>GIF Headerの「共通パレット」が「1」の場合に存在する。</p> <p>色はRGB順に並び「2^(共通パレットのパレット数 + 1)」個格納される。「共通パレットのパレット数」が0の場合は2色で「RGBRGB」の6byteのパレットが書き込まれます。</p> <h3>2-4. Block</h3> <p>Blockには「画像ブロック」と「拡張ブロック」がありますが、今回はシンプルなGIFファイルを作成しますので画像ブロックのみを解説します。</p>
表示
|
戻る
SPA blog system
Takeshi Okamoto wrote the code.