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

131–140 of 170 posts

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

#131

Post by quicktwo »

Someone wrote: post #60

My first thought would be “DAWG”. That’s a smart way to represent a trie, with identical ‘tail’ ends of the trie merged into one. 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 ‘i…

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

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

#132

Post by quicktwo »

Syzygies wrote: post #127
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 ef…

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.

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

#133

Post by quicktwo »

vanderZwan wrote: post #121
lifthrasiir wrote: post #114

Earlier quoted context omitted.

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

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

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

#134

Post by ant6n »

abainbridge wrote: post #125
HALtheWise wrote: post #58

Earlier quoted context omitted.

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?

One newline is probably better than 1-4 spaces.

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

#135

Post by nitrogen »

Animats wrote: post #45

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.

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

#136

Post by bbbbbr »

zackboe wrote: post #41

My flashcart's GB emulator doesn't have a color palette that matched perfectly, but works well enough! https://i.imgur.com/ePtY5Jf.jpg Found a GBC implementation as well: https://github.com/bbbbbr/gb-wordle

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.

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.

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

#137

Post by quicktwo »

steventhedev wrote: post #79
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?

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

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

#138

Post by bbbbbr »

There is also a NES port in the works: https://twitter.com/FG_Software/status/1495400042722897925

And a C64 port: https://twitter.com/roysterini/status/1493540659352985602

A brief quote about compression in the NES port:

https://twitter.com/FG_Software/status/1491044035884371971 "Official #Wordle dictionary implemented, and the game can now select a solution from all those found in the original for the cost of 1 extra bit per word! Uncompressed size (Raw text files): 76060 bytes Compressed size: 26256 bytes"

https://twitter.com/FG_Software/status/1495298243668099073 "Words are stored in 2 bytes: 15 bits data, 1 bit to check if it's a solution. They're all sorted alphabetically, so I can algorithmically determine the first 2 letters with a lookup table, and stick the last 3 letters in 15 bits. Bit more to it but you can't fit it all in a Tweet"

I've been working on a Game Boy Color (and regular GB) fork that in current builds uses the compression by arpruss. https://github.com/bbbbbr/gb-wordle

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

#139

Post by quicktwo »

microtonal wrote: post #77
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 autom…

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

8 * 15,599/64,860 = 1.92 bits per byte.

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

#140

Post by Someone »

quicktwo wrote: post #131
Someone wrote: post #60

My first thought would be “DAWG”. That’s a smart way to represent a trie, with identical ‘tail’ ends of the trie merged into one. 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 ‘i…

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

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.

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?

Post reply on HN