Een vlag comprimeren tot 11 bits

Hij liet zien hoe je vlaggen over hun assen kunt ontleden om ze als matrices weer te geven en zo opslagruimte te besparen. Uiteindelijk werd dit gebruikt om terug te keren naar daadwerkelijke matrices en berekeningen daarmee.

Dit inspireerde mij: vlaggen zijn vaak erg simpel — gewoon enkele gekleurde strepen, of algemene elementen zoals een ster, een halve maan of een kruis. Met een aangepast coderingsschema zou het definiëren van de Franse vlag (🇫🇷) als "3 strepen, Blauw, Wit, Rood", in combinatie met een aangepaste decoder en renderer, slechts een handvol bits moeten kosten. Hoe zou zo'n codering eruitzien?

Ik heb geprobeerd er een te maken.

Vereisten

Om te beginnen heb ik enkele acceptatiecriteria opgesteld voor mijn codering:

• De gedecodeerde vlag moet "herkenbaar genoeg" zijn: Details hoeven niet exact correct te zijn. Kleine afwijkingen en onnauwkeurigheden zijn acceptabel, zolang iemand ernaar kan kijken en kan zeggen: "Ah, dat is die vlag!". Dit geldt voor de exacte plaatsing, vormdetails van objecten en de exacte kleur (bijvoorbeeld: een specifieke tint blauw wordt vereenvoudigd tot een gemiddeld blauw).
• Alleen landvlaggen: Geen staatsvlaggen, stadsvlaggen of andere vexillologische ontwerpen.
• Geen Nepal (🇳🇵): Sorry Nepal, ik hou van je niet-rechthoekige vlag, maar dit zou de zaken te veel compliceren.
• Variabele lengte: Simpele vlaggen moeten zeer weinig bits vereisen, terwijl complexe vlaggen meer bits mogen gebruiken.
• Geen wapenschilden: Vlaggen zoals die van Andorra (🇦🇩) bevatten hun eigen wapenschild, waarvoor je in feite een aangepaste bitmap of vector nodig hebt. Dat zou een SVG of iets dergelijks in het kleine formaat plaatsen, dus dat laten we weg.

Wat maakt een vlag een vlag?

Eerst moest ik uitzoeken welke elementen veelvoorkomend zijn in vlaggen. De lijst van alle landvlaggen van Worldometers was hiervoor erg nuttig.

Vlaggen zijn gevarieerder dan ik dacht. Er zijn de eenvoudige gestreepte vlaggen zoals Frankrijk (🇫🇷), Italië (🇮🇹) of Duitsland (🇩🇪). Dan zijn er ontwerpen zoals die van Burundi (🇧🇮) of Bosnië (🇧🇦) met sterren en secties. Noord-Macedonië (🇲🇰) en de Seychellen (🇸🇨) hebben radiale strepen. Tsjechië (🇨🇿), de Bahama's (🇧🇸) en anderen hebben aangepaste driehoeken aan de linkerkant, en er is nog veel meer.

De meest voorkomende gemeenschappelijke elementen zijn:

• Strepen: Horizontaal (🇫🇷), verticaal (🇩🇪), twee strepen (🇵🇱), drie strepen (🇦🇲), dertien strepen (🇺🇸), ongelijkmatige strepen (🇨🇴) of schuine strepen (🇨🇬).
• Veelvoorkomende vormen: Sterren (🇻🇳), halve manen (🇩🇿) en cirkels (🇯🇵), in verschillende maten en posities (één ster in Vietnam, vele in de VS).
• Kleurrijke driehoek aan de linkerkant: Verrassend algemeen in veel kleuren, maar vaak met dezelfde algemene vorm (🇰🇲, 🇧🇸, 🇨🇿).
• Gekleurde linkerbovenhoek: Een soort aangepast rechthoekje in de linkerbovenhoek (🇺🇸, 🇬🇷).
• Union Jack: 🇬🇧, 🇦🇺, 🇳🇿, 🇹🇻.
• Noordse landen: De Scandinavische kruisen (🇳🇴, 🇸🇪, 🇩🇰, 🇫🇮).

De vlag ontleden

Op basis hiervan moet het protocol de volgende elementen definiëren:

Beeldverhouding (Aspect Ratio)

Vlaggen hebben allemaal hun eigen beeldverhouding, maar er zijn duidelijke patronen: ongeveer 45% heeft een verhouding van 2:3, ongeveer 28% heeft 1:2, en ongeveer 9% heeft 3:5, gevolgd door een 'longtail' van andere formaten.

Kleurenpalet

We richten ons op algemene kleurtonen in plaats van exacte kleurcodes. We gebruiken kleurgroepen zoals Blauw, Groen en Geel. Er is een grote prevalentie van rood, wit, blauw, geel/goud, groen, zwart en oranje.

