Not sure how big the word dict is in your latest version, but you can do much better simply by reordering how you create your index. With alphabet in order, assembling letters ABCDE: 17345.00 bytes With alphabet in…
May have been a DAWG like this: https://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/l... These days GADDAG are used which are faster, but usually much less space efficient: https://en.wikipedia.org/wiki/GADDAG…
Not sure what technique you're using for the answers list, but the compress5.py suggests it's doing a basic bitmap. Base bitmap is 12972 bits, or 1622 bytes (your file lists 1619, not sure why it's 3 bytes smaller, but…
Is this just a trie, but you reverse all the words first?
You can beat 15,412 bytes with a much simpler decompression algorithm than xz. Using variable length encoding on a tail-sorted delta-offset array gets down to 13,180 bytes. Neither competes with RoadRoller (which gets…
A good idea, saves a couple bits depending on alignment.
I tried this out and got 12,231 bytes Brotli encoded, and 12,493 bytes gzipped, with 16,311 bytes raw -- so the estimate is very close. It compresses better with new lines than if you remove them all (given you could…
I like your trick of subtracting the prior node size if it's too small, it gets a number of offsets into the lower bucket to save some bits. I took this technique and made a few changes. Firstly, I effectively did…
Ah, I replied to myself with more information while you were also replying. I also surmise that the short length of the words makes a DAWG just very heavy. It's not clear to me that relative offsets would be notably…
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…
I think you might have miscalculated bits per bytes here? 8 * 17,763/64,860 = 2.19 Also, I attempted to implement this as described in this paper (variable length encoding the letters and the offsets, utilized L, and…
A trie representation physically removes letters from the dataset. Leaving it in ASCII means that it still leaves enough information behind that can be compressed well (a trie only exploits shared prefixes, not…
A trie will already run-length encode all the first letters into 26*5=130 bits pre-Huffman coding. I doubt RLE will beat that. A trie will in essence RLE every level but without needing to track the length of the run,…
Thanks, I'll look into it. This case is interesting though, because the Gameboy doesn't even have native mul/div operators, so I suspect that Huffman coding is as fancy as you're going to get while still having a small…
I tried this method today, but a huge shortcoming here is that a DAWG needs these large pointers between nodes. I based my approach on http://www.wutka.com/dawg.html and http://stevehanov.ca/blog/?id=115. I generated a…
I was thinking that it's probably not quite sparse enough to benefit from RLE as-is, since the number of bits you'd need for your lengths would outstrip the length of your run. If any run can be more than 128 words,…
You can get down to 15,559 bytes by combining a trie with Huffman coding: https://github.com/adamcw/wordle-trie-packing However, this doesn't beat general Brotli encoding of a ASCII trie representation, which gets down…
Not sure how big the word dict is in your latest version, but you can do much better simply by reordering how you create your index. With alphabet in order, assembling letters ABCDE: 17345.00 bytes With alphabet in…
May have been a DAWG like this: https://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/l... These days GADDAG are used which are faster, but usually much less space efficient: https://en.wikipedia.org/wiki/GADDAG…
Not sure what technique you're using for the answers list, but the compress5.py suggests it's doing a basic bitmap. Base bitmap is 12972 bits, or 1622 bytes (your file lists 1619, not sure why it's 3 bytes smaller, but…
Is this just a trie, but you reverse all the words first?
You can beat 15,412 bytes with a much simpler decompression algorithm than xz. Using variable length encoding on a tail-sorted delta-offset array gets down to 13,180 bytes. Neither competes with RoadRoller (which gets…
A good idea, saves a couple bits depending on alignment.
I tried this out and got 12,231 bytes Brotli encoded, and 12,493 bytes gzipped, with 16,311 bytes raw -- so the estimate is very close. It compresses better with new lines than if you remove them all (given you could…
I like your trick of subtracting the prior node size if it's too small, it gets a number of offsets into the lower bucket to save some bits. I took this technique and made a few changes. Firstly, I effectively did…
Ah, I replied to myself with more information while you were also replying. I also surmise that the short length of the words makes a DAWG just very heavy. It's not clear to me that relative offsets would be notably…
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…
I think you might have miscalculated bits per bytes here? 8 * 17,763/64,860 = 2.19 Also, I attempted to implement this as described in this paper (variable length encoding the letters and the offsets, utilized L, and…
A trie representation physically removes letters from the dataset. Leaving it in ASCII means that it still leaves enough information behind that can be compressed well (a trie only exploits shared prefixes, not…
A trie will already run-length encode all the first letters into 26*5=130 bits pre-Huffman coding. I doubt RLE will beat that. A trie will in essence RLE every level but without needing to track the length of the run,…
Thanks, I'll look into it. This case is interesting though, because the Gameboy doesn't even have native mul/div operators, so I suspect that Huffman coding is as fancy as you're going to get while still having a small…
I tried this method today, but a huge shortcoming here is that a DAWG needs these large pointers between nodes. I based my approach on http://www.wutka.com/dawg.html and http://stevehanov.ca/blog/?id=115. I generated a…
I was thinking that it's probably not quite sparse enough to benefit from RLE as-is, since the number of bits you'd need for your lengths would outstrip the length of your run. If any run can be more than 128 words,…
You can get down to 15,559 bytes by combining a trie with Huffman coding: https://github.com/adamcw/wordle-trie-packing However, this doesn't beat general Brotli encoding of a ASCII trie representation, which gets down…