Compressing a Flag to 11 Bits
read.vantezzen.io112 points by bennett_dev 3 days ago
112 points by bennett_dev 3 days ago
In case anyone else was curious about using a lookup table: there are there are fewer than 256 recognized countries or territories [1], so 8 bits should be enough for a key.
This would be superior to the 11-bit encoding presented here because it handles complexities such as coats of arms. It would also handle bizarre situations such as two countries having almost identical flags [2].
[1] https://en.wikipedia.org/wiki/List_of_countries_and_territor...
[2] https://www.worldatlas.com/articles/country-flags-that-resem...
Maybe there's an allegory to the sciences. But I rather a model be suboptimal in encoding that can be used to generate hypothetical reasonable flags in its unpopulated states, than having an optimal encoding which doesn't answer questions or reveal possibilities in its unpopulated states. Like what does flag #0xFE look like in an 8-bit encoding? I really like the idea of driving compressed trees in reverse with random data to generate new fascinating (valid) sequences.
Also, for compressing into 8 bits - is this not like saying "I can compress all of Shakespeare's plays in 6 bits" because there are ~39 plays, but then the size of the "shakespearezip" is just the sum of the works?
Okay, but the article literally uses "Union Jack" as a primative.
That is an orthogonal matter and maybe my imagination is limited. But when I think of realistic new flags I do not think of a union jack missing its right diagonal in the corner (e.g. if we decide to decompose the UJ primitive).
We could also complain that the crescent is a complex primitive. Why not define it with three parameters: two circle radii with a center offset?
Choosing the primitives is hard and requires domain knowledge/taste, and finding a simple enough implementation solving for key usecases (e.g. decent coverage of maps, meaningful bit encoding) and descoping (e.g. deciding on no emblems) is also hard.
But I am personally impressed with the primitives the author created and the scope simplifications done to achieve it.
I don't understand why this is the top comment. The article isn't about encoding a bag of unique items, it's about drawing the flag. So of course you can do it in 8 bits, because you're just storing the "id", not how to draw it.
The actual article borders on just using IDs too. Things like the Union Jack are just stored as is.
The techniques here let you encode the currently existing flags but aren’t really enough to build a flag from scratch.
I’d give it a bit more credit than that. They encoded 128 flags with their scheme, only 5 of which have the union jack. The rest are truly built from scratch.
While in fairness the remaining flags seem like they would need more hard coded symbols, it’s still interesting as a procedural plausible flag generator.
Yeah. I had to read the comment a few times to make sure that I'm not missing anything, but you are right. Those are two distinct things.
As a side note, the title is not accurate either because the method in the article can compress only one flag to 11 bits:
> Using this format, the average flag can be represented in 76 bits, with a median of 55 bits.
One can use Huffman encoding (the same encoding the article uses) to compress one of the flags to a single bit.
A spec-compliant Unicode renderer is expected to render 259 flags [1]. So 8 bits isn't quite enough. You would need 9.
Obviously an arbitrary bitmap of dimensions that could be used for a recognizable flag would need orders of magnitude more storage. The constraint that we are representing a finite set of flags is what admits such a compact representation.
[1] https://www.unicode.org/Public/emoji/latest/emoji-sequences....
I’m surprised that the near-identical flags list omits Slovenia and Slovakia which both have white-blue-red horizontal stripes and a coat of arms (albeit with slightly different placement and different background colors on the coats of arms). A part of me feels like it’s part of a long-time joke the two countries are playing to confuse non-Slavs (the Slovenian word for their language is Slovenščina while the Slovak word for their language is Slovenčina and this is just the beginning of the confusion between the two countries/nationalities).
There are only 500K or so full length feature films so we should be able to encode them in about 18 bits or so. Who needs mp4 anyway!
I can't believe that second article doesn't include images of the flags it is talking about. Not even the links provided for each country show the flag...
Well it uses their emoji so you can see them. At least on my phone using brave. Iirc firefox doesn't reliably render them but I'm not sure
you could also exploit the fact that some flags may appear more frequently than others and use huffman encoding or something to encode the commonly used flags in a shorter sequence than rarely-mentioned countries, and save some bits on average
but then you have to have the svg built into decoder. will they be smaller than 5KB?
also then it's no different from a svg sprite
I feel like it would be unfair to make them include the SVG decoder, the artical uses TypeScript and I believe that is a feature most runtimes (browsers) provide. However they do have to include the SVG files themselves. The Canadian flag from Wikimedia comes in at 699 bytes and France at 262 bytes. So I'm fairly confident that even with compression they'll be over 5kB
Loved the title. I was like "that's 10 bits too many for a flag!" Haha
Slightly reminds me of how we used to use TINYINT in MySQL to store boolean flags (which can store a range from -128 to 127 or 0-255 if unsigned).
I'm the kind of nerd who secretly wished to store many such bools in one integer and use the bitwise operators to query them, but restrained myself from ever doing this, since if I managed to sneak that through code review, the number of curses of my name would no doubt become so large (and so loud) over time that it would affect my employability.
That’s ubiquitous in slightly lower level programming (pretty much every non-small C program probably does it in some way or other), but the problem with doing that in this database scenario is that you might run into atomicity issues.
To toggle a flag, you have to read the column, modify it, and write it back. If someone else does that to another flag at the same time, there’s a race that one of you might win, at the expense of the other flag’s new value.
Unless you employ a lock that would otherwise not be necessary.
This reminds me of a great series on YouTube called "Can You Draw Every Flag in Powerpoint?"[1] and the guy does his darnedest to do it precisely, and in the process you learn just how specific (and sometimes non-specific) flags are!
[1] Part 1: https://www.youtube.com/watch?v=w5QSVhgrqVE
A jack is a flag flown from a jackstaff, wot is found at the back of a ship or boat.
The UK flag is called the Union Flag (it's a flag and it is a union of various flags and possibly nations too!) but let's face it, given how many people think its called the Union Jack, it doesn't really matter.
If your flag pole at home is somewhat canted then I think you can call it a jackstaff, with a similar justification to the Royal Navy managing to designate their shore bases as ships. For example just up the road is HMS Heron (His Majesty's Ship: Heron).
The Union Flag/Jack is only the flag of the UK by convention and not law. It's a bit wooley, just like our Constitution but it still all works.
My point is that whilst I do enjoy this encoding scheme and it is jolly clever, reality is way more complicated. The UK's flag is pretty complicated but not alone. I'm pretty sure several flags have tassels, which I suppose strays into the coat of arms territory.
How hard do you want to squint!
I enjoyed that the Union Flag just gets its own 'preset' - the fact that it's still presiding over a large handful of others makes it a very efficient decision compared to trying to tease out all the necessary shapes to reconstruct it.
I'll admit, I was hoping for some geometric approximations for countries like Brazil, though.
This scheme is OK but not OK. You note the Brazil flag and that's a great example along with the likes of the UK and the US too.
The Brazilian flag is nominally "quite" simple: Green with a yellow/gold parallelogram/rhombus with a blue circle ... then there is the white band and stars. Absolute nightmare to classify.
I thought the UK flag was a bit of a challenge and I remember an art class 50 odd years ago, trying to paint the bloody thing. Little did I know at the time about how Aussies and Kiwi worriers and co would fare! Won't someone think of Hawaiians: their state flag is not something you depict for a quick laugh!
I suppose the US flag is arguably the hardest to depict: Those stars would take ages to draw/paint/dribble. I imagine kids get a box of stars to stick on their depictions in art classes in the US.
What's really hard, together with the quantity of them is that they're white! I haven't actually seen many star stickers used, but agree that's a great idea.
Often, when the Flag's depicted in kids' art, paints or paint pens are used, since 'negative space' stars would take forever to do with a blue marker or pencil but is quicker to paint on top of blue. And there's a great deal of artistic license used in terms of their size and color. Or on a small flag, just a lot of tiny white dots!
There are exactly 64 flags excluded for having custom glyphs/seals/symbols/icons, which is crying out for an “appendix” lookup table to complete the encoding. The positions look very regular too, you could probably fit the positioning in the remaining 2 bits of a u8.
Spoiler: after all this work only 128 flags were encoded to some degree, 67 left out. Dunno that I’d call an encoding scheme that can only represent 66% of its target set (and even so, with self admitted limitations) successful in any way.
This cool as an encoder, but to me, the most interesting aspect is the generating part near the end of the article. I can see me using that for a game or for avatars.
Surprised this didn’t mention heraldry, which has what’s basically a DSL for coats-of-arms:
If you're on Windows (where Microsoft famously chose they would not get involved with flags and show country codes instead), execute this in dev tools or save it as a javascript bookmarklet to make the emoji flags show up:
javascript:(function(){if(!document.getElementById('twemoji-styles')){const s=document.createElement('style');s.id='twemoji-styles';s.textContent='img.emoji{height:1em!important;width:1em!important;margin:0 .05em 0 .1em!important;vertical-align:-0.1em!important;display:inline!important;}';document.head.appendChild(s)}const r=()=>{const o={folder:'svg',ext:'.svg'};twemoji.parse(document.body,o);if(!window.__twemojiObserver){let t;const ob=new MutationObserver(()=>{clearTimeout(t);t=setTimeout(()=>{ob.disconnect();twemoji.parse(document.body,o);ob.observe(document.body,{childList:true,subtree:true});},300);});ob.observe(document.body,{childList:true,subtree:true});window.__twemojiObserver=ob;}};if(window.twemoji){r();}else{const sc=document.createElement('script');sc.src='https://cdn.jsdelivr.net/npm/@twemoji/api@latest/dist/twemoji.min.js';sc.crossOrigin='anonymous';sc.onload=r;document.head.appendChild(sc);}})();Thanks, that fixes it in Chrome for me. Firefox was already displaying the flags correctly from the beginning.
Nobody? Okay then: "Fun with flags!". There, I said it.
Cool idea. The author's AI failed to encode flags for approximately 35% of the world's population. Approximately 3 billion people. At least that's why my AI tells me. India obviously contributes a lot to this. I'm probably salty because my own country's simple (?) flag is also in the "unencodable" group. Lol.
I applaud the author holding aspect ratio as a priority to encode. It's jarring to see an otherwise correct and familiar flag stretched into an incorrect shape when flown or shown.
Nice work! I wonder if you could (or did?) choose a more median shade for each color, especially blue? It seems, going by the comparison page, that most flags actually call for a less royal, more sky shade of blue, so you could use the median (on a linear RGB scale, or XYZ) shade instead as the designated representative for that color?
I noticed Rwanda seems to have the wrong aspect ratio, though you are able to encode that arbitrarily, no?
How to encode all flags in a minimum number of bits:
1. Quantise colours to, say, 8 colours that you can confidently distinguish. Use a scheme that prefers "most commonly used" colours that actually appear in the flags.
2. Render each colour-quantised flag to a fixed-size bitmap, e.g., 100x50.
3. We seek a minimum-size subset of pixel locations P such that every pair of flags differs in colour at at least one of these pixel locations. This is the NP-complete problem Minimum Test Set [0] -- in fact, a slight generalisation, because the answer to each "test" (pixel location) is not yes or no but one of 10 colours. You could try to solve this by growing an exactly minimal solution using branch and bound, but this is likely to be too slow for such a large bitmap. Alternatively, I expect repeatedly running a heuristic that builds solutions by randomly adding any pixel location until all flags become distinguishable to be highly effective as there will likely be many equal-size optimal solutions, though of course you won't get an optimality guarantee this way.
4. At this point, since the 8 colours can be represented by 3 bits each, you basically have a 3|P|-bit "hash" that distinguishes all flags. If that is still bigger than log2(nFlags), you could shrink it further with standard minimal perfect hashing techniques.
ETA: There are a few ways to improve this. One thing you want is to choose relatively "stable" pixel locations that are not close to boundaries between colours on any flag, to avoid the problem of slightly different rasterisations of the same flag giving different answers (imagine if you were applying this to scanned photos of flags). To achieve this, you could compute, for each pixel location, a "stability value": The minimum distance in pixels to any differently-coloured pixel, across all flags. Then instead of considering all 100x50 pixel locations, you might consider only the 30 with the highest stability values. With such a small set of pixel locations to consider, it's feasible to consider all ~1 billion subsets of them, giving you a known-optimal solution.
I thought a flag is 1 bit
> I thought a flag is 1 bit
Well you see, it has to implement IStateful and IBooleanExpression, and both of those involve virtual methods so you have a vtbl pointer as well.
So that's 64+1 bits right there.
Then you also have the address-alignment requirements for that vtbl pointer, so practically speaking were talking 128 bits.
Or 80 bits of you're rolling dirty and say "screw it" to that alignment assumption.
Now if your on x86-64 and want to smuggle that bit value into the unused part of that "64" bit vtbl pointer, you could probably bring it down to just 64 bits overall I guess. Well probably want to let the compiler know about that though, before anyone tries actually using that vtbl pointer.
But, if we also need to make this accessible to Python, then...
With all the attention on the link between compression and intelligence lately it is neat to have this example of how creating a encoding scheme naturally allows you to create new (likely) never before seen flags.
Cool idea. Interesting that Indonesia, Poland and Monaco with very similar two-stripe designs have different compression rates (11, 14 and 17 respectively). Probably the aspect ratio that also gets encoded.
Fun fact: Constitution of Nepal has chapter about format of The Flag and it reads as geometry textbook problem (starred one, for advanced students).
This reminds me of the old joke[0]:
There are 10 kinds of people in the world.
Those who understand binary and those who don't.
I had some physical therapy sessions back in 2021, and during that time, I discovered the myths of Procrustes and his infamous bed. I shared the profile of Procrustes with the doctor of PT, and he was thrilled. He will probably get a tattoo of that guy.
Perhaps every month I should bestow a Procrustean Award on some Show HN like this. I hereby proclaim the September 2026 Procrustean Award goes to vantezzen for their 11-bit flag-encoding.
I will also point out that flags change over time, and there may be more than one flag in use by an entity (the latter is something that Unicode ignores.)
And my favorite flag drama of the 2020s is when Wikipedia "discovered" that its Vatican Flag image was "wrong"... after distributing it far and wide: https://www.ewtnnews.com/world/us/wikipedia-had-the-wrong-va...
you couldn't dedicate one of those bit patterns to nepal?
fun stuff
> Some kind of custom rectangle happening in the top left
I believe that is a "canton": https://en.wikipedia.org/wiki/Canton_(flag)
> In vexillography, the canton is a rectangular emblem usually placed in the upper hoist of a flag, usually occupying up to a quarter of a flag's area. The canton of a flag may be a flag in its own right. For instance, British ensigns have the Union Jack as their canton, as do their derivatives such as the national flags of Australia and New Zealand.
They say it's in the "upper hoist" because it's not per se the top left - If the flag is flying and you're seeing it from behind, it may be the top right. Either way it is the side closer to the flag pole, or whatever it's flying from. When shown on a computer screen or in print, usually it is the top left. Some flag codes require flags to be mirrored on the right side of vehicles or uniforms so that it always appears to be flying from the vehicle or person as they move forward.