Game Boy Wordle clone: How to compress 12972 five-letter words to 17871 bytes

I ended up doing some math on a theoretical DAWG, based on: https://www.cs.put.poznan.pl/dweiss/site/publications/downlo...

With 12,822 nodes, you need 57,387 bits for the labels and the Huffman table (I'm sure you could make the Huffman table more efficient, but it's only 50 bytes, so that's not helping much).

Then, to mimic their edge reordering technique but without having to actually implement all the logic, I ordered the edges by frequency and used variable length integer encoding of size 3 (this performed the best on the data set) which required 95,988 bits.

Variable length integer encoding breaks the number into 3 bit chunks, each prefixed by 1 bit to indicate if there is another 4 bit chunk to read for that number. Since the distribution of offsets is heavily skewed, optimizing the most frequent offsets into a small package is better even if rarer ones suffer from multiple prefix bits.

This is 19,171 bytes total, or substantially worse than both the original article and Huffman tries do. This isn't even counting the flag bits needed for actually traversing the graph. So even cheating, it's not clear I can get a DAWG to be within striking distance of either other approach.

I hypothesize that the reason tries and other methods perform so well here is the relatively shallow depth. All words are only length 5, so the trie doesn't ever get really deep. This also means that suffixes generally don't actually take up that much space given common ones will also pack small with Huffman coding. The size of offsets appears to be just too great relative to how much you can save by removing shared suffixes from 5 letter words.

Would love to know if there is some trick to DAWG that I'm missing that would let me get it even smaller.

My guess is that it was the last version of Visual Basic before they moved over to VB.net -- it was easy and simple, and didn't aim for industrial strength.

Like y'all, I wanted to see how I could do. Of course, I didn't get all the way to tested code on a gameboy. But it does compress & decompress in Python.

I took the central idea of encoding deltas (or actually delta less 1, since the delta is always at least one; I'll just say delta below), but did it on the full five letter word. The largest delta was still less than 2*18 but bigger than 2*17. (I'm not sure why the blog mentions 20 bits as the biggest delta; I used the dataset from https://github.com/alex1770/wordle/commit/62520406365ca58a1a...)

I decided I wanted a variable length code in bits. Manually, I found the best break-points that I could:

    breaks = [16, 128, 512, 2**12, 2**18] 
    bitprefixes = ['0', '10', '110', '1110', '1111']

So deltas 0..15 are encoded as '0' plus a 4-bit number, deltas 16..271(=16+256-1) as '10' plus a 7-bit number, etc.

Compressed like that, my dictionary runs to 14840 bytes.

    1111000000000001010110 // aahed   4839 =    4839-      0
    1110100001101100       // aalii   2813 =    7652-   4839
    1110110100010010       // aargh   4003 =   11655-   7652
    110011000010           // aarti    339 =   11994-  11655
    1111000000001101110001 // abaca   5634 =   17628-  11994
    00111                  // abaci      8 =   17636-  17628
    00001                  // aback      2 =   17638-  17636
    00111                  // abacs      8 =   17646-  17638
    100111110              // abaft     79 =   17725-  17646
    ...

However, a non byte aligned code isn't ideal, especially on the gameboy's CPU which doesn't have variable bit shifts as far as I recall. Still, over 3000 bytes beckoning to be re-used for some other purpose. Did they put in a soundtrack yet?

Compressor & decompressor: https://gist.github.com/jepler/d502965b57fd52df0838a6def2d32...