国旗を11ビットに圧縮する

最近、「Physics for the Birds」というチャンネルの興味深いYouTube動画を見ました。主な内容は行列についてですが、行列の演算を説明するために国旗が使われていました。

［画像: 動画からのスクリーンショット］

動画からのスクリーンショット

動画では、国旗をその軸に沿って分解し、行列として表現してストレージスペースを節約する方法が解説されていました。最終的には、実際の行列やその計算に戻るために使われました。

しかし、これが私にインスピレーションを与えました。国旗はしばしば非常にシンプルです――単なる色のストライプ、星、三日月、十字のような一般的な要素です。カスタムエンコーディングスキームを使えば、例えばフランス国旗を「青、白、赤の3つのストライプ」のように定義し、カスタムデコーダーとレンダラーを使えば、ほんの数ビットで済むはずではないでしょうか？そのようなエンコーディングはどのようなものになるでしょうか？

そこで、私はそのようなエンコーディングを作成しようと試みました。

要件

まず、エンコーディングの受け入れ基準を設けました。

• デコードされた国旗は「十分に認識可能」であること

• 細部は正確である必要はありません。誰かがそれを見て「ああ、あれはあの国旗だ！」と言える限り、小さなずれや不正確さは許容されます。

• これには、正確な配置やオブジェクトの形状の詳細も含まれます。

• 正確な色も同様です。フランスがその新しい青色をどれほど誇りに思っているかは知りませんが、このエンコーディングでは、どんな青色も一般的な青色に分解できます。

• 国の国旗のみ

• 州旗、市旗、その他の旗章学的なデザインは含みません。

• 🇳🇵ネパールは除く

• ネパール、ごめんね。君の長方形でない国旗は好きだけど、これはただ事態を複雑にするだけだから。

• シンプルな国旗は非常に少ないビットを必要とし、非常に複雑な国旗はより多くのビットを許容できるようにします――固定長ではありません。

• 紋章は除く

• 🇦🇩アンドラのような国旗には、それ自体の紋章が含まれています。そのためには、カスタムビットマップやベクターが必要になり、この小さなフォーマットにはSVGのようなものが入ることになるので、それはできません。

国旗を構成するものとは？

まず、一般的な国旗がどのような要素を持っているかを理解する必要がありました。Worldometersの全国旗リストが非常に役立ちました。

まず最初に：すごい、国旗は私が思っていたよりも多様でした。もちろん、🇫🇷フランス、🇮🇹イタリア、🇩🇪ドイツのようなシンプルなストライプのものがあります。次に、🇧🇮ブルンジや🇧🇦ボスニアのような星やセクションなどを含むデザインがあります。🇲🇰北マケドニアや🇸🇨セーシェルは放射状のストライプです。🇨🇿チェコ、🇧🇸バハマなどは左端にカスタムの三角形があり、さらに多くのデザインがあります。

では、ほとんどの国旗に共通するものは何でしょうか？ 私が見る限りでは：

1. ストライプ

   1. ストライプ、たくさんのストライプ：🇫🇷横縞、🇩🇪縦縞、🇵🇱 2つのストライプ、🇦🇲3つのストライプ、🇺🇸13のストライプ、🇨🇴 不均等なストライプ、🇨🇬斜めのストライプ。

2. 一般的な形状

   1. 🇻🇳星、🇩🇿三日月、🇯🇵円。
   2. カスタムサイズと配置で――🇻🇳1つまたは🇺🇸複数。

3. 左側のカラー三角形

   1. 驚くほど一般的で、多くの色がありますが、多くは同じ一般的な形状です 🇰🇲🇧🇸🇨🇿。

4. 左上に色が付いた領域

   1. 左上にカスタム長方形のようなものがあります 🇺🇸🇬🇷。

5. ユニオンジャック

   1. 🇬🇧🇦🇺🇳🇿🇹🇻。

6. そして北欧諸国

   1. これらは間違いなく、持っておくと良いものです… 🇳🇴🇸🇪🇩🇰🇫🇮。

国旗の分解

私の分析によると、プロトコルは以下の要素を定義すべきです。

1. アスペクト比

   1. 国旗はそれぞれ独自のアスペクト比を持っていますが、明確なパターンがあります：約45%の国旗は2:3の比率、約28%は1:2、約9%は3:5――そして残りはその他のフォーマットです。

