ロスレスGIF再圧縮と全探索
Lossless GIF recompression via exhaustive search (blog.arusekk.pl)
要約
この記事は、GIF画像のロスレス再圧縮について探求しています。GIFが古いブラウザの互換性確保に依然として重要である一方、その圧縮効率が低いことが問題とされています。筆者は、LZW圧縮の全探索アプローチ(ZopfliPNGに触発された)を提案し、既存ツールのflexiGIFの限界を指摘しながら、自身の遅いながらもより最適化されたZGIFの概念を紹介しています。
全文翻訳
Lossless GIF recompression via exhaustive search
少しの歴史
GIFは、広く普及した最も古い画像フォーマットです。今日では、主に画像ファイルでアニメーションを可能にすることで有名ですが、私はその用途にはあまり興味がありません。
実際、NCSA Mosaicがサポートした唯一の画像フォーマットがこれだったことが判明しています。もし、古いブラウザを真にサポートしたいのであれば、ウェブサイトはすべての重要な画像に対してGIFのフォールバックを用意する必要があります。私が言っているのは、古いChromiumのようなものではありません。実際のMosaic、Netscape、IE、Netsurf、Dillo、Konquerorのような、oldweb.todayで試せるようなものです。(おそらく、それらをサポートすることには興味がないでしょうが、これは楽しい演習です。)
私は1-Click Linuxのウェブサイトが、最も古いブラウザでも許容できる見た目になるようにしたかったので、<picture>要素を使用し、GIFをフォールバックにすることにしました。私は、各モダンウェブ機能は、本番環境で使用される場合、それ自体で合理的に広く互換性があるべきであり、その後、絶対的な1000%の互換性を持つフォールバックを1つだけ持つべきだと信じています。
問題
問題は、GIFの圧縮率が印象的ではないことです。正直に言って、2026年現在、画像フォーマットはSVGとWebP(写真にはロスレス、小さなパレットの描画/ロゴにはロスレス)を使用すべきでしょう。PNGでもJPEGでもなく、ましてやAI、DWG、その他のプロプライエタリフォーマット(DICOMのことですよ)など論外です。まあ、少なくともウェブ上では(名前の通り、WebPです)。
部分的な解決策は、小さな画像を使用することです。真に古いデバイスは、240x320のNokia携帯電話のような、非常に小さな画面サイズを持っています。そのため、アイコンやロゴのフォールバックは128x128で安全ですが、256x256は画面に収まらない可能性すらあります。
もっと良くできるでしょうか? はい。画像最適化には分野全体が捧げられており、それはメタデータの削除から始まります。次に、パレットから未使用の色を削除し、次にパレットから使用頻度の低い色を削除し、といった具合です。
しかし、上記のどのステップも、実際の圧縮自体には言及していません!
ZopfliPNG
私はzopflipngについて聞きました。PNGはDEFLATEを使用しています。これはZIPやGZIPで知られる圧縮フォーマットです。これはLZ77とハフマンコーディングのバリアントです。このフォーマットでは、他の多くの圧縮フォーマットでも一般的ですが、全く同じ非圧縮データを表現するための多くの異なる方法が存在します。
DEFLATEは、妥当な圧縮入力を生成するアルゴリズムの名前でもあり、より良い圧縮を達成するために、より多くの時間を圧縮に費やすように調整することができます(同じデータに対して、覚えておいてください)。しかし、DEFLATEアルゴリズムでは生成されない、構文的に有効なDEFLATEストリームは数多く存在します。これは面白いことです。ZIPファイルが自分自身を含むように作成できるという事実もありますが、とにかく、それらの中には最大の「圧縮レベル」よりも優れたものもあります。
Zopfliは、与えられた非圧縮入力を表現するために実際に最小のビット数を見つけるために、すべての構文的に有効なストリームにわたる網羅的な探索を実行するソフトウェアです。ZopfliPNGは、PNG用にそれを実行し、PNGピクセルエンコーディングも探索するバリアントです。ここで注意が必要です。なぜなら、任意のフォーマットに対する実際の最適な圧縮を見つけることは、停止性問題(あなたの圧縮フォーマットがチューリング完全に近い場合はどうなるか?)を解決することと同等になりうるからです。しかし、今日私たちが話している圧縮フォーマットは、探索が常に停止することを保証する、いくつかの有用な不変量を持っています。
ZopfliGIF?
ZopfliGIFはありませんが、flexiGIFというものがあります。これはほぼ同じことを行います。明らかに素晴らしいツールであり、すべてのGIFにそれを使用すべきです。しかし、GIFは非常に異なる圧縮スキーム、LZWを使用しています。そして、私はそのREADMEで、元のアルゴリズムよりも大きなファイルを残す可能性があるという、当惑するような記述を見つけました。これは非常に疑わしいものでした。そこで私は探求に乗り出しました。「それは一人の人間によって作られた - だから私もそれを理解できるだろう」と考えました。
LZW
当時のすべての論文のように、元の説明はアルゴリズムを中心にデータフォーマットを構築することを主張していたため、理解するのが少し難しいと感じました。しかし、私たち、数十年後の人々にとっては、データフォーマットの方がアルゴリズムよりも興味深いのは当然です。フォーマットを変更するには、デコーダーソフトウェアを変更する必要があります。フォーマットを維持し、エンコーダーソフトウェアを変更すれば、同じデコーダーを使い続けることができます。互換性です。
時間を節約するために、それを説明しましょう。圧縮ストリームはアクションで構成されており、それぞれが「このバイトを生成する」と言うか、以前のアクションの名前を指定して「この操作をすべてやり直すが、その後、それに続くアクションの最初のバイトも追加する」と言います。(最後の選択肢のエッジケースはうまく機能し、論文ではKwKwKと呼ばれています。)(GIFには「データ終了」アクションと「状態をゼロにする」アクションもありますが、これは関連性がありません。)
シンプルですよね? まあ、少なくとも私にはそう聞こえます。圧縮擬似コード9行と、対応する解凍擬似コード9行を読むことから始めるよりずっとシンプルです。
その後、アルゴリズムは、すべて以前のアクションを見て、続くものに最も長く一致するものを選択する、という貪欲なアプローチとして単純に表現できます。これは二重に合理的です。なぜなら、(a)局所的に最良であるものは、少なくとも大局的に最良である可能性があり、(b)それは常に「語彙」に新しい「単語」を追加するからです。
時間を節約するために、圧縮の例ストリームを以下に示します。
a b a b a b a a b a a b a a a b
可能な分割方法の1つ(貪欲な方法)は次のとおりです。
a b a-b a-b-a a-b-a-a b-a a a-b
1. aと言う。(abと言う方法はない。このアクションを再生するとabと言うだろう)
2. bと言う。(baと言う方法はない。このアクションを再生するとbaと言うだろう)
3. アクション1を再生する。(abと言う。abaと言う方法はない。これを再生するとabaと言うだろう)
4. アクション3を再生する。(abaと言う。abaaと言う方法はない。これを再生するとabaaと言うだろう)
5. アクション4を再生する。(abaaと言う。abaabと言う方法はない。これを再生するとabaabと言うだろう)
6. アクション2を再生する。(baと言う。baaと言う方法はない。これを再生するとbaaと言うだろう)
7. aと言う。(aaと言う方法はない。これを再生するとaaと言うだろう)
8. アクション1を再生する。(abと言う。abEOFと言う方法はない。最後のアクションは決して再生されないが、
9番目の最初の文字が何であれ、abaまたはabbになるだろう)
しかし、それは唯一の方法ではありません。見てみましょう。
a b a-b a-b-a a-b-a a-b-a-a a-b
1. aと言う。(abと言う方法はない。このアクションを再生するとabと言うだろう)
2. bと言う。(baと言う方法はない。このアクションを再生するとbaと言うだろう)
3. アクション1を再生する。(abと言う。abaと言う方法はない。これを再生するとabaと言うだろう)
4. アクション3を再生する。(abaと言う。abaaと言う方法はない。これを再生するとabaaと言うだろう)
5. アクション3を再生する。(abaと言う。4はabaaと言うだろうが、これは無駄な辞書スロットだ!これを再生するとabaと言うだろう)
6. アクション4を再生する。(abaaと言う。abaabと言う方法はない。これを再生するとabaabと言うだろう)
7. アクション1を再生する。(abと言う。abEOFと言う方法はない。最後のアクションは決して再生されないが、
8番目の最初の文字が何であれ、abaまたはabbになるだろう)
1アクション少ない!しかし、ステップ5の注に注意してください。
さて、flexiGIFに戻りましょう。それがやっていることは「柔軟な解析」です。これは、プログラムが最も遠くまで到達するアクションを即座に決定するのではなく、2つのアクションの最も遠くまで到達する組み合わせが何になるかを知るまで決定を延期することを意味します。次に、最初のアクションを発行しますが、2番目のアクションは再評価のために保持します。これは1ステップ先読みと呼ばれます。基本的にまだ貪欲ですが、今は2つのアクションを使用します。
理論的には、はるかに優れており、最適でさえあるはずですが、ステップ5で起こったことは、辞書スロットが無駄になり、それが(リセットが発生するまで)永遠に失われることを意味します。だからこそ、flexiGIFはより悪い結果をもたらす可能性があるのです。それは貪欲な圧縮を完全に諦め、「各(サブ)貪欲なマッチに対して、貪欲な次のマッチを見つける。前者を発行する」という方法に固執します。
ZGIF
そこで、私自身のものを作成する必要がありました。私は「実際にすべての可能性をチェックするのはどれくらい遅いだろうか?」と思っていました。そこで試してみたところ、何を発見したでしょうか? カタツムリのように遅い。(ここで、PythonはCPUバウンドなソフトウェアには最適ではないことに注意すべきです。Zigを学ぶ機会を得たいです。)16x16の画像を完全に圧縮するのに、私のラップトップで4分かかります。それは非圧縮で256バイトです。そして、数分かかります。すごい。
私は同じことを何度も計算しているに違いありませんよね?(いいえ、それは改善をもたらさないものだけです。最初のバージョンは30分かかりました。)
そこで、現在最先端のものを上回ったまま、4分から4秒に短縮できる、現在最良のものよりすぐに拡張できない探索をすべてスキップするオプションを設けることにしました。これは結果を悪化させますが(実際には最良の解を見つけられませんが)、それでも最先端を上回るというのは考慮に値する勝利です。
SourceHutのZGIFリポジトリを見ることができます。コードは決してクリーンではありませんが、Gitの履歴で私の思考プロセスを見ることができます。A*から動的計画法、そして枝刈りを用いたハイブリッド探索へと進みました。
お役に立てば幸いです!