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

121–130 of 170 posts

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

#121

Post by vanderZwan »

lifthrasiir wrote: post #114
vanderZwan wrote: post #95

Earlier quoted context omitted.

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! :)

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

#122

Post by mzs »

dietrichepp wrote: post #43

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. https://www.moria.us/blog/2022/01/dictionary-compression The annoying part is that the NES only gives you four background pa…

Nice! Do you have a repo somewhere?

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

#123

Post by microtonal »

hinkley wrote: post #81
microtonal wrote: post #77

Earlier quoted context omitted.

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

5.5 bits per word is pretty good. 18 bits per word leaves room to be undercut by a lucky break with a Bloom Filter.

But not for Wordle, since a Bloom filter cannot enumerate items? (So, you can't tell which letters were correct.)

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

#124

Post by dahart »

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

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.

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

#125

Post by abainbridge »

HALtheWise wrote: post #58
davidjohnstone wrote: post #17

Earlier quoted context omitted.

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…

Because all the words are five letters here, you should be fine to elide leading spaces in this case.

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?

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

#127

Post by Syzygies »

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.

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.

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

#128

Post by lucb1e »

I've noticed in the past (trying to optimize traffic for a game with delta compression, variable-length integers, ...) that it's really hard to beat good compression with manual tricks.

Original word list: https://raw.githubusercontent.com/arpruss/gb-fiver/main/comp...

    $
2000 bytes smaller without any optimizations (this even includes the newlines), though now I guess the question is what the size of the xz decompressor is since a few KB actually matter (not like on a regular computer).

For some reason bzip2 gets it only to 36K, even worse than gzip (32K) and zstd (29K).

Update: Counter-intuitively, stripping the newlines (... | tr -d \\n | ...) results in a higher compressed size with xz. It's surprisingly hard to find a minimal xz decompressor, it doesn't seem as though anyone bothers with this stuff. The Hutter Prize includes the decompressor so that was my first stop, but none of the contestants submitted that (I assume they predate xz).

Update#2: Found at least one measurement of xz decompressor at 36K, but it seems to me like this is the general-purpose utility and includes the compressor, help output, etc. http://mattmahoney.net/dc/text.html

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

#129

Post by hinkley »

microtonal wrote: post #123
hinkley wrote: post #81

Earlier quoted context omitted.

5.5 bits per word is pretty good. 18 bits per word leaves room to be undercut by a lucky break with a Bloom Filter.

But not for Wordle, since a Bloom filter cannot enumerate items? (So, you can't tell which letters were correct.)

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

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

#130

Post by rootsudo »

iforgotpassword wrote: post #83
justinlloyd wrote: post #71

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

Man, at 11 my programs mainly consisted of INPUT, PRINT and GOTO, which I wrote on my uncle's brand new IBM XT.

My programs at 11 were just Visual Basic 6 for an IE scrapper/clicker and making HTML websites in Dreamweaver 6.

Not sure why the 6 was so popular for many programs then. It was for sure Photoshop 7 era.

Post reply on HN