2. カラーパレット

   1. 定義したように、正確なカラーコードを再現するのではなく、一般的なカラートーンに焦点を当てます。そのため、青、緑、黄色などのカラーグループに焦点を当てます。
   2. ここでも同様の状況です：驚くほど多くの赤、次に白、青、黄色/金色、緑、黒、オレンジ――そしてその他の色が続きます。

3. レイヤー

   1. 個々の一般的な要素をハードコーディングしようとするのではなく、いくつかの「レイヤー」を使用して実際のコンテンツを定義するのが理にかなっていると思います。各レイヤーは、オプションのリストを供給できます。
   2. これはPhotoshopなどのアプリのように機能するはずです：例えば🇺🇸アメリカ国旗の場合、まずストライプレイヤーがあり、次に青い長方形のレイヤー、そして星のレイヤーがあります。
   3. 最も一般的なレイヤーは「ストライプ」レイヤーになります。これには、ストライプの数とその色、方向、均等または不均等な分布、および繰り返しパターンなどのオプションがあります。
   4. 他のレイヤーには、星、三日月、その他のための「形状」レイヤー――位置と回転を定義します。「バンド」レイヤーと特定の長方形を着色するための「領域」レイヤー。

ビットへの変換

ほとんどの物事と同様に、国旗の多くの側面もジップの法則に従っているようです――アスペクト比、使用される色、要素（ストライプ、星など）。一般的な要素を短くするために、ほとんどすべてを独自のハフマンツリーにエンコードし、一般的なケースに短いバイナリコードを割り当てることにしました。

ロングテールが存在できるように、巨大なツリーを作成することなく、単一の国旗にのみ存在するすべての値をカットオフし、ツリーの最後のリーフを「カスタム」値に設定し、その後に固定長のフリー値オプションを付けました。例えば、これにより🇸🇻エルサルバドルは、ツリー自体に含めることなく、189:335のアスペクト比を維持することができました。

例として、国旗のアスペクト比の完全なハフマンツリーを以下に示します。

［画像: notion image］

Mermaid