Lagen

Het is logisch om de inhoud te definiëren met behulp van "Lagen" in plaats van alle veelvoorkomende elementen apart hard te coderen. Elke laag kan zijn eigen lijst met opties hebben.

Dit werkt zoals in Photoshop: voor de Amerikaanse vlag (🇺🇸) zou je eerst een strepenlaag hebben, dan een laag voor het blauwe rechthoekje en tot slot een sterrenlaag.

• Strepenlaag: De meest voorkomende laag. Opties voor het aantal strepen, kleuren, richting, gelijke of ongelijke verdeling en herhalende patronen.
• Vormenlaag: Voor sterren, halve manen en andere vormen, inclusief positie en rotatie.
• Band- en Region-lagen: Om een specifiek rechthoekig gebied in te kleuren.

Omzetten naar bits

Veel aspecten van vlaggen lijken de Wet van Zipf te volgen (beeldverhouding, gebruikte kleuren, elementen). Om veelvoorkomende elementen kort te houden, heb ik besloten bijna alles te coderen in een eigen Huffman-boom, waarbij de meest voorkomende gevallen korte binaire codes krijgen.

Om de 'longtail' mogelijk te maken zonder een enorme boom te creëren, heb ik alle waarden die slechts in één vlag voorkomen weggefilterd. In plaats daarvan is het laatste blad van de boom een "Custom"-waarde, gevolgd door een optie met een vaste lengte. Hierdoor kan bijvoorbeeld El Salvador (🇸🇻) zijn beeldverhouding van 189:335 behouden zonder dat dit specifiek in de boom hoeft te staan.

Hieronder staat de Huffman-boom voor de beeldverhouding:

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

Voor de 45% van de vlaggen met een beeldverhouding van 2:3 is het dus voldoende om het eerste bit op 0 te zetten. Het totale formaat bestaat uit Huffman-bomen voor:

• Beeldverhouding (meest voorkomend: 2:3, 1:2, 3:5)
• Aangepaste Breedte:Hoogte voor de longtail
• Grootte van het kleurenpalet (meest voorkomend: 3, 2, 4, 5)
• Aangepaste "Aantal - 7" voor de longtail, aangezien de boom tot 7 gaat
• Kleur (meest voorkomend: Rood, Wit, Blauw). Aangepaste kleuren kunnen worden gegeven als een compacte 10-bit RGB-benadering (RRR GGGG BBB)
• Aantal lagen
• Type laag (Strepen, Vorm, Regio's, Kruis, Band, Ingebouwd)
• Gespecialiseerde subbomen (bijv. aantal punten van een ster, plaatsing van de vorm)

Het gehele formaat is in feite een opeenvolging van Huffman-boomtraversals.

Laten we dit testen met de vlag van Indonesië (🇮🇩), wat waarschijnlijk de "gemiddeldste vlag" is en daarmee een winnaar voor onze codering:

1. Beeldverhouding 2:3 (1 bit) → 0
2. Kleurenpalet van 2 kleuren (2 bits) → 10 (3 kleuren is gebruikelijker, dus dit kost een bit extra)
3. Definiëren van de 2 kleuren: Rood (2 bits) → 00 en wit (2 bits) → 01
4. Aantal lagen: 1 laag (1 bit) → 0
5. Strepenlaag (1 bit) → 0, "palette-equal" modus (elke kleur uit het palet krijgt één gelijke streep, 1 bit) → 0 en horizontale strepen (1 bit) → 0

Gecombineerd: 0 10 00 01 0 0 0 0, of in base64: QgA=.

Met dit formaat kan de gemiddelde vlag worden weergegeven in 76 bits, met een mediaan van 55 bits. De langste is Qatar (🇶🇦) met 420 bits. Die vlag kon nauwelijks in het formaat worden gepast vanwege de zigzaggende rand, die ik heb gecodeerd als 11 individuele rechthoeklagen.

De Union Jack 🇬🇧

Hier heb ik een beetje gesjoemeld. De Union Jack komt veel voor, maar is te complex om op te bouwen uit lagen. Daarom heb ik deze als een "ingebouwde vorm" in het protocol geplaatst. Een vlag kan nu simpelweg "Union Jack-laag in de linkerbovenhoek" specificeren.

Codering

Eerst gebruikte ik Base64 om de bits om te zetten in bewaarbaar tekstformaat. Met 6 payload-bits per ASCII-byte had de gemiddelde vlagdefinitie 14 tekens nodig (mediaan 12). De kortste code is QgA= voor de vlag van Indonesië.

Later stapte ik over op Base94, dat elk zichtbaar ASCII-teken van "!" tot "~" gebruikt om de efficiëntie te verhogen. Ik heb ook nagedacht over een Emoji-gebaseerde codering, maar omdat elk Emoji-teken meer dan 1 byte kost, zou het totaal aantal bits waarschijnlijk toenemen. Bovendien wilde ik het risico niet lopen om de vlag van een land te coderen als "💩🤮👎".

Met Base94 zitten we op een gemiddelde van 12 tekens per vlag, met een mediaan van 9. Indonesië blijft de kortste: <F.

Rendering

Ik heb ChatGPT Codex gebruikt om het formaat om te zetten in een systeem van twee stappen: een encoder/decoder en een SVG-renderer.

De decoder zet de binaire blob eerst om in een leesbaar formaat. Voor de vlag van Indonesië ziet dat er zo uit:

{
  "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
        }
      ]
    }
  ]
}

