News for hackers. Stuff that matters.
Re:Zstandard – Fast real-time compression algorithm by olliej on Sunday November 25, 2018 @10:59PM (#18530948)
Ok so they say that small file compression is achieved via a training step to produce a dictionary for subsequent compression/decompression cycles.

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.

Re:Zstandard – Fast real-time compression algorithm by asdfasgasdgasdg on Sunday November 25, 2018 @11:08PM (#18530992)
Those other compression algorithms don't have that feature. If they did have that feature, they would be different than what they are. If they did have that feature, zstd would not claim a big improvement. But they don't, so it does.
Re:Zstandard – Fast real-time compression algorithm by felixhandte on Monday November 26, 2018 @05:15PM (#18537325)
To add to @ot's reply, zlib and lz4 actually do support dictionaries. (Zlib via `deflateSetDictionary()`, lz4 via `LZ4_loadDict()`/`LZ4_attach_dictionary()`.)

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.

Re:Zstandard – Fast real-time compression algorithm by ot on Monday November 26, 2018 @01:42AM (#18531586)
Although not explicitly advertised, it is possible to implement external dictionary compression with both gzip and lz4 by using their streaming interfaces.
Re:Zstandard – Fast real-time compression algorithm by storyinmemo on Monday November 26, 2018 @01:05AM (#18531458)
The dictionary is only useful in independently compressing lots of small data chunks. Tiny files, rows in a database, VCS commits kind of things where each is independently compressed and extricable. If you tarball them so you're compressing ~100kb+, there's really no benefit to the dictionary step.
Re:Zstandard – Fast real-time compression algorithm by igg on Sunday November 25, 2018 @11:47PM (#18531154)
The decompression step on the receiver does not need the knowledge of the pre-trained dictionaries; they are used only to bootstrap the compression step.
Re:Zstandard – Fast real-time compression algorithm by olliej on Monday November 26, 2018 @02:02AM (#18531637)
No, because if I receiver does not know the starting state of the compression algorithm, no matter what the algorithm is, then it cannot decompress.

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

Re:Zstandard – Fast real-time compression algorithm by flaviu1 on Sunday November 25, 2018 @11:49PM (#18531160)
> The result of this training is stored in a file called "dictionary", which must be loaded before compression and decompression

The docs say that the dictionary is required for both compression & decompression.

Re:Zstandard – Fast real-time compression algorithm by igg on Monday November 26, 2018 @12:10AM (#18531212)
Yup, that's correct.