graph TD
    %% Internal Nodes
    root((Root))
    n1(( ))
    n11(( ))
    n110(( ))
    n1101(( ))
    n11011(( ))
    n111(( ))
    n1110(( ))
    n11100(( ))
    n111001(( ))
    n11101(( ))
    n111010(( ))
    n111011(( ))
    n1111(( ))
    n11110(( ))
    n111100(( ))
    n111101(( ))
    n11111(( ))
    n111110(( ))
    n1111100(( ))
    n1111101(( ))
    n111111(( ))
    n1111110(( ))
    n1111111(( ))
    n11111111(( ))

    %% Leaf Nodes (Ratios)
    L_2_3[2:3]
    L_1_2[1:2]
    L_3_5[3:5]
    L_5_8[5:8]
    L_10_19[10:19]
    L_3_4[3:4]
    L_4_7[4:7]
    L_1_1[1:1]
    L_7_10[7:10]
    L_8_11[8:11]
    L_11_18[11:18]
    L_11_20[11:20]
    L_11_28[11:28]
    L_18_25[18:25]
    L_1_phi[1:φ]
    L_4_5[4:5]
    L_6_7[6:7]
    L_10_17[10:17]
    L_13_15[13:15]
    L_15_22[15:22]
    L_16_25[16:25]
    L_189_335[189:335]
    L_28_37[28:37]
    L_5_7[5:7]
    L_7_11[7:11]
    L_CUSTOM[CUSTOM]

    %% Left Branch (0...)
    root -- 0 --> L_2_3
    root -- 1 --> n1
    
    n1 -- 0 --> L_1_2
    n1 -- 1 --> n11
    
    %% 110... Branch
    n11 -- 0 --> n110
    n110 -- 0 --> L_3_5
    n110 -- 1 --> n1101
    n1101 -- 0 --> L_5_8
    n1101 -- 1 --> n11011
    n11011 -- 0 --> L_10_19
    n11011 -- 1 --> L_3_4

    %% 111... Branch
    n11 -- 1 --> n111
    n111 -- 0 --> n1110
    
    %% 1110... Sub-branches
    n1110 -- 0 --> n11100
    n11100 -- 0 --> L_4_7
    n11100 -- 1 --> n111001
    n111001 -- 0 --> L_1_1
    n111001 -- 1 --> L_7_10
    
    n1110 -- 1 --> n11101
    n11101 -- 0 --> n111010
    n111010 -- 0 --> L_8_11
    n111010 -- 1 --> L_11_18
    n111011 -- 0 --> L_11_20
    n111011 -- 1 --> L_11_28
    n11101 -- 1 --> n111011

    %% 1111... Branch
    n111 -- 1 --> n1111
    n1111 -- 0 --> n11110
    
    %% 11110... Sub-branches
    n11110 -- 0 --> n111100
    n111100 -- 0 --> L_18_25
    n111100 -- 1 --> L_1_phi
    n1111001(( ))
    n11110 -- 1 --> n111101
    n111101 -- 0 --> L_4_5
    n111101 -- 1 --> L_6_7

    %% 11111... Branch
    n1111 -- 1 --> n11111
    n11111 -- 0 --> n111110
    
    %% 111110... Sub-branches
    n111110 -- 0 --> n1111100
    n1111100 -- 0 --> L_10_17
    n1111100 -- 1 --> L_13_15
    n111110 -- 1 --> n1111101
    n1111101 -- 0 --> L_15_22
    n1111101 -- 1 --> L_16_25

    %% 111111... Deepest Branch
    n11111 -- 1 --> n111111
    n111111 -- 0 --> n1111110
    n1111110 -- 0 --> L_189_335
    n1111110 -- 1 --> L_28_37
    
    n111111 -- 1 --> n1111111
    n1111111 -- 0 --> L_5_7
    n1111111 -- 1 --> n11111111
    n11111111 -- 0 --> L_7_11
    n11111111 -- 1 --> L_CUSTOM

    %% Styling for better readability
    classDef leaf fill:#e1f5fe,stroke:#0288d1,stroke-width:2px;
    classDef internal fill:#eceff1,stroke:#607d8b,stroke-width:1px;
    
    class L_2_3,L_1_2,L_3_5,L_5_8,L_10_19,L_3_4,L_4_7,L_1_1,L_7_10,L_8_11,L_11_18,L_11_20,L_11_28,L_18_25,L_1_phi,L_4_5,L_6_7,L_10_17,L_13_15,L_15_22,L_16_25,L_189_335,L_28_37,L_5_7,L_7_11,L_CUSTOM leaf;
    class root,n1,n11,n110,n1101,n11011,n111,n1110,n11100,n111001,n11101,n111010,n111011,n1111,n11110,n111100,n111101,n11111,n111110,n1111100,n1111101,n111111,n1111110,n1111111,n11111111 internal;

アスペクト比が2:3である45%の国旗の場合、必要なのは最初のビットを0に設定することだけです。

このフォーマットには、以下のためのハフマンツリーが含まれています。

• アスペクト比（最も一般的：2:3、1:2、3:5）
• ロングテール用のカスタム幅:高さ
• カラーパレットサイズ（最も一般的：3、2、4、5）
• ロングテール用のカスタム「カウント - 7」（ツリーは7までなので）
• 色（最も一般的：赤、白、青）
• カスタムカラーは、コンパクトな10ビットRGB近似（RRR GGGG BBB）として提供できます。
• レイヤー数
• レイヤータイプ（ストライプ、形状、領域、クロス、バンド、ビルドイン）
• いくつかのより専門的なサブツリー
• 例：星の点の数、形状の配置。

フォーマット全体は、国旗が何で構成されているかを定義するために、ハフマンツリーをウォークするだけです。

これで、最初の国旗をフォーマットにエンコードしてみましょう。ここでは🇮🇩インドネシアを選びます。これは間違いなく、私たちのエンコーディングの勝者、あるいは「最も平均的な国旗」と言えるでしょう。

• 2:3のアスペクト比（エンコードに1ビット）→ 0
  • 最も一般的なアスペクト比
• 2色のカラーパレットサイズ（2ビット）→ 10
  • これは、3色がツリーで最も一般的であるため、唯一ビットを失う場所です。
• 次に2色を定義します：赤（2ビット）→ 00 と白（2ビット）→ 01
  • ツリーの上位2色。
• レイヤー数1（1ビット）→ 0
  • ツリーのトップ。
• ストライプレイヤー（1ビット）→ 0、「パレット均等」モード（つまり、パレットの各色に均等なストライプを与える、1ビット）→ 0、横縞（1ビット）→ 0。
  • すべてハフマンツリーのトップ。
• → すべてを組み合わせると：0 10 00 01 0 0 0 0、またはBase64エンコードで「QgA=」。

