51–60 of 170 posts
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.
edit: oops double counted the reduction
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".
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.
Can we compresses further by optimizing for only testing set membership?
Might be a perfect hash waiting in there somewhere.
I haven't done any noodling with compression in some time and I'm tempted to sit down and try this. But I think he must be using a different list than I can find because the numbers don't quite add up. Any time you are tasks with crushing the living daylights out of an unordered list, always, always look at suffix sorting as an option. It might not work out as useful, but it's frequently worth the cost of checking. I…
He is encoding 7 bits per byte, so there are about 172 words that spill over into the next byte due to this.
With 5 bits per letter, if the second to last character shifts by more than 4, then it automatically spills over. With 26, it also depends on how much the last letter also varies.
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.
Over on http://golf.horse/ there are leaderboards for finding the smallest Javascript programs that output various word lists, including the Wordle list. I've found it to be a fun and educational challenge. I would be excited to see more submissions!
Interesting that page suggests that the wordle dictionary is 'at most 11.11 bits per word', which works out to 18015 bytes, slightly higher than was achieved here. Golf.horse is measuring the payload plus the compressor, which I don't believe the author is doing, and is important when trying to be objective about the relative strength of solutions. Otherwise you can store the entire file out of band in the compressor…
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…
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".
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.
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 ‘is a word’ bit can be taken out.