5 ms·

And far better than gzip compression. Nice work. My takeaway is that context matters - this is not General Purpose Compression, but compression made specificall

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.

deleted 5y ago
[deleted]
noduerme 5y ago
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.
- vanderZwan 5y ago
  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
  - lifthrasiir 5y ago
    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).
    - vanderZwan 5y ago
      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! :)
      - quicktwo 5y ago
        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 https://github.com/adamcw/wordle-trie-packing#all-words).
      - noduerme 5y ago
        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.
davidjohnstone 5y ago
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.
- pronoiac 5y ago
  You might want to look at locatedb and frcode - https://manpages.ubuntu.com/manpages/bionic/man5/locatedb.5.html https://manpages.ubuntu.com/manpages/bionic/man5/locatedb.5.... If you want to skim, check out the EXAMPLE section toward the bottom.
- HALtheWise 5y ago
  Because all the words are five letters here, you should be fine to elide leading spaces in this case.
  - deleted 5y ago
    [deleted]
  - abainbridge 5y ago
    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?
    - ant6n 5y ago
      One newline is probably better than 1-4 spaces.
nerfhammer 5y ago
It's similar to the compression techniques you might use in column store
anyfactor 5y ago
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".
- hamandcheese 5y ago
  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 https://developer.nvidia.com/ai-video-compression
- detaro 5y ago
  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.
- willis936 5y ago
  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.
- psidebot 5y ago
  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.
- morcheeba 5y ago
  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/ 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.

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.

deleted 5y ago

[deleted]

noduerme 5y ago

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.

vanderZwan 5y ago
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
- lifthrasiir 5y ago
  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).
  - vanderZwan 5y ago
    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! :)
    - quicktwo 5y ago
      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 https://github.com/adamcw/wordle-trie-packing#all-words).
    - noduerme 5y ago
      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.

davidjohnstone 5y ago

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.

pronoiac 5y ago
You might want to look at locatedb and frcode - https://manpages.ubuntu.com/manpages/bionic/man5/locatedb.5.html https://manpages.ubuntu.com/manpages/bionic/man5/locatedb.5.... If you want to skim, check out the EXAMPLE section toward the bottom.
HALtheWise 5y ago
Because all the words are five letters here, you should be fine to elide leading spaces in this case.
- deleted 5y ago
  [deleted]
- abainbridge 5y ago
  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?
  - ant6n 5y ago
    One newline is probably better than 1-4 spaces.

nerfhammer 5y ago

It's similar to the compression techniques you might use in column store

anyfactor 5y ago

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

hamandcheese 5y ago
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 https://developer.nvidia.com/ai-video-compression
detaro 5y ago
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.
willis936 5y ago
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.
psidebot 5y ago
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.
morcheeba 5y ago
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/ 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.