> I don’t have a good feel for how fast the Game Boy runs, so I did a bit of speed optimization.
This sounds like a very wrong approach to optimization. I mean, if you don't know exactly what and how to optimize, or if there's a need for optimization at all, then what are you doing?
The idea of 'don't optimize if you don't have to' probably doesn't apply as much when developing a game for a 8-bit processor that runs at 4mhz with 8kb of working RAM, and when you are building a program which is inherently aiming to push the capabilities of the hardware with clever coding tricks (I mean the whole project is basically an exercise in optimization).
I think OP was saying they weren't sure if the original algorithm would be too slow to run under these conditions, and didn't have the ability to test it at the time, so they wrote it in a way which increased the chances of it running quickly considering the system limitations.
And far better than gzip compression. Nice work. My takeaway is that context matters - this is not General Purpose Compression, but compression made specifically for this case. Good Stuff.
Even though it's domain specific, it's a pretty clever idea that could carry over to other things. I wonder if you couldn't cleverly reorder any text document in chunks and get the maximum word differences per chunk, keep a map of word order and compress it this way. With a 2 bit minimum per word, maybe you could take all replica words in two bits.
If you have enough space to store the fully decompressed list, then you could in transpose the list of words - so instead of 5 by 12972 make them 12972 by 5, and get enormously long repeated runs of first, letters, second letters, etc. Any lz77 based compression will compress pretty well after that
That would be only effective for initial letters though. Implicit delta coding, where you strip a common prefix from the lexicographically previous word and mark word boundary somehow (e.g. capitalization), would be better suited if there are many short runs of words sharing a longer prefix; it seems to be the case for the Wordle list as well (about 10% smaller for zlib -9).
It would be, but it would also be really effective on those initial letters: a near-perfect use case for RLE compression on the first two characters should already result in something close to a 40% size reduction before Huffman encoding. But I suppose implicit delta coding also basically achieves that.
Anyway, thinking about the transposing idea some more: this would effectively split the word in to 26² = 625 "buckets" of three-letter suffixes. What we could do to make those still compress decently after transposing is look for shared suffixes in multiple buckets, and ensure they get grouped together in the same order before transposing. This would result in short runs in those suffixes, squeezing some more compression out of it.
... which should also work really well for implicit delta coding.
Hmm... you know, the basic concept here shouldn't be too difficult to implement and try out out, thanks for the ideas! :)
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'll outperform RLE at every level.
If you have a means of doing RLE that performs otherwise, I'd love to understand how it works.
FYI, turning it into 12972 by 5 and Brotli compressing achieves 15,093 bytes, which is less than if you first turn the data into an ASCII trie then Brotli compress that (14,180 bytes) (Source: https://github.com/adamcw/wordle-trie-packing#all-words).
This is neat. 1st letter, 2nd, then 3rd as simple lengths of runs; If you compressed a whole dictionary this way, it's possible you could then compress a document against that dictionary even further.
My only claim in this post is that anything can be pre-sorted if you want to achieve some better DS compression but of course, that means you have to have some map to undo the sorting after you decompress it (and obviously the utility only exceeds the computation time if the documents are longer than the associated dictionaries). The person who wrote the gameboy wordle compression did it by necessity, which is beautiful, and the way people used to do things when you had to fit them into tiny structures like that, so, huzzah! to that person.
But yeah, the observation that you could handle 40% reduction on the first two characters is a good clue.
So much has been missed in lossless image compression, along the same creative lines. We humans can look at an image of a red-black-yellow Cardinal bird sitting on a green-gray stem in the middle of a forest, and basically compress it in our mind in a way you'd have to throw thousands of CPU hours against. If you knew you only had to consider a red bird on a green background, you would have a whole different domain-specific strategy for compression; the amazing thing about our minds is that we can devise that compression strategy from the inputs, remember the strategy for that specific set, and then recall our own compression strategy well enough to decompress the data later.
There was, actually, an attempt in the 90s to do something they labeled "fractal compression" which was more or less an attempt to come up with a lambda function for a particular image; extremely CPU expensive to compress, and might or might not be lossy depending on the goal, but the salient thing was that the compression strategy was unique for each image. That didn't really work out as a commercial concept for a whole host of reasons. But it's one of those corners of extremely clever pre-modern code that might be worth a bundle to revisit now.
So if you wanna code something really, really fun -- consider a fully adaptive compressor that comes up with a specific strategy for each general sub-batch of use cases.
If you want to start a company doing that, let me know because I literally just came up with this idea 12 seconds ago.
To improve compression of a sorted list of words you can replace the (initial) letters repeated from the word above with spaces before compression and add them back as an extra step after decompression. For example, if the previous word was "apple", the next entry will be " y" ("apply", edit: HN removes extra spaces, so this should be four spaces + "y") ("apple" will probably already be entered as " le" (three spaces + "le")). In theory a compression algorithm could handle this automatically, but in practice this gives better compression.
This is conceptually similar to what OP does by storing the (numerical) difference between the words. Also, if you have a list of numbers that aren't random, they generally compress better if you turn it into a list of the differences between the numbers.
A simple compression algorithm (miniLZO is apparently 6KB compiled) might be small enough and save enough bytes with compression to make it worth it for OP.
How would that work? If I want to store "apple", "apply", "apron" the bytes in memory would be "appleyron". How would I know where the second word ends?
In the more general sense, there is an almost universally overlooked property of compressed data that some of the data is unordered, and you are free to rearrange it any way you want in order to improve the compression ratio.
Years ago I worked on a J2ME (Java2 Mobile Edition) application that had no business being attempted given the very small archive files allowed. We did it anyway and it actually worked pretty well. We very quickly hit the max file size however, and every feature request meant first shrinking the existing code base to make space. First we had an intern fixing bugs in the code minifier we were using, especially around deleting unused (usually debug) methods. For some reason they rejected on archive size, not payload size, so while I started out doing 'honest' work with shrinking the binary, I had spent a lot of time in college noodling with compression algorithms so my eye was eventually drawn there.
Those were in the days when I could still read JVM assembly code, and shortly after I started thinking about the compression, I realized that the constant pool entries start with the type and then the size of the entry. So while our minifier made the reasonable assumption of sorting the constant pool by type and then alphabetically within it, because most of the constant pool was strings, and strings are variable length, it was hit or miss whether the header would be treated as a run or just Huffman encoded (the fallback). If I suffix sorted, then all but the last string in the pool would be followed immediately by the header for the next string, increasing the average run length.
This ended up knocking almost a kilobyte off of the archive size. Depending on your perspective that sounds like a little or a lot, but in our case each feature cost about 500 bytes, so that change pushed the cliff I was walking toward out almost a month (and slowing the growth rate), just by changing a sort algorithm.
I filed a ticket with Sun about this, but as it turns out they already had the dense archive format in flight, and within a couple months my observation was moot because the dense format can compress constant pools across and entire archive, not just a singe file. That was at least an order of magnitude better than what I had.
It's quite likely a lot of the files we use have similar problems in them. Off the top of my head, JSON compression probably would be much higher if we treated it as unordered, and did more aggressive minification particularly for JSON-at-rest. Sorting sibling keys by value instead of by name for instance.
Is task specific compression a thing in real life practical software engineering? As far as reducing data loads go I only came across the keyword "SQL optimization".
One example that comes to mind is some work nvidia has done compressing “video” streams. They do so by capturing your facial movements and reconstructing them on the other side, resulting and massively less bandwidth.
Depends how specific you want "specific" to be I guess? I.e. we have loads of compression algorithms for different kinds of data. Whereas here we are looking at almost dataset-specific compression (i.e. the only benchmark is how it works for one specific set of data to compress), and there's a sliding scale between the two ends.
Similarly, having to contain the decompression code in the measured result size and it being a relevant contribution is something that only applies in some use cases of compression.
Scarcity breeds innovation. Why hand tune a compression scheme for a specific dataset when it is less storage efficient than LZ? You opt to not use LZ when all the memory and compute you have can barely run prefix codes.
That's why people still write for the Z80: it's a fun toy.
I have designed task specific data structures/compression oriented around memory efficiency. In my experience this starts to crop up when datasets get big enough to trigger cost for performance sensitivity. This is especially true for SaaS offerings, where e.g. an ability to stay under the next RAM doubling can result in serious hosting savings.
I'm echoing a couple of replies before me, but I'll give concrete examples - MP3, JPEG, and H.264 are all lossy task-specific compressions. Lossless compression includes FLAC and TIFF.
So, yes, actively researched, but you've got to pick a specific task that makes sense. Even small niches are viable; I made a task-specific compressor to strip the essential numbers out of a remote sensor report to make it small enough to squirt to a satellite.
Video compression algorithms are fascinating. Choosing the correct color space and reducing bit count because the human eye doesn't see color as well, using discrete cosine transform to "group together" the important parts of an image, using diffs from previous and future frames, using diffs from movement in the image. There are so many techniques.
It used to be just best practice to shrink down anything over the wire as much as possible. When I started building websites around 1996, every byte counted and you would "optimize" every GIF image carefully to the smallest size you could, taking it down to 256 or 16 or even custom colors - like 6 colors in the VGA spectrum that looked good enough with dithering.
It kinda didn't matter from 2010 on. But one area I've written my own specific "compression" methods in, for the last few years, has been in shipping data in and out of webworkers (in-browser or in Node). This is where there's still enough of a performance penalty on a lot of devices for sending 1MB that in use cases where you're spawning lots of workers to run long tasks, it makes sense to trade time to compression for a smaller transfer size.
Here's another example from a constrained environment: in Andy Gavin's interview with Ars Technica, he talks about a domain-specific compressor they made for storing Crash Bandicoot's animations, because storing each coordinate of each vertex for each frame would have been too large.
Yep, in video games, especially on older systems, we did an awful lot of that. Storing vector deltas for bone animations rather than the full vector3. Compiled graphics on old PC games I worked on, which both helped in size, but also in speed of blitting to the display. Vector3 are made up of three 32-bit floats, but frequently stored as four 32-bit floats so that everything aligns on word boundaries, but you don't need to do that for data you aren't currently using, so you can save 25% of memory right there. Also, interleaving vector3's for packing and alignment on 3d models. Lots of bitmask manipulations and interleaved SIN/COS and DIV/MUL look-up tables. These last couple of techniques go all the way back to the original Atari Asteroids game from the arcades in the 1970's.
Anything that has limited memory or limited bandwidth, or where the data is much larger than the available memory or bandwidth, e.g. neural compute models at the edge in a IoT device, word databases on limited memory systems, and foveated compression in VR/AR on super high bandwidth connections that still cannot keep up with the 16K video stream given modern video protocols.
Anytime you're trying to squeeze more performance out of old/underpowered embedded hardware you'll come across stuff like this...
Eg. You work for a doorbell company and the boss says "yo, can we make our doorbell have 6 tunes instead of one, because our competitors are doing that. No, we don't want to change microcontroller".
At transit app, we built a domain specific compression for transit schedules. So instead of a city like New York taking 100mb, it takes like 5mb or so. This was a couple years back when data was still more expensive, so one of the things it allowed is simply always downloading schedules for offline availability, instead of having to ask the user when and what to download. Here's a write up (sorry for the cheery tone) with some details
Yes! Not only is it a real thing, but with Moore’s Law slowing down, data/compute appetites going up, and the gap between processing speed and memory speed still large and growing, the need for task specific compression is currently going up.
Working on GPUs, I see many, and work on some task specific compression ideas as part of my job. The compiler has it’s own ways of compressing code & debug info. The hardware has it’s own ways of compressing textures. A recent feature we built on my team is a compressed encoding for adaptively subdividing curves. All of these things have the primary goal of reducing memory bandwidth, which in turn increases the speed of computation because memory is so frequently the main bottleneck.
Of course. For instance when you have an embedded controller with limited ROM size and you run out of space, compressing the message strings that are sent to a till roll printer or display might be the only way you can get enough space to add a feature.
I had to do this in the early '80s. The alternative was scrapping the boards and redesigning them to allow double the EPROM size but that would have been a lot more costly than writing the decompression routine and manually compressing the strings. It would also have delayed delivery.
I imagine only having to store 5 bits for the differences accounts for a large swath of the savings. With the first letter bucketing the rest of the words in a sort of trie-like behaviour, I wonder if there's enough duplication of successive characters for a full trie to be worth it. After all, there would need to be extra bits used to store leaf/node identity, as well as whether there are _more_ nodes past the current leaf. I suppose instead of using markers to denote ends, the parent node could store a count, but that might be wasteful for buckets at the fourth character.
That's what I was thinking, too. Are compression algorithms for Sets a thing? Might be useful for compressing JSON, because the key-value pairs are a Set.
>The Answers could be stored as a bitmap of length 12972, which would be 1622 bytes. But this would make the code for generating a random word more complicated and slower.
You could run RLE on that as well for a decent storage savings.
Another thought: you could order the list of words such that the first 1622 words are answers. That way you don't need to store the answer list and checking is as fast as comparing the value of a memory address. This would probably hurt the differential coding performance though.
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'd need at least 8 bits for the run, making it only beneficial for runs of longer than that.
An alternative would be to make 0 mean five zeros (or some other N) and then if you hit a 1, it means the next 5 bits are to be interpreted as-is. This reduces all 5 length 0s to 1 bit, while only adding 1 bit whenever there is a bit. At worst this introduces 1 extra bit per answer. The answer to non-answer ratio is about 5 to 1, so this should definitely save space while also having a trivial decoding algorithm.
Probably not suitable for direct RLE as you say, but if you looked over the data I suspect you might find that a stepped RLE, where you interleave two or more RLEs could provide a savings. You do of course need a cache to decompress parts of the intervleaved RLE'd data into.
Over on http://golf.horse/ there are leaderboards for finding the smallest Javascript programs that output various word lists, including the Wordle list. I've found it to be a fun and educational challenge. I would be excited to see more submissions!
Hasegawa Sayuri wrote up some notes about their submissions at http://sayuri.tx0.org/golfhorse/, including an extremely elegant and compact encoding of huffman trees.
Interesting that page suggests that the wordle dictionary is 'at most 11.11 bits per word', which works out to 18015 bytes, slightly higher than was achieved here.
Golf.horse is measuring the payload plus the compressor, which I don't believe the author is doing, and is important when trying to be objective about the relative strength of solutions. Otherwise you can store the entire file out of band in the compressor, emit 1 bit in the output file, and then the compressor just returns the expected value on 1 and throws an error on 0 saying the file was corrupt.
The other major difference is that golf.horse requires the payload to be valid uft8 javascript, which means your binary blobs are essentially limited to base64 encoded strings. You might manage slightly better, but I suspect the limit is somewhere around 6.5bits per byte.
On the gameboy, you have the advantage of being able to use the full 8 bits per byte.
(Replace 0x80 with 0x7c to account for ES6 template literals.) The characteristic polynomial for this recurrence has a positive root of 144.61 (or 141.12 for literals). This means that you can actually put quite more than 7 bits per byte in a valid JS code, provided that your decoder is negligibly small enough. Indeed, there exists an encoding that allows exactly 7 bits per byte by using two-byte-long UTF-8 sequence as an escape code [1].
I wonder why the first letter is used on its own. Getting the first letter in 5 bits + 3 bits out of the second should make the first array much more densely populated. Maybe making the further lists more sparse offsets the gains?
$ grep '^[a-z]\{5\}$' /usr/share/dict/words | python -c '
> from sys import stdin
> from os import write
> N = 26 ** 5
> data = bytearray((N+7)//8)
> for l in stdin:
> b = 0
> for c in l.strip():
> b *= 26
> b += ord(c)-ord("a")
> data[b//8] |= 1<<(b%8)
> write(1, data)
> ' | gzip | wc -c
12126
decompression code costs extra. Though I imagine someone has a small gunzip implementation somewhere.
The memory requirements for inflate are (in bytes) 1 << windowBits
that is, 32K for windowBits=15 (default value) plus about 7 kilobytes
for small objects.
This example above is the entire dict file, not the wordle file, so it might be worth looking at this.
I'd have to check the version history, but while 15 bits is the default it's also the maximum, and you can go down to 8. Hardware has gotten a lot faster.
I haven't done any noodling with compression in some time and I'm tempted to sit down and try this. But I think he must be using a different list than I can find because the numbers don't quite add up.
Any time you are tasks with crushing the living daylights out of an unordered list, always, always look at suffix sorting as an option. It might not work out as useful, but it's frequently worth the cost of checking.
I will say that given that a delta encoding was settled on, bitpacking the words first is probably a mistake, and multiplication should have been used instead. For instance using multiplication you can store the words in 24 bits without chopping off the first character and using pointers to them. That may seem a small difference but it makes the deltas he's looking at narrower. So instead of choosing 8 words in 8 bytes versus 10 words in 8 bytes, it could be 8 vs 11, possibly 12.
It looks like the reliance on 5 bits per character versus using 26*5 is that a lot more of his deltas get an extra character.
He is encoding 7 bits per byte, so there are about 172 words that spill over into the next byte due to this.
With 5 bits per letter, if the second to last character shifts by more than 4, then it automatically spills over. With 26, it also depends on how much the last letter also varies.
The linked GBC version is my fork with some improvements (and more in the works).
The current published release uses a similar compression approach by zeta_two, but in current builds I've switched to the compression by arpruss since total data + decompression code size is now a couple hundred bytes smaller.
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 the same). You can "skip encode" (I don't know the formal name for this technique) into 1232 bytes by encoding runs of three [0, 0, 0] as [0], and anything else as [1, X, X, X], saving another 390 bytes.
I tried all combinations of runs between 1 and 7, and 3 is optimal.
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 EDCBA: 16949.00 bytes
With alphabet order tweaked, assembling letters EDCBA: 16309.00 bytes
Where tweaked means you build your offset as if each position was ordered like this ([::-1] means reverse if you're unfamiliar with Python).
You can also use a prefix rather than variable length encoding, this means you can use 2 bits to represent a number bigger than 2^14, rather than 3. This might hurt your ability to decode though, as you'll have bits that cross byte boundaries.
You can get much smaller using length 3 varints rather than 7 (13,110 bytes), but I presume that would perform worse on GB hardware than staying byte aligned.
I got nerd sniped and compressed it to under 28K, which was good enough for the goal of fitting it in a 32K NROM cartridge for the NES. On the NES, you don’t need to do better than that, because you get a separate 8K for graphics, and 4K is plenty of space to fit the code for your Wordle clone.
I’ll put one sometime relatively soon, got some other stuff on my plate. The Wordle clone is currently “mostly functional”—no pretty graphics or anything, but gameplay checks. I have a limited stamina for NES programming, but I had fun with the proof of concept.
I once came across a calculator-like device that had some version of a Bible stored in it. But not very well. It clearly had a dictionary with the text stored by word number, because some of the longer words were off by one word in the dictionary. This produced some strange texts.
When I was a kid my parents had some bible (plus other books) software for their PC XT that came on dozens of 360K floppies and filled most of the 20MB hdd. What impressed me most was the search feature, and I've never seen anything like it since. You could search for a word within N words or N verses of another word, for example. I always wondered what indexing structures allowed that on an 8MHz 8088.
There is probably a bloom filter that covers all 26*5 possibilities with no false positives but that's somewhere over 10 bits per element or 16215 bytes not counting the encoder.
Might be a perfect hash waiting in there somewhere.
With 5 bits per letter, you have 6 symbols left over. We can use those to represent alternate pairs like "A or E", so you can encode BANDS and BENDS at the same time. Looks like if you pick the 6 highest frequency replacements for each starting letter, you can reduce the full word list size by ~2k words.
A naive lookup table for the replacements is 26 * 2 * 6 = 312 bytes.
Many times you don't even need to store the individual letters, just the pairings, and if you are permitted to prune out troublesome words from your dictionary, all the better.
However, this doesn't beat general Brotli encoding of a ASCII trie representation, which gets down to 14,180 bytes (but needs an experience decoder), but goes to show general purpose compression is still really really good these days.
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).
Roadroller [1] is probably a borderline general purpose compression algorithm, and with some automatic parameter tuning it results in 12,170 bytes estimated, at the expense of a lot of memory. "Estimated" because the algorithm was originally meant to be recompresssed in a ZIP file, so it doesn't bother to generate the smallest JS file in terms of uncompressed size (yet). But that estimation does include the decoder size so it is a good estimate for the Kolmogorov complexity of the generated code though.
[1] https://lifthrasiir.github.io/roadroller/ (the exact parameters: golf.horse dataset; input mode text; action write to document; # contexts 12 with 12,15,49,50,70,79,96,97,131,154,292,353; pollute the global scope; max memory usage 150 MB; precision 16; learning rate 1333; model max count 11; model base divisor 14; dynamic model flags -1; # abbreviations 64)
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 characters later), which is an odd quirk of compression algorithms that my brain will never quite grasp.
My best algorithm attempt + Brotli achieved 12,773 bytes, which is a painfully close 542 bytes away. It is 13,181 bytes raw though, and can technically be used in-memory, which is definitely a perk.
> It compresses better with new lines than if you remove them all (given you could just split on every 5 characters later), which is an odd quirk of compression algorithms that my brain will never quite grasp.
New lines give a usable context (namely the word boundary) to compression algorithms. If I give you an arbitrary unsorted list of 5-letter-long words with no delimiters you need to think harder to figure out that it is indeed a list of 5-letter-long words. Same for the compression algorithm.
> My best algorithm attempt + Brotli achieved 12,773 bytes, which is a painfully close 542 bytes away. It is 13,181 bytes raw though, and can technically be used in-memory, which is definitely a perk.
Yeah, the best solution depends on what you want to do with that. Your estimation is not too far from my experience: Roadroller tends to be on par with or slightly smaller than Brotli. Of course, Roadroller exists because web browsers generally don't provide a way to use Brotli in JS ;-)
Arithmetic coding is a drop-in replacement for Huffman coding that saves binary roundoff. It's less known because it was patented, and the (short) code to implement requires optimizing a tricky 1.0000 versus 0.9999 issue (in binary).
The usual application involves letter frequencies without context. Rather than a trie for deterministic context, one could in far less space compute a hidden Markov chain of small but effective dimension, to generate the probabilities for arithmetic coding.
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 and efficient decoder that isn't taking up more space than its saving.
This list is a lot shorter, so there will be fewer opportunities for savings. On the other hand, all words are five letters, so the ‘is a word’ bit can be taken out.
I guess a strategy for compressing a word set could be to compile a regular expression recognizing it using a good regex engine and to then construct a compact representation of the resulting automaton.
I generated a DAWG with 12,822 nodes, which means you need 14 bits for each pointer. A trie representation can be packed much smaller because you don't need to randomly jump around the graph, you can just read it out sequentially.
With huffman coded labels and offsets, I got the size down to approximately:
- 94,761 bits for offsets.
- 56,900 bits for labels.
- 12,822 bits for indicating when you're at the end of a next chain.
I feared that (“This list is a lot shorter, so there will be fewer opportunities for savings”)
However, I think you can layout the tree so that no pointers point backwards. If so, can you make those offsets smaller by making them relative to the current point in the tree?
Also, since the list only has five-letter words, for the last letter, you don’t even need the letters themselves, just 26 bits for what letters can complete a word. That might be a saving.
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 extent that would be needed. Even a hypothetical and cheated DAWG I came up with is ~33% bigger than alternatives. I've generally explored enough (see the paper in my other comment) that I don't feel that further investigations into a DAWG are likely to outperform other methods.
I can't see anything immediately that jumps out that the Crab game is doing that's special to save space, I think it just achieves better compression because you can compress larger files easier, and the words are longer with more overlapping sections.
I agree that you need to compare including the decompressor size, so I'm not sure which approach is better the Huffman trie or the one in the original article. I'm not familiar enough with GB programming to be able to suggest how much program memory would be needed to decode the Huffman Trie, it looks like it would be somewhat similar in complexity.
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.
There's a technique whose name I can't remember, where you take a bunch of words and you produce a much shorter string that has all of the input words in it but overlapping, where the beginning of one word is the end of the previous. Functionally it's like a 1 dimensional word search, and you store pointers into it for all of the individual words.
This morning without putting a whole lot of effort into this, I was able to winnow it down to 27.32 bits per word without any other trickery like 5bit packing. You need at most 1 bit per word to identify the real words, so that's 27.32+1 bits without the bitpacking. Doing 6 bits per letter drops that by 25%.
Now having put too much effort in, I'm around 21.6 + 1 bits per word, (17 bit packed) just by using SSP.
You can probably get better compression by storing the words in a minimized acyclic finite state automaton, since then e.g. shared prefixes and suffixes between words are compressed. Finite state automata can be stored as compact contiguous tables and you can use some of the same tricks as in the article to compress characters on transitions.
The linked post reaches 3.6 bits per byte. E.g. [1] uses finite state automata to reach 1.1 bits per byte for a Scrabble word list and 1.5 bits per byte for an English word list. Both word lists are probably more difficult, since they contain words of varying lengths and long words have less sharing in their pre/suffixes.
What you'd need is a Bloom filter with no false positives in the 26^5 keyspace, and then you'd have to guess random words on startup until you got a hit, which on average would take you 917 guesses.
Which is terrible but still probably faster than the algorithm that the linked article is using, since finding the offset of the kth worth takes O(k) time, and there are 12948 (I still haven't found the mythical 12972 word list).
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 because all words are the same length, N didn't make a big difference).
I achieved a naive size of 20,560 bytes, which I didn't have confidence implementing more advanced techniques outlined in the paper would get the size down sufficiently to compete with using a trie+Huffman representation (15,599 bytes, https://github.com/adamcw/wordle-trie-packing#all-words).
Interesting. Here we don’t care about duplicates though, except that they may indicate we had yet to arrive at the optimal solution.
But it’s possible that you could accidentally make duplicates of one word by pairing others. For a single copy you can omit that word. But if it appears multiple times that represents a compression opportunity that a shuffle to avoid it might destroy.
De Bruijn sequence is more restricted: a cyclic portmontout over a "complete" lexicon of fixed sized words, where every possible string is a valid word.
Strictly speaking, treating the word list as a ring buffer might actually make it a little smaller. Perhaps more importantly, the cycle makes the problem almost exactly analogous to the Traveling Salesman Problem (Although there is an acyclic TSP, it is somewhat lacking in interesting properties like isomorphism)
Does anybody know how much words the Lingo/Motus GB game had ? Can't find the info online. Might be interesting toncompare to the original 1994 version (if it can be decompiled ?!).
169 comments
[ 4.0 ms ] story [ 215 ms ] threadThis sounds like a very wrong approach to optimization. I mean, if you don't know exactly what and how to optimize, or if there's a need for optimization at all, then what are you doing?
I think OP was saying they weren't sure if the original algorithm would be too slow to run under these conditions, and didn't have the ability to test it at the time, so they wrote it in a way which increased the chances of it running quickly considering the system limitations.
Anyway, thinking about the transposing idea some more: this would effectively split the word in to 26² = 625 "buckets" of three-letter suffixes. What we could do to make those still compress decently after transposing is look for shared suffixes in multiple buckets, and ensure they get grouped together in the same order before transposing. This would result in short runs in those suffixes, squeezing some more compression out of it.
... which should also work really well for implicit delta coding.
Hmm... you know, the basic concept here shouldn't be too difficult to implement and try out out, thanks for the ideas! :)
If you have a means of doing RLE that performs otherwise, I'd love to understand how it works.
FYI, turning it into 12972 by 5 and Brotli compressing achieves 15,093 bytes, which is less than if you first turn the data into an ASCII trie then Brotli compress that (14,180 bytes) (Source: https://github.com/adamcw/wordle-trie-packing#all-words).
My only claim in this post is that anything can be pre-sorted if you want to achieve some better DS compression but of course, that means you have to have some map to undo the sorting after you decompress it (and obviously the utility only exceeds the computation time if the documents are longer than the associated dictionaries). The person who wrote the gameboy wordle compression did it by necessity, which is beautiful, and the way people used to do things when you had to fit them into tiny structures like that, so, huzzah! to that person.
But yeah, the observation that you could handle 40% reduction on the first two characters is a good clue.
So much has been missed in lossless image compression, along the same creative lines. We humans can look at an image of a red-black-yellow Cardinal bird sitting on a green-gray stem in the middle of a forest, and basically compress it in our mind in a way you'd have to throw thousands of CPU hours against. If you knew you only had to consider a red bird on a green background, you would have a whole different domain-specific strategy for compression; the amazing thing about our minds is that we can devise that compression strategy from the inputs, remember the strategy for that specific set, and then recall our own compression strategy well enough to decompress the data later.
There was, actually, an attempt in the 90s to do something they labeled "fractal compression" which was more or less an attempt to come up with a lambda function for a particular image; extremely CPU expensive to compress, and might or might not be lossy depending on the goal, but the salient thing was that the compression strategy was unique for each image. That didn't really work out as a commercial concept for a whole host of reasons. But it's one of those corners of extremely clever pre-modern code that might be worth a bundle to revisit now.
So if you wanna code something really, really fun -- consider a fully adaptive compressor that comes up with a specific strategy for each general sub-batch of use cases.
If you want to start a company doing that, let me know because I literally just came up with this idea 12 seconds ago.
This is conceptually similar to what OP does by storing the (numerical) difference between the words. Also, if you have a list of numbers that aren't random, they generally compress better if you turn it into a list of the differences between the numbers.
A simple compression algorithm (miniLZO is apparently 6KB compiled) might be small enough and save enough bytes with compression to make it worth it for OP.
If you want to skim, check out the EXAMPLE section toward the bottom.
29.44% - Original sorted list just compressed with zstd
22.45% - Matching prefix characters from previous word replaced with space
19.38% - Matching prefix characters from previous word removed
Years ago I worked on a J2ME (Java2 Mobile Edition) application that had no business being attempted given the very small archive files allowed. We did it anyway and it actually worked pretty well. We very quickly hit the max file size however, and every feature request meant first shrinking the existing code base to make space. First we had an intern fixing bugs in the code minifier we were using, especially around deleting unused (usually debug) methods. For some reason they rejected on archive size, not payload size, so while I started out doing 'honest' work with shrinking the binary, I had spent a lot of time in college noodling with compression algorithms so my eye was eventually drawn there.
Those were in the days when I could still read JVM assembly code, and shortly after I started thinking about the compression, I realized that the constant pool entries start with the type and then the size of the entry. So while our minifier made the reasonable assumption of sorting the constant pool by type and then alphabetically within it, because most of the constant pool was strings, and strings are variable length, it was hit or miss whether the header would be treated as a run or just Huffman encoded (the fallback). If I suffix sorted, then all but the last string in the pool would be followed immediately by the header for the next string, increasing the average run length.
This ended up knocking almost a kilobyte off of the archive size. Depending on your perspective that sounds like a little or a lot, but in our case each feature cost about 500 bytes, so that change pushed the cliff I was walking toward out almost a month (and slowing the growth rate), just by changing a sort algorithm.
I filed a ticket with Sun about this, but as it turns out they already had the dense archive format in flight, and within a couple months my observation was moot because the dense format can compress constant pools across and entire archive, not just a singe file. That was at least an order of magnitude better than what I had.
It's quite likely a lot of the files we use have similar problems in them. Off the top of my head, JSON compression probably would be much higher if we treated it as unordered, and did more aggressive minification particularly for JSON-at-rest. Sorting sibling keys by value instead of by name for instance.
https://developer.nvidia.com/ai-video-compression
Similarly, having to contain the decompression code in the measured result size and it being a relevant contribution is something that only applies in some use cases of compression.
That's why people still write for the Z80: it's a fun toy.
For genetic data, HapZipper beats general-purpose compression. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3488212/
So, yes, actively researched, but you've got to pick a specific task that makes sense. Even small niches are viable; I made a task-specific compressor to strip the essential numbers out of a remote sensor report to make it small enough to squirt to a satellite.
It kinda didn't matter from 2010 on. But one area I've written my own specific "compression" methods in, for the last few years, has been in shipping data in and out of webworkers (in-browser or in Node). This is where there's still enough of a performance penalty on a lot of devices for sending 1MB that in use cases where you're spawning lots of workers to run long tasks, it makes sense to trade time to compression for a smaller transfer size.
https://www.youtube.com/watch?v=izxXGuVL21o&t=21m12s
Eg. You work for a doorbell company and the boss says "yo, can we make our doorbell have 6 tunes instead of one, because our competitors are doing that. No, we don't want to change microcontroller".
https://blog.transitapp.com/how-we-shrank-our-trip-planner-t...
Working on GPUs, I see many, and work on some task specific compression ideas as part of my job. The compiler has it’s own ways of compressing code & debug info. The hardware has it’s own ways of compressing textures. A recent feature we built on my team is a compressed encoding for adaptively subdividing curves. All of these things have the primary goal of reducing memory bandwidth, which in turn increases the speed of computation because memory is so frequently the main bottleneck.
I had to do this in the early '80s. The alternative was scrapping the boards and redesigning them to allow double the EPROM size but that would have been a lot more costly than writing the decompression routine and manually compressing the strings. It would also have delayed delivery.
> Step 2: Each four letter “word” (or tail of a word) can be stored with 5 bits per letter, thereby yielding a 20 bit unsigned integer.
I'm very curious about this.
[One of] the reasons gzip does worse is it also preserves the order of input.
You could run RLE on that as well for a decent storage savings.
Another thought: you could order the list of words such that the first 1622 words are answers. That way you don't need to store the answer list and checking is as fast as comparing the value of a memory address. This would probably hurt the differential coding performance though.
An alternative would be to make 0 mean five zeros (or some other N) and then if you hit a 1, it means the next 5 bits are to be interpreted as-is. This reduces all 5 length 0s to 1 bit, while only adding 1 bit whenever there is a bit. At worst this introduces 1 extra bit per answer. The answer to non-answer ratio is about 5 to 1, so this should definitely save space while also having a trivial decoding algorithm.
https://ibb.co/93CdVWv
Golf.horse is measuring the payload plus the compressor, which I don't believe the author is doing, and is important when trying to be objective about the relative strength of solutions. Otherwise you can store the entire file out of band in the compressor, emit 1 bit in the output file, and then the compressor just returns the expected value on 1 and throws an error on 0 saying the file was corrupt.
On the gameboy, you have the advantage of being able to use the full 8 bits per byte.
[1] http://blog.kevinalbs.com/base122
I'd have to check the version history, but while 15 bits is the default it's also the maximum, and you can go down to 8. Hardware has gotten a lot faster.
only 5 letter words from the dict, not the entire one. check the grep command at the beginning.
Any time you are tasks with crushing the living daylights out of an unordered list, always, always look at suffix sorting as an option. It might not work out as useful, but it's frequently worth the cost of checking.
I will say that given that a delta encoding was settled on, bitpacking the words first is probably a mistake, and multiplication should have been used instead. For instance using multiplication you can store the words in 24 bits without chopping off the first character and using pointers to them. That may seem a small difference but it makes the deltas he's looking at narrower. So instead of choosing 8 words in 8 bytes versus 10 words in 8 bytes, it could be 8 vs 11, possibly 12.
He is encoding 7 bits per byte, so there are about 172 words that spill over into the next byte due to this.
With 5 bits per letter, if the second to last character shifts by more than 4, then it automatically spills over. With 26, it also depends on how much the last letter also varies.
Green usually signifies something is correct. You should have used yellow for misplaced letters instead.
I had CRAN? in the second row, but I lost the game, because it was RANCH.
Found a GBC implementation as well: https://github.com/bbbbbr/gb-wordle
The current published release uses a similar compression approach by zeta_two, but in current builds I've switched to the compression by arpruss since total data + decompression code size is now a couple hundred bytes smaller.
I did some profiling and code size measurements before switching over. https://github.com/bbbbbr/gb-wordle/blob/compress_arpruss/wo...
Speed (and code size somewhat) have improved more since then.
Base bitmap is 12972 bits, or 1622 bytes (your file lists 1619, not sure why it's 3 bytes smaller, but all the same). You can "skip encode" (I don't know the formal name for this technique) into 1232 bytes by encoding runs of three [0, 0, 0] as [0], and anything else as [1, X, X, X], saving another 390 bytes.
I tried all combinations of runs between 1 and 7, and 3 is optimal.
With alphabet in order, assembling letters ABCDE: 17345.00 bytes With alphabet in order, assembling letters EDCBA: 16949.00 bytes With alphabet order tweaked, assembling letters EDCBA: 16309.00 bytes
Where tweaked means you build your offset as if each position was ordered like this ([::-1] means reverse if you're unfamiliar with Python).
``` alpha1 = "abcdestfghijklmnopqruvwxyz"[::-1] alpha2 = "eaioustrbcdfghjklmnpqvwxyz" alpha3 = "aeioustrbcdfghjklmnpqvwxyz" alpha4 = "eaiousthrbcdfgjklmnpqvwxyz" alpha5 = "aeioustryhkbcdfgjlmnpqvwxz" ```
You can also use a prefix rather than variable length encoding, this means you can use 2 bits to represent a number bigger than 2^14, rather than 3. This might hurt your ability to decode though, as you'll have bits that cross byte boundaries.
You can get much smaller using length 3 varints rather than 7 (13,110 bytes), but I presume that would perform worse on GB hardware than staying byte aligned.https://www.moria.us/blog/2022/01/dictionary-compression
The annoying part is that the NES only gives you four background palettes, and you are constrained to use all four of those to color your words.
Might be a perfect hash waiting in there somewhere.
With 5 bits per letter, you have 6 symbols left over. We can use those to represent alternate pairs like "A or E", so you can encode BANDS and BENDS at the same time. Looks like if you pick the 6 highest frequency replacements for each starting letter, you can reduce the full word list size by ~2k words.
A naive lookup table for the replacements is 26 * 2 * 6 = 312 bytes.
edit: oops double counted the reduction
interestingly, the sweet spot is a mix at 30^4 at 16797B
But more likely one of us has a bug in their logic.
Many times you don't even need to store the individual letters, just the pairings, and if you are permitted to prune out troublesome words from your dictionary, all the better.
However, this doesn't beat general Brotli encoding of a ASCII trie representation, which gets down to 14,180 bytes (but needs an experience decoder), but goes to show general purpose compression is still really really good these days.
A lot can be done in 3014 bytes, but what's the difference in code size for the ascii trie vs. a flat list/gzip/brotli?
[1] https://lifthrasiir.github.io/roadroller/ (the exact parameters: golf.horse dataset; input mode text; action write to document; # contexts 12 with 12,15,49,50,70,79,96,97,131,154,292,353; pollute the global scope; max memory usage 150 MB; precision 16; learning rate 1333; model max count 11; model base divisor 14; dynamic model flags -1; # abbreviations 64)
It compresses better with new lines than if you remove them all (given you could just split on every 5 characters later), which is an odd quirk of compression algorithms that my brain will never quite grasp.
My best algorithm attempt + Brotli achieved 12,773 bytes, which is a painfully close 542 bytes away. It is 13,181 bytes raw though, and can technically be used in-memory, which is definitely a perk.
New lines give a usable context (namely the word boundary) to compression algorithms. If I give you an arbitrary unsorted list of 5-letter-long words with no delimiters you need to think harder to figure out that it is indeed a list of 5-letter-long words. Same for the compression algorithm.
> My best algorithm attempt + Brotli achieved 12,773 bytes, which is a painfully close 542 bytes away. It is 13,181 bytes raw though, and can technically be used in-memory, which is definitely a perk.
Yeah, the best solution depends on what you want to do with that. Your estimation is not too far from my experience: Roadroller tends to be on par with or slightly smaller than Brotli. Of course, Roadroller exists because web browsers generally don't provide a way to use Brotli in JS ;-)
The usual application involves letter frequencies without context. Rather than a trie for deterministic context, one could in far less space compute a hidden Markov chain of small but effective dimension, to generate the probabilities for arithmetic coding.
https://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/l... compresses a 780k word list into 175k. That’s about 22% of the size. This accomplishes 27%.
This list is a lot shorter, so there will be fewer opportunities for savings. On the other hand, all words are five letters, so the ‘is a word’ bit can be taken out.
That sounds like a DAG-shaped FSM to me...? At least I can't spot the difference.
I guess a strategy for compressing a word set could be to compile a regular expression recognizing it using a good regex engine and to then construct a compact representation of the resulting automaton.
I based my approach on http://www.wutka.com/dawg.html and http://stevehanov.ca/blog/?id=115.
I generated a DAWG with 12,822 nodes, which means you need 14 bits for each pointer. A trie representation can be packed much smaller because you don't need to randomly jump around the graph, you can just read it out sequentially.
With huffman coded labels and offsets, I got the size down to approximately:
- 94,761 bits for offsets. - 56,900 bits for labels. - 12,822 bits for indicating when you're at the end of a next chain.
= 164,483 bits + Size of Huffman Table = ~20,560 bytes
I assumed I didn't need any bits for indicating end of word, because all Wordle words are length 5.
Meanwhile, bitpacked trie can get down to 15,599 bytes.
https://github.com/adamcw/wordle-trie-packing#all-words
It's not clear to me a path that will compress the DAWG so much that it could cut another 5000 bytes and whatever the Huffman table size is.
However, I think you can layout the tree so that no pointers point backwards. If so, can you make those offsets smaller by making them relative to the current point in the tree?
Also, since the list only has five-letter words, for the last letter, you don’t even need the letters themselves, just 26 bits for what letters can complete a word. That might be a saving.
Also, the crab source code is available (DEC: http://www.gtoal.com/wordgames/gatekeeper/crab.sh.txt, Mac: http://www.gtoal.com/wordgames/jacobson+appel/mac/Crab_sourc.... Both via http://www.gtoal.com/wordgames/scrabble.html)
Both are nice examples of C the way it is intended to be written, or rather, was intended to be written decades ago.
I don’t remember how that stores the data, but it might do a trick you didn’t think of.
And finally, I just realize that, for fairness, you need to look at (data size + decompressor size). Did you do that?
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 extent that would be needed. Even a hypothetical and cheated DAWG I came up with is ~33% bigger than alternatives. I've generally explored enough (see the paper in my other comment) that I don't feel that further investigations into a DAWG are likely to outperform other methods.
I can't see anything immediately that jumps out that the Crab game is doing that's special to save space, I think it just achieves better compression because you can compress larger files easier, and the words are longer with more overlapping sections.
I agree that you need to compare including the decompressor size, so I'm not sure which approach is better the Huffman trie or the one in the original article. I'm not familiar enough with GB programming to be able to suggest how much program memory would be needed to decode the Huffman Trie, it looks like it would be somewhat similar in complexity.
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.
Anybody know what I'm thinking of?
After throwing more words at the Google Wall, it finally allowed that what I'm thinking of is the Shortest Superstring Problem.
This morning without putting a whole lot of effort into this, I was able to winnow it down to 27.32 bits per word without any other trickery like 5bit packing. You need at most 1 bit per word to identify the real words, so that's 27.32+1 bits without the bitpacking. Doing 6 bits per letter drops that by 25%.
Now having put too much effort in, I'm around 21.6 + 1 bits per word, (17 bit packed) just by using SSP.
The linked post reaches 3.6 bits per byte. E.g. [1] uses finite state automata to reach 1.1 bits per byte for a Scrabble word list and 1.5 bits per byte for an English word list. Both word lists are probably more difficult, since they contain words of varying lengths and long words have less sharing in their pre/suffixes.
[1] https://www.cs.put.poznan.pl/dweiss/site/publications/downlo...
Which is terrible but still probably faster than the algorithm that the linked article is using, since finding the offset of the kth worth takes O(k) time, and there are 12948 (I still haven't found the mythical 12972 word list).
NYT source: https://www.nytimes.com/games/wordle/main.4d41d2be.js
NYT removed 6 words from the solutions
agora pupal lynch fibre slave wench
and 19 words from the guessable list
bitch chink coons darky dyked dykes dykey faggy fagot gooks homos kikes lesbo pussy sluts spick spics spiks whore
so that's 12972 - 25 = 12947
I am glad they did that, but I'm not sure I wanted to know that those used to be in the dictionary.
(also you are probably on a list now, but we appreciate your sacrifice)
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 because all words are the same length, N didn't make a big difference).
I achieved a naive size of 20,560 bytes, which I didn't have confidence implementing more advanced techniques outlined in the paper would get the size down sufficiently to compete with using a trie+Huffman representation (15,599 bytes, https://github.com/adamcw/wordle-trie-packing#all-words).
8 * 15,599/64,860 = 1.92 bits per byte.
But it’s possible that you could accidentally make duplicates of one word by pairing others. For a single copy you can omit that word. But if it appears multiple times that represents a compression opportunity that a shuffle to avoid it might destroy.
http://tom7.org/portmantout/
an extension of portmanteau:
https://en.m.wikipedia.org/wiki/Portmanteau
De Bruijn sequence is more restricted: a cyclic portmontout over a "complete" lexicon of fixed sized words, where every possible string is a valid word.