De renderer zet dit vervolgens om in SVG-code:

<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>

De code hierachter is vrij netjes, maar zelfs na compilatie was de encoder/decoder 27 kB en de renderer 12,5 kB. Dat leek me wat veel nadat ik elke bit van het bronformaat had geoptimaliseerd.

Daarom heb ik via Codex een alternatieve "minidecoder" gemaakt: het decoderen en renderen in één pass combineren, de klassenstructuur verwijderen en alles terugbrengen tot kleine primitieve functies. Dit resulteerde in één TypeScript-bestand van 470 regels, wat gecompileerd 5,29 kB (2,66 kB gzipped) groot is.

Vlaggen die niet gedekt worden

Met dit primitieve formaat ben ik erin geslaagd 128 vlaggen te coderen met wisselend succes. Er waren echter 67 vlaggen die ik niet kon coderen. De belangrijkste redenen hiervoor zijn:

• Wapenschilden, zegels of nationale emblemen (25): o.a. Spanje, Equatoriaal-Guinea, Andorra, Belize, Brunei, Cambodja, Costa Rica, Kroatië, Dominicaanse Republiek, Ecuador, El Salvador, Fiji, Haïti, Mexico, Moldavië, Montenegro, Nicaragua, Oman, Paraguay, Portugal, San Marino, Servië, Slowakije, Slovenië, Venezuela.
• Object-glyfen zoals wapens, gereedschappen, kronen, schilden of een hoed (11): o.a. Angola, Barbados, Eswatini, Guatemala, Kenia, Lesotho, Liechtenstein, Malta, Mozambique, Tadzjikistan, Vaticaanstad.
• Dier-glyfen, meestal adelaars en andere vogels (10): o.a. Albanië, Bhutan, Dominica, Egypte, Kiribati, Papoea-Nieuw-Guinea, Sri Lanka, Oeganda, Zambia, Zimbabwe.
• Plant-glyfen zoals bladeren, takken of nootmuskaat (5): Canada, Cyprus, Eritrea, Grenada, Libanon.
• Geometrie die het lagenmodel niet kan uitdrukken, zoals Y-vormen, V-velden, een wereldbol of een niet-rechthoekige omtrek (5): Antigua en Barbuda, Brazilië, Nepal, Zuid-Afrika, Vanuatu.
• Arabische tekst of kalligrafie (4): Afghanistan, Iran, Irak, Saoedi-Arabië. (Een aangepaste tekstlaag zou hier kunnen helpen).
• Religieuze of culturele symbolen zoals de Ashoka Chakra, tunduk, Soyombo of Taegeuk (4): India, Kirgizië, Mongolië, Zuid-Korea.
• Ornamentale patronen aan de stokzijde (hoist): Wit-Rusland, Kazachstan, Turkmenistan.

Kortom: bijna al deze vlaggen bevatten een aangepaste glyf of tekst die niet eenvoudig weergegeven kan worden met geometrische lagen.

Willekeurige vlaggen!

Nu er een gestructureerde taal is voor hoe een vlag eruit kan zien, heb ik een randomizer toegevoegd. Deze vult een nieuwe vlag met willekeurige items uit de verschillende Huffman-bomen. Het resultaat is... tja, ik kan me voorstellen dat een land zo'n vlag heeft?

Conclusie

Ik weet zeker dat anderen nog meer methoden kunnen vinden om bits te besparen of volledig andere manieren kunnen bedenken om de data te comprimeren. Toch was het erg leuk om vanuit een lijst met alle vlaggen de gemeenschappelijke elementen te vinden en te zoeken naar manieren om zoveel mogelijk data in bits te proppen. Het was bovendien leuk om mijn kennis van Huffman-codering uit mijn bachelor weer eens toe te passen en code op bit-niveau te schrijven.

De uiteindelijke pagina met vlaggen is te vinden op https://vantezzen.github.io/miniflags/ en de broncode is beschikbaar op GitHub. Verwacht geen super nette code; het is grotendeels "vibe coded" op basis van mijn ideeën over het formaat. Alle details over het formaat zijn gedocumenteerd in de repository.