Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

alexanderpruss.blogspot.com

Post reply on HN
Print view View original

71–80 of 170 posts

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

#71

Post by justinlloyd »

I love little compression hacks like the one given in the article.

I created a word search game way back in late 1978/early 1979 4KB of RAM. I had about 2KB for storing the word database. And I recall I had about 2,500 words. Which I had to type in by hand.

I used the 26 tables of words trick too, to drop the first letter. I also treated each word being made up of 32 symbols. I called them letters, but they didn't represent individual letters necessarily.

Edit 36 minutes after writing my original comment: Having just checked my notes from December 24th 1978, I need to correct myself and say it was 38 symbols. Though I seem to recall I actually got it down to 32 symbols. I need to keep looking through my notes to refresh my brain on the solution.

A word might end in "ING" so that was considered a single letter/symbol. Words were between four and seven letters long.

Most words took up two bytes, some only took up a single byte, only a few took up three bytes, maybe a few dozen took up four bytes. And I judiciously pruned the database to minimize the words that took up three or four bytes so that I didn't have too many of them. I also packed the bits, so that there was no gaps between words.

And it was all written in 6502 assembly, originally for the CBM PET, and later for the Acorn Atom.

I was 11 years old and so proud of myself for such cleverness. I still have my notes and scribblings, including the digitised versions from all those years back.

Later, when I wrote a much more complex Bookworm type of game I had to take a word list that was about 8MB long, uncompressed, which would just barely fit on the hard drive, and turned it into a trie, which brought it down to just a few dozen kilobytes, which handily fit on a SS/SD 100KB 5+1/4" floppy.

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

#72

Post by [deleted] »

hinkley wrote: post #65

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. Anybody know what I'm thinking of?

[deleted]

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

#73

Post by justinlloyd »

anyfactor wrote: post #25
jagged-chisel wrote: post #3

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.

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".

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.

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

#74

Post by justinlloyd »

voussoir wrote: post #63
anyfactor wrote: post #25

Earlier quoted context omitted.

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".

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. https://www.youtube.com/watch?v=izxXGuVL21o&t=21m12s

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.

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

#75

Post by justinlloyd »

quicktwo wrote: post #61
willis936 wrote: post #14

>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…

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 t…

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.

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

#76

Post by justinlloyd »

corruptio wrote: post #51

oo oo, idea... trying to implement it now: 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. ed…

Hmmm... sounds familiar https://justinlloyd.li/blog/word-search-game-part-two/

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.

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

#77

Post by microtonal »

hinkley wrote: post #65

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. Anybody know what I'm thinking of?

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.

[1] https://www.cs.put.poznan.pl/dweiss/site/publications/downlo...

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

#78

Post by hinkley »

habibur wrote: post #64
hinkley wrote: post #34

Earlier quoted context omitted.

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.

> This example above is the entire dict file, not the wordle fil only 5 letter words from the dict, not the entire one. check the grep command at the beginning.

Right, but it's still many times larger and compresses better.

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

#79

Post by steventhedev »

quicktwo wrote: post #56

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 to 14,180 bytes (but needs an experience decoder), but goes to show general purpose compression is still really really good these days.

brotli on the raw word list gives 17194 bytes. gzip gives 32352.

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?

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

#80

Post by nathell »

There’s a similar algorithm for indexing words in text collections (I know it from the ‘Managing Gigabytes’ book).

Say you want to store the information that the word ‘algorithm’ occurs in documents 42, 2718 and 3141. That’s a sorted list, so as the author notes, you can just store the differences (42, 2676, 423). Those differences can still be arbitrarily large, but if there are many documents, you can expect most differences to be small.

The trick is to store the numbers not as fixed-bit-size integers, but using a variable-length encoding. The algorithm stipulates using a Golomb code with the parameter b = ceil(N / n * ln(2)), where N is the number of documents in total, n is the number of documents containing our word, and ln is the natural logarithm.

For our example, assuming 5000 documents in total, this gives N = 5000, n = 3, b = 1156, and our index entry is 10000101010001010110110010110100111, for a total of 35 bits.

Post reply on HN