ロスレスGIF再圧縮と全探索

A bit of history# GIFは、最も古く広く普及している圧縮画像フォーマットです。今日では、画像ファイル内でアニメーションを可能にすることで最も有名ですが、私はその用途にはあまり興味がありません。実際、NCSA Mosaicがサポートした唯一の画像フォーマットはこれでした。もし本当に古いブラウザをサポートしたいのであれば、ウェブサイトのすべての重要な画像にGIFフォールバックを用意する必要があります。古いChromiumのような「古い」ではありません。実際のMosaic、Netscape、IE、Netsurf、Dillo、Konquerurのような、oldweb.todayで試せるようなブラウザのことです。（おそらくそれらをサポートすることには興味がないでしょうが、これは楽しい演習です。）私は1-Click Linuxのウェブサイトが最も古いブラウザでも許容できる見栄えになることを本当に望んでいたので、<picture>要素をGIFへのフォールバック付きで使うことにしました。私は、プロダクションで使われるすべての最新のウェブ機能は、それ自体がすでに合理的に広く互換性があるべきであり、その後は絶対的な1000%の互換性を持つ一つのフォールバックのみを持つべきだと考えています。 Problem# 問題は、GIF圧縮が素晴らしいものではないということです。正直に言って、2026年にはほとんどの場合、SVGとWebP（写真には非可逆、小パレットの描画/ロゴには可逆）を使うべきでしょう。PNGでもJPEGでもなく、ましてやAI、DWG、その他のプロプライエタリなフォーマット（DICOMを見ていますよ）などは論外です。まあ、少なくともウェブ上では（名前が示す通りWebP）。部分的な解決策は、小さな画像を使うことです。本当に古いデバイスは、240x320のNokia電話のように本当に小さな画面サイズを持っています。そのため、アイコンやロゴのフォールバックは128x128で安全であり、256x256では画面に収まらない可能性すらあります。もっと良くできるでしょうか？はい。画像最適化に特化した分野全体があり、それはメタデータの削除から始まります。次に、パレットから未使用の色を削除し、次にあまり使用されない色を削除するなどです。しかし、上記のどのステップも実際の圧縮そのものについては触れていません！ ZopfliPNG# 私はzopflipngについて聞きました。PNGは、ZIPやGZIPで知られる圧縮フォーマットであるDEFLATEを使用します。これはハフマン符号化を伴う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 それを分割する可能な方法の一つ（貪欲な方法）は次のとおりです。 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と言うだろうが; これを再生するとabaaと言う - 4を再生するのと同じ！無駄な辞書スロット！) 6. アクション4を再生する。(abaaと言う、abaabと言う方法がない; これを再生するとabaabと言う) 7. アクション1を再生する。(abと言う。abEOFと言う方法がない; 最後のものは決して再生されないが、8の最初の文字によってabaまたはabbになるだろう) アクションが一つ少ない！しかし、ステップ5の注記に注意してください。さて、flexiGIFに戻りましょう。それがしていることは柔軟なパースです。これは、プログラムが最も遠くに到達するアクションをすぐに決定するのではなく、2つのアクションの最も遠くに到達する組み合わせが何になるかを知るまで決定を延期するという意味です。次に最初のアクションを発行しますが、2番目のアクションは再評価のために保持します。これは1ステップの先読みと呼ばれます。つまり、基本的にはまだ貪欲ですが、今は2つのアクションを使用します。理論的には、はるかに優れていて、最適でさえあるはずですが、ステップ5で起こったことは、無駄な辞書スロットが発生し、それが永遠に失われるということです（リセットが発生するまでですが）。これがflexiGIFが悪い結果を出す理由です。それは貪欲な圧縮を完全に諦め、「各（サブ）貪欲な一致について、貪欲な次の候補を見つける。前者を排出する」という方針に固執します。 ZGIF# そこで私は自分のものを作成する必要があると感じました。「すべての可能性を実際にチェックすると、どれくらい遅くなるだろうか？」と疑問に思いました。そこで試してみたところ、何が分かったかというと、非常に遅い！ （ここで、PythonはCPUバウンドのソフトウェアには最適な選択ではないと述べておくべきです。これを機にZigを学びたいと思います。）私のラップトップで16x16の画像を完全に圧縮するのに4分かかります。