このフォーマットを使用すると、平均的な国旗は76ビットで表現でき、中央値は55ビットです。

最も長いのは🇶🇦カタールで420ビットです：#gHR1Y$?-+]m.0xS3F!0{.UH{uDppW5u2^+s|6~(p@GwHH<N:?57K99\(s)~!G4`!。この国旗は、私たちのフォーマットにぎりぎりエンコードできると言えるでしょう。側面間のジグザグのエッジがあり、これを11個の個別の長方形レイヤーとしてエンコードしました。

ユニオンジャック🇬🇧

ここで少しズルをしたと言えるかもしれません。ユニオンジャックは非常に一般的ですが、レイヤーから構築するのが非常に複雑なため、プロトコルにビルドイン形状として丸ごと含めました。したがって、それを構築する代わりに、国旗は「左上のユニオンジャックレイヤー」を指定するだけで配置できます。

エンコードする

まず、Base64を使用してビットを保存可能なテキストに変換しました。6ビットのペイロード/ASCIIバイトで、平均的な国旗の定義は14文字、中央値は12文字を必要としました。最も短い国旗コードはインドネシア国旗の「QgA=」です。

しかし、エンコーディングをさらに効率化するために、すべての表示可能な1バイトASCII文字（「!」から「~」まで）を使用するBase94を使用することにしました。

絵文字ベースのエンコーディングも考えましたが、各文字を保存するのに1バイト以上必要になるため、文字数の削減はそれでも合計ビット数を増やすことになるでしょう。（また、国の国旗を「💩🤮👎」のようなものでエンコードするリスクも避けたいと思いました…）

これにより、国旗あたりの平均文字数は12文字、中央値は9文字になりました。インドネシア国旗は最も短いエンコーディングのままです：「<F」。

レンダリングする

ChatGPT Codexを使用して、フォーマットを2段階のシステムに変換しました。エンコーダー/デコーダーとSVGレンダラーです。

デコーダーはまずバイナリブロブを読み取り可能な形式に変換します。すでに分解した🇮🇩インドネシア国旗の場合、以下のようになります。

{
  "aspectRatio": {
    "kind": "rational",
    "height": "2",
    "width": "3"
  },
  "palette": [
    {
      "r": 210,
      "g": 16,
      "b": 52
    },
    {
      "r": 255,
      "g": 255,
      "b": 255
    }
  ],
  "layers": [
    {
      "kind": "stripes",
      "direction": "horizontal",
      "stripes": [
        {
          "color": 0
        },
        {
          "color": 1
        }
      ]
    }
  ]
}

レンダラーは、このデコードされた国旗を受け取り、以下のようなSVGコードに変換します。

<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 1.5 1">
	<rect x="0" y="0" width="1.5" height="0.5" fill="#d21034"/>
	<rect x="0" y="0.5" width="1.5" height="0.5" fill="#fff"/>
</svg>

その背後にあるコードは非常に優れており、エンコードされたバイナリ部分とレイヤーには、個別のクラスとインターフェースがあります。しかし、tscでコンパイルしても、エンコーダー/デコーダーは27kB、レンダラーは12.5kBになります――ソースフォーマットのすべてのビットを最適化した後では、少し多すぎるかもしれません…

そこでCodexに戻り、代替の「ミニデコーダー」を作成しました。デコードとレンダリングを2つの別々のエンジンではなく、1つのパスに結合し、優れたインターフェース/クラスインフラストラクチャを排除し、すべてを小さなプリミティブ関数に凝縮しました。

これにより、コンパイル時に470行のTypeScriptファイル、5.29kB（gzip圧縮で2.66kB）にまで削減できました。

カバーされていない国旗

この（むしろ原始的な）フォーマットで、128の国旗を様々な成功度でエンコードすることができました。

しかし、エンコードできなかった国旗も67ありました。注目すべき理由をいくつか挙げます。

• 🇪🇸スペイン、🇬🇶赤道ギニア、🇦🇩アンドラ、🇧🇿ベリーズ、🇧🇳ブルネイ、🇰🇭カンボジア、🇨🇷コスタリカ、🇭🇷クロアチア、🇩🇴ドミニカ共和国、🇪🇨エクアドル、🇸🇻エルサルバドル、🇫🇯フィジー、🇭🇹ハイチ、🇲🇽メキシコ、🇲🇩モルドバ、🇲🇪モンテネグロ、🇳🇮ニカラグア、🇴🇲オマーン、🇵🇾パラグアイ、🇵🇹ポルトガル、🇸🇲サンマリノ、🇷🇸セルビア、🇸🇰スロバキア、🇸🇮スロベニア、🇻🇪ベネズエラ

  • 紋章、印章、または国のエンブレムが含まれている（25）

