Zstandard – Fast and efficient compression algorithm

Also see corresponding article: http://fastcompression.blogspot.fr/2015/01/zstd-stronger-com...

This looks very interesting. Before everybody starts making the obvious comparisons, note that this is from the same guy that made LZ4, and he is someone who clearly knows what he's doing. I've been following his work for some time.

It looks like this is the evolution of Zhuff, an experimental (closed-source) compressor [1]. It is basically LZ4 followed by a fast entropy coder, specifically FSE [2], that is a flavor of arithmetic coding that is particularly suited for lookup-table based implementations.

From a quick look at the source code it seems that the entropy stage uses 3 probability tables, one for literal bytes, one for match offsets, and one for match lengths. This is not dissimilar from gzip (which however uses Huffman).

EDIT: from a second look it seems that the LZ77 compression stage is basically LZ4: it uses a simple hash table with no collision resolution, which offers very high compression speed but poor match search. I'm surprised he didn't implement (yet?) an HC variant as for LZ4, it could even beat gzip compression rate with no overhead in decompression speed/memory requirements.

[1] http://fastcompression.blogspot.fr/p/zhuff.html

[2] https://github.com/Cyan4973/FiniteStateEntropy

Somewhat interestingly, this would do pretty well, as the semi-fictional [1] Weissman score takes into account both compression speed and ratio.

[1] http://spectrum.ieee.org/view-from-the-valley/computing/soft...

P.S. Yes, semi-fictional is a perfectly cromulent description of this metric.

Please note that the HN community takes a rather strict approach when moderating comments that contribute noise to the conversation. "Nice article!" comments are routinely downvoted. As is sarcasm, witticisms, memes, references and other styles of comments that occur frequently but do not contribute to the discussion. It's a knowingly doomed attempt to hold back the flood of noise that covers Reddit.

Neat.

Google's Gipfeli (https://github.com/google/gipfeli) also aims for compression ratio and time to fall in between gzip -6 and the fastest algorithms. I've only glanced at code; think it includes a Snappy/LZO/LZ4-like repeat matcher using a hashtable, combined with simple-but-fast entropy coding where each literal input byte becomes 6, 8, or 10 bits.

Super cool that Collet's working on still-pretty-fast-but-better compression out in the open.