Zstandard – Fast real-time compression algorithm
github.com
github.com
https://hn.algolia.com/?query=zstandard&sort=byPopularity&da...
A great example is this post [2], where he talks about how to correctly implement a Huffman encoder/decoder. It's a lot tricker than it is made to sound in most books. For example, most Huffman codes that are used in practice are length limited, to allow the decoder to use smaller lookup tables. There are a bunch of surprisingly interesting tricks to get that to work well from the encoding side (which symbols do you choose to be smaller than they would be otherwise?).
[1] http://cbloomrants.blogspot.com/ [2] http://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffma...
[1] https://fgiesen.wordpress.com/category/compression/
[2] https://fgiesen.wordpress.com/2018/02/19/reading-bits-in-far...
So, there's an RFC, but it is not standardized, per se. But close enough, for many uses.
IETF working groups are perfectly capable of defining file formats, eg RFC 7468.
ZStandard wasn't developed using the IETF process, that's why it isn't on the IETF Standards Track. PNG likewise is not on the Standards track, whereas Ogg (the container format) is.
This gets more confusing my the minute.
“For our data zstd was giving amazing results even on the lowest compression level. Compression ratio was better than even gzip at maximum compression level, while throughput was a lot higher.”
One nice quality of zstd is that you can adaptively adjust the compression ratio according to load -- i.e., input rate, or available CPU.
However, Zstd recently added “negative” compression levels (i.e., faster than level 1). Compression is more or less comparable to LZ4 (try level -4 or -5, via `—fast 4` or `—fast 5`). Decompression speed will be somewhere between normal Zstd and LZ4.
This lets you use a single format and library in an extremely wide range of situations, where previously you might have used a combination of LZMA and Zlib and LZ4.
It might be small gains, it might be large ones on both transfer size and decompression speed, I'd love to see some tests on this. The best thing is that, if a browser (say Chrome) and a CDN (say Cloudflare) agreed on something like this there would be no need to even to anything on the front-end nor the server side, automatic free benefit for the users.
Anyway, this should ease transitions away from legacy compression formats.
Similarly there's lbzip2 ( http://lbzip2.org ) for parallel bz2.
From my point of view zstd looks like a very interesting alternative to gzip since it's an order of magnitude faster in tests I've seen.
But lz4 seems to still be the champion for raw throughput speed with decent compression, this might change (have changed?) with the negative compression modes in zstd.
It would be interesting to hear from people who've got a bit more hands on experience with zstd in theses contexts.
The dictionary training, would that be applicable on a dataset/volume in a FS context? It would be awesome if for instance I have a dataset for jpg and another for raw-photos and I could get some good compressions for those.
Media usually yields quite bad compression ratios using more traditional compression formats, dedupe can improve this some but usually requires large DDTs (deduplication tables). Could the dictionary training be an alternative in these cases?
For this to work either you need the library to include all of those models, or you have to transmit those models at least once so they can be cached by the recipient.
I don't see why any of the other compression schemes couldn't also use that type of bootstrap mechanism. Obviously it would not be binary compatible with the baseline libraries, but it's seems disingenuous to claim a huge improvement if the bulk of it is coming from just that.
A few things set Zstd's implementation apart.
1. Zstd actually comes with tooling to generate dictionaries (`zstd --train`, `ZDICT_trainFromBuffer()`). No other compressor ships with this capability, even libraries that support using dictionaries. So we use Zstd to create dictionaries at Facebook, even when, for example, the application is using lz4.
2. Both zlib and lz4 treat dictionaries as strictly prefixes to make LZ77 matches into. Zstd additionally can use metadata in the dictionary to prime the entropy stage.
3. Zstd's support for efficiently using dictionaries is much more extensive than other compressors'. Dictionaries are much more a first class citizen in the internals of the algorithm. Zlib implements support for dictionaries similarly to @ot's suggestion. I.e., the dictionary must be parsed/loaded at the beginning of each compression, or (slightly more efficiently) copied from one pre-loaded context into a working context that will then be used by the compression. For very small inputs--which is where dictionaries are most effective--this loading and/or copying can end up being the bulk of the work performed. LZ4 used to work this way, but additional functionality was added--`LZ4_attach_dictionary()`--that let it use the dictionary in place (as a warm-up exercise in a simpler codebase in preparation for doing the same work in Zstd). Zstd includes mature support for maximally pre-processing a dictionary, producing a `ZSTD_CDict`. This object can then be searched in-place with no per-compression set-up work. This lets Zstd use a large dictionary over and over again very efficiently.
Basically the trained dictionary can be thought of as a generic "context" for a compression algorithm. The process of compressing a symbol in any compression algorithm can be summed up with a function: compress(Context, Symbol) -> (New context, Bits[1])
Decompression is always then decompress_symbol(Context, Stream) -> (New context, symbol).
The important thing is that to be able to decompress a symbol, the decompression engine needs to know the exact state of the compression algorithm at each point. It should be obvious why this is necessary. if it's difficult to see why, imagine your entire compression algorithm is trivial: allocate a number to each word in a dictionary, and your compression algorithm is simply to replace each word in the input with the assigned number, it's then obvious that the dictionary the decompression engine uses has to be identical. This is a simplification, but the same logic applies to every compression algorithm. Even a static Huffman table for instance has this semantic - the result of compress(context, symbol) is going to have the same context, but that requires transmission of the static table before any decompression happens.
The illogical extreme for an algorithm is to include a specific entry for specific inputs - for example the "honest" algorithm at https://nerget.com/compression/
1. Note that for some algorithm Bits may technically be a whole number of bits
The docs say that the dictionary is required for both compression & decompression.
Edit: it's not well suited to real-time...
zstd --long=31 -T4 -10
Luckily, as part of the big react grant backlash,it was dropped from zstd as well and now it’s (as far as I understand) also good from a legal standpoint.
> The project is provided as an open-source dual BSD and GPLv2 licensed C library.
I don't understand how this works. "You either contribute back your changes or not". Wouldn't the BSD license be enough for that?
You cannot relicense code you are not the copyright holder of (ignoring public domain, that's a special case).
Just because it is under a permissive BSD license does not mean that you own the copyright; only that the copyright owner permits you to use the material permissively.
You are still unable to re-license it unless you are the copyright owner (or the copyright owner gives you permission to do so, e.g. by dual-licensing the code).
In practice, there's little reason to license under both BSD and GPL since the BSD is compatible with the GPL on its own.
By the way, that might be what you're thinking of; when you have BSD code, you can integrate it into a GPL codebase, but that's not because you're re-licensing it as GPL, but because the GPL is explicitly meant to be compatible with most other free software licenses. You're still using said code under the terms of the BSD, which allow you to use it alongside GPL code.
Presumably what has happened here is that Facebook's lawyers felt more comfortable being more explicit about the intended licenses, though I can't think of a concrete reason why they'd feel the need to do so.
And dump everything else ?