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

最近、「Physics for the Birds」というYouTubeチャンネルで興味深い動画を見ました。その動画の主な内容は行列についてでしたが、行列の演算を説明するために国旗が使われていました。 動画からのスクリーンショット 彼は、国旗をその軸に沿って分解し、行列として表現することでストレージ容量を節約する方法を説明しました。最終的には、これが実際に行列やそれらの計算に戻るために使われました。 しかし、これが私にインスピレーションを与えました：国旗はしばしば非常にシンプルです――単なる色のストライプ、星、三日月、十字のような一般的な要素です。カスタムエンコーディングスキームを使えば、フランス国旗のようなものを「青、白、赤の3つのストライプ」と定義し、カスタムデコーダーとレンダラーで数ビットしか必要としないはずではないでしょうか？そのようなエンコーディングはどのように見えるでしょうか？ そこで、私は1つ作成しようとしました： 要件 まず、私のエンコーディングのための受け入れ基準を定めました： デコードされた国旗は「十分に認識可能」であること 細部は正確である必要はありません。小さなずれ、不正確さは許容されます――誰かがそれを見て「ああ、あれはあの国旗だ！」と言える限りは。 これには、配置の正確さ、オブジェクトの形状の詳細も含まれます。 正確な色も含まれます。フランスが新しい青の色合いをどれほど誇りに思っているかは知りませんが、このエンコーディングでは、あらゆる青の色合いを中間の青に分解できます。 国旗のみ 州旗、市旗、その他の旗章学的なデザインは対象外です。 ネパール国旗は対象外です。 ネパール、あなたの長方形でない旗は好きですが、それは物事を複雑にするだけです。 シンプルな旗は非常に少ないビットを必要とし、非常に複雑な旗はより多くのビットを許容されるべきです――したがって固定長ではありません。 紋章は対象外です。 アンドラ国旗のような旗には、それ自体の紋章が含まれており、それにはカスタムビットマップ/ベクトルが必要になるでしょう。それは、その小さなフォーマットにSVGなどを入れることになるので、対象外です。 何が国旗を国旗たらしめるのか？ まず、一般的な国旗がどのような要素を持っているかを理解する必要がありました。Worldometersのすべての国旗のリストは、このために非常に役立ちました： まず：うわー、国旗は私が思ったよりも多様です。もちろん、フランス、イタリア、ドイツのようなシンプルなストライプのものがあります。次に、ブルンジやボスニアのような星やセクションなどを含むデザインがあります。北マケドニアやセーシェルは放射状のストライプを持っています。チェコ、バハマなど、左端にカスタムの三角形を持つものや、さらに多くのものがあります。 では、ほとんどの国旗に共通するものは何でしょうか？私が見る限りでは： ストライプ ストライプ、たくさんのストライプ：フランス（水平）、ドイツ（垂直）、ポーランド（2つのストライプ）、アルメニア（3つのストライプ）、アメリカ（13のストライプ）、コロンビア（不均等なストライプ）、コンゴ共和国（斜めのストライプ） 一般的な形状 ベトナム（星）、アルジェリア（三日月）、日本（円） カスタムサイズと位置で――ベトナム（1つ）またはアメリカ（複数） 左側の色付き三角形 驚くほど一般的で、多くの色がありますが――しばしば同じ一般的な形状です。コモロ、バハマ、チェコ 左上の角が色付けされている 左上のカスタム長方形のようなもの。アメリカ、ギリシャ ユニオンジャック イギリス、オーストラリア、ニュージーランド、ツバル そして北欧諸国 それらは間違いなく、持つべき大きなプラスです……ノルウェー、スウェーデン、デンマーク、フィンランド 国旗の分解 私がわかる限りでは、プロトコルはこれらの要素を定義する必要があります： アスペクト比 国旗はそれぞれ独自のアスペクト比を持っていますが、明確なパターンがあります：約45％の国旗は比率2:3、約28％は1:2、約9％は3:5――そして他のフォーマットのロングテールがあります。 カラーパレット 定義したように、正確なカラーコードを再現するのではなく、一般的なカラートーンに焦点を当てます。そのため、青、緑、黄色のようなカラ​​ーグループに焦点を当てます。 ここでも似たような状況です：驚くほど多くの赤、次に白、青、黄色/金、緑、黒、オレンジ――そして他の色のロングテールがあります。 レイヤー すべてを別々にハードコードしようとするのではなく、いくつかの「レイヤー」を使って実際のコンテンツを定義するのが理にかなっていると思います。各レイヤーは、オプションのリストを提供できます。 これは、Photoshopなどのアプリのように機能するはずです：例えば、アメリカ国旗の場合、まずストライプレイヤーがあり、次に青い長方形のレイヤー、次に星のレイヤーがあります。 最も一般的なレイヤーは「ストライプ」レイヤーになります。これには、ストライプの数とその色、方向、均等または不均等な分布、および繰り返しパターンなどのオプションがあります。 他のレイヤーは、星、三日月、その他のための「シェイプ」レイヤー――位置と回転を定義します。「バンド」レイヤーと特定の長方形を色付けするための「リージョン」レイヤーです。 ビットへの変換 ほとんどのことと同様に、国旗の多くの側面もZipfの法則に従うようです――アスペクト比、使用される色、それらの上の要素（ストライプ、星など）。一般的な要素を短く保つために、私はほとんどすべてを独自のハフマンツリーにエンコードすることを決定し、一般的なケースに便利な短いバイナリコードを割り当てました。 ロングテールが存在することを可能にするために、巨大なツリーを作成することなく、単一の国旗にしか存在しないすべての値をカットオフし、ツリーの最後のリーフを「カスタム」値として設定し、その後に固定長のフリー値オプションを付けました。例えば、これにより、エルサルバドルがその189:335のアスペクト比を、ツリー自体に含める必要なしに維持することができました。 例として、国旗のアスペクト比の完全なハフマンツリーを以下に示します。 グラフ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までなので） 色（最も一般的：赤、白、青）