Game Boy Wordle clone: How to compress 12972 five-letter words to 17871 bytes • Hacker News Board

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

#151

Post by Someone » Mon, Feb 21, 2022, 7:08 AM UTC

quicktwo wrote: post #142

Someone wrote: post #140

Earlier quoted context omitted.

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…

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…

Thanks for all the informational replies.

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

#152

Post by noduerme » Mon, Feb 21, 2022, 7:41 AM UTC

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…

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.

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

#153

Post by elahieh » Mon, Feb 21, 2022, 9:22 AM UTC

hinkley wrote: post #129

microtonal wrote: post #123

Earlier quoted context omitted.

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

The 12972 are in the old source: https://web.archive.org//web/20220201010250js_/https://www.p...

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

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

#154

Post by kwhitefoot » Mon, Feb 21, 2022, 10:44 AM UTC

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

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.

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

#155

Post by quicktwo » Mon, Feb 21, 2022, 10:26 PM UTC

jepler wrote: post #145

Like y'all, I wanted to see how I could do. Of course, I didn't get all the way to tested code on a gameboy. But it does compress & decompress in Python. I took the central idea of encoding deltas (or actually delta less 1, since the delta is always at least one; I'll just say delta below), but did it on the full five letter word. The largest delta was still less than 2*18 but bigger than 2*17. (I'm not sure why the…

I like your trick of subtracting the prior node size if it's too small, it gets a number of offsets into the lower bucket to save some bits.

I took this technique and made a few changes.

Firstly, I effectively did variable length integer encoding in chunks of 3, this mildly outperformed your hand crafted prefixes.

    self.breaksv = [2**3, 2**6, 2**9, 2**12, 2**15, 2**18, 2**21]
    self.prefixesv = [
       ['0'],
       ['1', '0'], 
       ['1', '1', '0'], 
       ['1', '1', '1', '0'], 
       ['1', '1', '1', '1', '0'], 
       ['1', '1', '1', '1', '1', '0'], 
       ['1', '1', '1', '1', '1', '1', '0']]

Secondly, I made my offsets relative to the overall solution space of 26*5, ordering the words sorting from their ends, and with a little bit of twiddling the order of the alphabet to put common letters near the start:

  alpha1 = "aeioustrbcdfghjklmnpqvwxyz"
  alpha2 = "aeioustrbcdfghjklmnpqvwxyz"
  alpha3 = "aeioustrbcdfghjklmnpqvwxyz"
  alpha4 = "aeioustrbcdfghjklmnpqvwxyz"
  alpha5 = "aeioustrybcdfghjklmnpqvwxz"

  bitmap = []
  for ia, a in enumerate(alpha1):
    for ib, b in enumerate(alpha2):
      for ic, c in enumerate(alpha3):
        for id, d in enumerate(alpha4):
          for ie, e in enumerate(alpha5):
            bitmap.append(e+d+c+b+a in words)

Doing this, and then doing the variable length encoding I got the file down to 13,181 bytes (it was 13,180 bytes, but I needed to add a 7 bit termination string so that you can properly decode the file after you write it to disk, otherwise when the file rounds to the nearest byte you have random 0s that get decoded).

I'm sure with some twiddling of the alphabets some more you could save a few more bytes, but this does better than both Brotli on a ASCII trie and the Huffman Trie by almost 1KB (https://github.com/adamcw/wordle-trie-packing#all-words), so I'm very happy.

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

#156

Post by hinkley » Mon, Feb 21, 2022, 11:34 PM UTC

elahieh wrote: post #153

hinkley wrote: post #129

Earlier quoted context omitted.

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

The 12972 are in the old source: https://web.archive.org//web/20220201010250js_/https://www.p... 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

What in the actual fuck.

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)

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

#157

Post by hinkley » Mon, Feb 21, 2022, 11:38 PM UTC

alisonkisk wrote: post #116

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?

See tom7's portmontout 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.

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)

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

#158

Post by hinkley » Mon, Feb 21, 2022, 11:39 PM UTC

corruptio wrote: post #92

hinkley wrote: post #62

Earlier quoted context omitted.

Since delta encoding is applied after this step, it's probably better to just use 26^5 instead of trying to pack extra things into those bits.

oook did some experiments... just counting the size of the delta streams: 17346B for 26^4 and 16852B for 32^4 (as described above) interestingly, the sweet spot is a mix at 30^4 at 16797B

I've been using the cleaned up list, so it's possible that changes the behavior a little bit.

But more likely one of us has a bug in their logic.

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

#159

Post by hinkley » Mon, Feb 21, 2022, 11:53 PM UTC

davidjohnstone wrote: post #17

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.

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…

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.

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

#160

Post by quicktwo » Mon, Feb 21, 2022, 11:59 PM UTC

lifthrasiir wrote: post #82

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.

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

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.