lyncd

Innovation in Lossless Compression: Apple’s LZFSE, Google’s Brotli and Yann Collet’s Zstandard

With Google’s recent open-sourcing of Brotli following on the heels of Apple’s announcement of LZFSE, it’s an exciting time in the lossless compression world, as new compression schemes tuned for specific use cases now appear to offer substantial enough benefits to challenge the venerable ZIP/Deflate as the Internet’s transport compression algorithm of choice.

Of course, Deflate and its most widespread implementation, zlib, aren’t dead yet, not by a long shot. But what these new LZ77 algorithms offer is significant enough performance gains to justify widespread implementation, and adoption by the W3C. And they have the backing of companies such as Google and Apple, which means they’ll ship on tens of millions of devices and browser installs.

For online encoding and decoding — i.e. transport encoding — where encode/decode speed are critical, Zstandard and LZFSE offer substantial performance/energy usage improvements over Deflate, while roughly matching its compression ratio, by employing finite state entropy (FSE) coding in place of older Huffman and arithmetic methods.

For offline encoding and online encoding — i.e. static Web assets, or APKs on Android — Brotli offers 20% or greater improvement in compression ratio versus Deflate while providing slightly improved decode speed.

(For pure offline compression use cases, such as file archives, LZMA and ZPAQ provide still higher compression ratios at the cost of much longer compression and decompresssion times.)

A subset of Matt Mahoney’s large text compression benchmark (be sure to refer to his current benchmark results, I won’t be updating this table) illustrates these key characteristics and tradeoffs:

A quick run-down of each algorithm’s design and anticipated applications:

• Yann Collet’s ZStandard was released in January and is perhaps the most interesting of all, since it provides large performance gains over zlib in both compression and decompression, with similar compression ratios. So, its most obvious application is in stream or online compression — i.e. at the network transport layer, but with potential other applications such as filesystem compression (btrfs currently offers LZO and zlib, so Zstandard would offer an attractive middle choice in the performance/compression ratio tradeoff). It’s speed gains versus zlib in decompression (roughly 2x faster) also make it suitable for some offline compression (compress once, decompress many) use cases, such as static assets on the web. Faster decompression also means improved battery life on mobile devices, which leads to …
• Apple’s LZFSE, which from a design standpoint is extremely similar to Zstandard, except developed and tested (and optimized for ARM) by Apple, and now shipping on OS X and iOS. Both algorithms use finite state entropy (FSE) rather than Huffman or arithmetic entropy coding — again, permitting about 2x decompression performance vs. Huffman coding without the high computational cost of arithmetic coding. Both LZFSE and Zstandard are approximately equivalent to zlib level 5, so in terms of pure compression ratio they’re not quite at par with zlib at its commonly use standard level 6 (or at level 9), but they’re essentially close enough and with much higher performance per bit are more attractive for all uses except for offline compression, which brings us to …
• Google’s Brotli, named for brotli. There are already several alternatives to zlib that offer better compression ratios by performing more exhaustive search, at the expense of greater memory usage and cpu time. For instance, Ken Silverman’s KZIP, as well as those available in 7-Zip and AdvanceCOMP have been in use for years, and most recently, Google released Zopfli in 2013, which continues to offer the highest compression ratio of any deflate encoder. So, the new Brotli won’t replace Zopfli or zlib where compatibility with Deflate is required — but it’s shipping in Google Chrome and currently staged to be included in version 44 of Mozilla Firefox. It uses Huffman coding, so decompression performance is similar to zlib.