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

91–100 of 170 posts

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

#91

Post by forgotusername6 »

morcheeba wrote: post #52
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".

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

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.

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

#92

Post by corruptio »

hinkley wrote: post #62
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…

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

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

#93

Post by rasz »

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?

https://en.wikipedia.org/wiki/De_Bruijn_sequence

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

#95

Post by vanderZwan »

noduerme wrote: post #15
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.

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

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

#97

Post by tyingq »

There was as similar discussion about Barclay's bank, and a list of 74,000 numbers:

https://shkspr.mobi/blog/2021/05/the-74000-numbers-of-barcla...

I tried a similar scheme of sorting the list and storing the delta of the previous number:

https://news.ycombinator.com/item?id=28348965

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

#98

Post by justinlloyd »

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.

It doesn't matter how we all started, or how fast we got here, we're here now, in the same place, the adventure only stops, when you don't want to learn new things.

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

#99

Post by justinlloyd »

slim109ya wrote: post #89
iforgotpassword wrote: post #83

Earlier quoted context omitted.

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

Yeah, me too. Mainly D&D character generators.

D&D character generators were fun to write. And remember those name generators? And you could make planet name & planet environment generators, and then solar system generators for Traveller. I threw together a really bad dungeon map designer thing when I bought once of the earliest mice you could get, with the roller ball inside the mouse that you had to take out and clean.

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

#100

Post by NieDzejkob »

jhgb wrote: post #90
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…

> That’s a smart way to represent a trie, with identical ‘tail’ ends of the trie merged into one. That sounds like a DAG-shaped FSM to me...? At least I can't spot the difference.

Yeah, tries are special cases of FSMs, and so are DAWGs.
Post reply on HN