quicktwo

7 ms·

1.
by quicktwo 5y ago
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 order, assembling letters
2.
by quicktwo 5y ago
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:/
3.
by quicktwo 5y ago
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 all th
4.
by quicktwo 5y ago
Is this just a trie, but you reverse all the words first?
5.
by quicktwo 5y ago
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 down to around 12,200
6.
by quicktwo 5y ago
A good idea, saves a couple bits depending on alignment.
7.
by quicktwo 5y ago
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 just split on every 5 c
8.
by quicktwo 5y ago
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 variable length integ
9.
by quicktwo 5y ago
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 smaller to the exte
10.
by quicktwo 5y ago
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&#x27
11.
by quicktwo 5y ago
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 dropped F entirely
12.
by quicktwo 5y ago
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 suffixes).
13.
by quicktwo 5y ago
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, so I suspect it'l
14.
by quicktwo 5y ago
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 a
15.
by quicktwo 5y ago
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=11
16.
by quicktwo 5y ago
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, then you'
17.
by quicktwo 5y ago
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