Taking a Look at Compression Algorithms
cefboud.github.io
cefboud.github.io
My impression after my own, shallower dive is that trainable dictionaries are an underappreciated part of the (or at least my) system design toolkit.
For example, say you're serving Wikipedia - a bunch of pages that are kind of static. In order to minimize disk space, you'll be tempted to compress the content. Compressing the whole corpus gets a good compression ratio, but it means that, to read an arbitrary item, you need to decompress everything (or 50% of everything, on average, I guess).
So to get random access, you compress each page. That's ok, but you get a worse compression ratio because every compressor starts from scratch.
But with Zstandard and a trainable dictionary, you could train a dictionary on a couple pages, then use that dictionary to compress and decompress arbitrary items.
As far as I can tell, that's probably the best of both worlds - close to the compression ratio of compressing the whole corpus with gzip, but the random access of compressing each item individually.
This seems really generalizable - e.g. maybe Facebook has to store a zillion photos that are very rarely accessed, but 10% of them are selfies. If we use a vector search to find clusters of similar items, we can compress those items with a single dictionary.
In fact, taking another step back, it seems like databases ought to offer this out of the box. Just like the concept of an index, it's not always a win and there are a lot of knobs that you might want to tune, but the benefits seem clear.
Maybe all of this already exists, or there's something I'm missing, but I really appreciate article's like OP's that break things down so clearly.
Entries are stored in-memory/logged (instead of put into a b-tree like classic DB's) and then periodically placed in span-files that are "linear" for faster search, however as these span files are built in bulk it makes more sense to compress blocks of them since much data is handled at once (so even if it's linear it's still blocks and reading just produces more variable size blocks by decompression upon read).
The Brotli algorithm is typical LZ plus a shared dictionary aimed at common web documents and markup. It does work well and fast for HTML. A common criticism is that it's basically targeted at compressing Wikipedia and the dictionary is loaded with a bunch of junk and now every browser needs a copy of that 120 kB of junk some of which will very rarely be used unless you're compressing Wikipedia. (Both "II, Holy Roman" and "Holy Roman Emperor" are tokens in the Brotli dictionary, for example. Whole dictionary here for the curious: https://gist.github.com/duskwuff/8a75e1b5e5a06d768336c8c7c37... )
"I was able to achive a random WARC file compression size of 793,764,785 bytes vs Gzip's compressed size of 959,016,011" [0]
In hindsight, I could have written that up and tested it better, but it's at least something.
[0] https://github.com/benwills/proposal-warc-to-zstandard?tab=r...
What's missing a bit is that the comparison is more for general purpose data, there are some very interesting and super fast compressing algorithms for e.g. numbers (Turbopforc, gorilla, etc...) Daniel Lemires blog is super interesting about the different algorithms and how to make them faster.
Free link to online version http://www.inference.org.uk/itprnn/book.pdf
Back in the 80s and early 90s multiplication was expensive (multiple cycles) while tables were more or less "free" in comparison, today cache-misses are super-expensive (100s of cycles) while multiplications can be run in parallel (MMX,SSE,etc). Sure a huffman table will probably mostly be in-cache but it'll still be at the cost of cache space.
In addition to that various arithmetic encoding methods were patented and thus avoided.
* the graphs - https://gitlab.com/pronoiac/billion-file-fs/-/tree/main/grap...
* the Pareto frontier for compression vs time: zstd -1 and -9, plzip -0, xz -1 and -9. lzop -1 was a bit faster, and plzip -9 a bit smaller, but they had heavy penalties on the other axis.
I wasn't aware of Snappy.
Rolling hashes and bloomfilters would get you a lot more than trying to glean something out of a compressed stream. It's not because compression algorithms use dictionaries that it's the only way to build a dictionary...
So... any links on how it actually works?
https://openlibrary.org/books/OL803861M/The_data_compression....
Is there room for creativity in this field, or has the last juice been squeezed by proving that it can't be done better?
A good deal of the time we care about decompression speeds, or the tradeoff between speed and bandwidth. The algorithms that reigned in the 90's and still kind of reign today are unwieldy. So new techniques that get within a few percent of optimal much faster or using less memory are an easy sell.
And once in a while we get something like Burrows Wheeler which isn't a compression, it's a transform (hence BWT) that can unearth some broader patterns in a file and make them more conducive to being compressed without a large memory structure that grows faster than the data under inspection.
For example, look at Algorithmics on SLP-compressed strings: A survey (https://www.degruyter.com/document/doi/10.1515/gcc-2012-0016...).
Btw, does anyone know of an article or book about GPU texture compression? Would love a good in detail reference.
For example, on my data I have 2x compression rate for lz4 and 7x for zstd somehow.
Then get 4 goals: compression ratio, compression speed, decompression speed and search (which could be split further)
See Algorithmics on SLP-compressed strings: A survey (Markus Lohrey) (https://www.degruyter.com/document/doi/10.1515/gcc-2012-0016...)
Implementation-wise, you probably loose on the first goal, gain on the second and third (simpler, faster implementations), if you make the fourth one easy to implement.