News for hackers. Stuff that matters.
Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by jagged-chisel on Saturday February 19, 2022 @09:53PM (#30402787)
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.
Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by davidjohnstone on Saturday February 19, 2022 @10:27PM (#30402942)
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 + "le")). In theory a compression algorithm could handle this automatically, but in practice this gives better compression.

This is conceptually similar to what OP does by storing the (numerical) difference between the words. Also, if you have a list of numbers that aren't random, they generally compress better if you turn it into a list of the differences between the numbers.

A simple compression algorithm (miniLZO is apparently 6KB compiled) might be small enough and save enough bytes with compression to make it worth it for OP.

Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by pronoiac on Saturday February 19, 2022 @10:49PM (#30403045)
You might want to look at locatedb and frcode - https://manpages.ubuntu.com/manpages/bionic/man5/locatedb.5....

If you want to skim, check out the EXAMPLE section toward the bottom.

Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by creatonez on Sunday February 20, 2022 @07:29AM (#30405179)
Testing this with zstd -19

29.44% - Original sorted list just compressed with zstd

22.45% - Matching prefix characters from previous word replaced with space

19.38% - Matching prefix characters from previous word removed

Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by hinkley on Monday February 21, 2022 @06:53PM (#30422342)
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 ... by HALtheWise on Sunday February 20, 2022 @01:45AM (#30403754)
Because all the words are five letters here, you should be fine to elide leading spaces in this case.
Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by abainbridge on Sunday February 20, 2022 @11:48AM (#30407045)
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 ... by ant6n on Sunday February 20, 2022 @02:25PM (#30408474)
One newline is probably better than 1-4 spaces.
Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by quicktwo on Monday February 21, 2022 @10:37PM (#30423743)
Is this just a trie, but you reverse all the words first?
Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by nerfhammer on Saturday February 19, 2022 @10:40PM (#30403005)
It's similar to the compression techniques you might use in column store
Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by anyfactor on Saturday February 19, 2022 @10:51PM (#30403054)
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".
Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by morcheeba on Sunday February 20, 2022 @12:48AM (#30403536)
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 made a task-specific compressor to strip the essential numbers out of a remote sensor report to make it small enough to squirt to a satellite.

Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by forgotusername6 on Sunday February 20, 2022 @05:05AM (#30404601)
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 ... by hamandcheese on Saturday February 19, 2022 @10:54PM (#30403079)
One example that comes to mind is some work nvidia has done compressing “video” streams. They do so by capturing your facial movements and reconstructing them on the other side, resulting and massively less bandwidth.

https://developer.nvidia.com/ai-video-compression

Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by willis936 on Saturday February 19, 2022 @10:56PM (#30403087)
Scarcity breeds innovation. Why hand tune a compression scheme for a specific dataset when it is less storage efficient than LZ? You opt to not use LZ when all the memory and compute you have can barely run prefix codes.

That's why people still write for the Z80: it's a fun toy.

Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by noduerme on Sunday February 20, 2022 @01:50AM (#30403765)
It used to be just best practice to shrink down anything over the wire as much as possible. When I started building websites around 1996, every byte counted and you would "optimize" every GIF image carefully to the smallest size you could, taking it down to 256 or 16 or even custom colors - like 6 colors in the VGA spectrum that looked good enough with dithering.

It kinda didn't matter from 2010 on. But one area I've written my own specific "compression" methods in, for the last few years, has been in shipping data in and out of webworkers (in-browser or in Node). This is where there's still enough of a performance penalty on a lot of devices for sending 1MB that in use cases where you're spawning lots of workers to run long tasks, it makes sense to trade time to compression for a smaller transfer size.

Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by ant6n on Sunday February 20, 2022 @04:26AM (#30404418)
At transit app, we built a domain specific compression for transit schedules. So instead of a city like New York taking 100mb, it takes like 5mb or so. This was a couple years back when data was still more expensive, so one of the things it allowed is simply always downloading schedules for offline availability, instead of having to ask the user when and what to download. Here's a write up (sorry for the cheery tone) with some details

https://blog.transitapp.com/how-we-shrank-our-trip-planner-t...

Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by psidebot on Saturday February 19, 2022 @11:36PM (#30403247)
I have designed task specific data structures/compression oriented around memory efficiency. In my experience this starts to crop up when datasets get big enough to trigger cost for performance sensitivity. This is especially true for SaaS offerings, where e.g. an ability to stay under the next RAM doubling can result in serious hosting savings.
Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by londons_explore on Sunday February 20, 2022 @04:24AM (#30404408)
Anytime you're trying to squeeze more performance out of old/underpowered embedded hardware you'll come across stuff like this...

Eg. You work for a doorbell company and the boss says "yo, can we make our doorbell have 6 tunes instead of one, because our competitors are doing that. No, we don't want to change microcontroller".

Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by dahart on Sunday February 20, 2022 @11:34AM (#30406937)
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 ... by detaro on Saturday February 19, 2022 @10:55PM (#30403085)
Depends how specific you want "specific" to be I guess? I.e. we have loads of compression algorithms for different kinds of data. Whereas here we are looking at almost dataset-specific compression (i.e. the only benchmark is how it works for one specific set of data to compress), and there's a sliding scale between the two ends.

Similarly, having to contain the decompression code in the measured result size and it being a relevant contribution is something that only applies in some use cases of compression.

Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by kwhitefoot on Monday February 21, 2022 @05:44AM (#30414214)
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 ... by voussoir on Sunday February 20, 2022 @02:01AM (#30403822)
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

Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by justinlloyd on Sunday February 20, 2022 @02:33AM (#30403949)
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 ... by justinlloyd on Sunday February 20, 2022 @02:25AM (#30403922)
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 ... by noduerme on Saturday February 19, 2022 @10:22PM (#30402924)
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.
Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by vanderZwan on Sunday February 20, 2022 @06:10AM (#30404859)
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 ... by lifthrasiir on Sunday February 20, 2022 @09:52AM (#30406127)
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).
Re:Game Boy Wordle clone: How to compress 12972 five-letter ... by vanderZwan on Sunday February 20, 2022 @11:01AM (#30406667)
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 ... by noduerme on Monday February 21, 2022 @02:41AM (#30412937)
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 ... by quicktwo on Sunday February 20, 2022 @02:15PM (#30408408)
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).