• 🇦🇴アンゴラ、🇧🇧バルバドス、🇸🇿エスワティニ、🇬🇹グアテマラ、🇰🇪ケニア、🇱🇸レソト、🇱🇮リヒテンシュタイン、🇲🇹マルタ、🇲🇿モザンビーク、🇹🇯タジキスタン、🇻🇦バチカン市国

  • 武器、道具、王冠、盾、帽子などのオブジェクトグリフ（11）

• 🇦🇱アルバニア、🇧🇹ブータン、🇩🇲ドミニカ、🇪🇬エジプト、🇰🇮キリバス、🇵🇬パプアニューギニア、🇱🇰スリランカ、🇺🇬ウガンダ、🇿🇲ザンビア、🇿🇼ジンバブエ

  • 動物グリフ、主にワシや他の鳥（10）

• 🇨🇦カナダ、🇨🇾キプロス、🇪🇷エリトリア、🇬🇩グレナダ、🇱🇧レバノン

  • 葉、枝、ナツメグなどの植物グリフ（5）

• 🇦🇬アンティグア・バーブーダ、🇧🇷ブラジル、🇳🇵ネパール、🇿🇦南アフリカ、🇻🇺バヌアツ

  • Y字型、V字型フィールド、地球儀、または非長方形のアウトラインのようなレイヤーモデルで表現できない幾何学模様（5）

• 🇦🇫アフガニスタン、🇮🇷イラン、🇮🇶イラク、🇸🇦サウジアラビア

  • アラビア文字またはカリグラフィー（4）
  • カスタムテキストレイヤーを追加すると、ここで役立つかもしれません。

• 🇮🇳インド、🇰🇬キルギス、🇲🇳モンゴル、🇰🇷韓国

  • アショーカチャクラ、ツンドゥク、ソヨンボ、テグクなどの宗教的または文化的なシンボル（4）

• 🇧🇾ベラルーシ、🇰🇿カザフスタン、🇹🇲トルクメニスタン

  • 装飾的なホイストパターン。

→ ほとんどすべてに、幾何学ベースのレイヤーでは簡単に表現できないカスタムグリフまたはテキストが含まれています。

ランダムな国旗！

これで、国旗がどのようなものになり得るかについての構造化された言語のようなものができました。そこで、さまざまなハフマンツリーからランダムなアイテムを埋め込むランダム化機能を追加することにしました。

［画像: notion image］

［画像: notion image］

［画像: notion image］

［画像: notion image］

［画像: notion image］

［画像: notion image］

…ええ、このような国旗を持つ国があるのは想像できますか？

総括

他の人がさらにビットを節約する方法や、データを圧縮またはレイアウトするまったく異なる方法を見つけられると確信しています。しかし、すべての国旗のリストから始めて、共通の要素を見つけ、可能な限り多くのデータをビットに詰め込む方法を探すのは、非常に楽しい作業でした。学士課程で学んだハフマンコーディングの知識を実際に使い、ビットレベルのコードを書くことも非常に楽しかったです。

最終的なページはhttps://vantezzen.github.io/miniflags/で見ることができ、ソースコードはここにあります。コードはそれほどクリーンではないかもしれませんが、最終的にはフォーマットのアイデアに基づいて、ほとんどバイブでコーディングされました。フォーマットの詳細については、こちらでドキュメント化されています。

編集：これはHNで少し人気が出たようです！そこでは多くの良い、有効な批判が見られます：「世界の人口の約35%の国旗をエンコードできませんでした。約30億人」

本当にその通りです！私は主に、国旗の幾何学的な側面に焦点を当てており、それをSVGや明確な幾何学的なレイヤーにうまく変換できます。しかし、それを「普遍的な」エンコーディングスキームと呼ぶべきではないかもしれません… 紋章を異なる方法でエンコードするための素晴らしい提案をいくつか見ました――将来的にデコーダーを拡張することを試みるかもしれません！

また、「左上の領域」がカントンと呼ばれることを教えてくれてありがとう。