7 ms·

Modern LZ Compression (2019)

122 points by imadr 5y ago

dang 5y ago
Discussed at the time: Modern LZ Compression - https://news.ycombinator.com/item?id=19064791 https://news.ycombinator.com/item?id=19064791 - Feb 2019 (4 comments)
user-the-name 5y ago
"Modern", but uses Huffman coding? No LZ implementation aiming for high compression in the last decade has used Huffman.
- chriswarbo 5y ago
  > For our goal of a high compression LZ variant, we will want to Huffman code our symbols (zstd actually uses FSE, a variant of arithmetic coding to do this, but we will cover that in a future post).
  - user-the-name 5y ago
    But why? Why spend that much effort introducing a method that is basically entirely outdated at this point, and is also fairly complicated?
    - hexxagone 5y ago
      Huffmann is rather simple and hard to beat in decompression speed.
      - vardump 5y ago
        For high entropy data (=somewhat random data), FSE is quite comparable to Huffman in compression speed. For low entropy (lots of high probability symbols, like zeroes), Huffman is about 2-3x faster. But on the flipside, FSE achieves markedly higher compression ratio. I think FSE is worth the speed tradeoff vs Huffman in most cases.
        hexxagone 5y ago
        "FSE achieves markedly higher compression ratio". I do not thin it is true, FSE/ANS achieves slightly better ratios in general. Zstd uses both Huffman (for large alphabets) and FSE (for small alphabets).
      - user-the-name 5y ago
        Arithmetic coding is much, much simpler. And decompression speed is not a limiting factor in most applications of data compression like this.
        hexxagone 5y ago
        "Arithmetic coding is much, much simpler." Let us agree to disagree. "And decompression speed is not a limiting factor in most applications of data compression like this". It depends on the application. Zstd and Brotli are certainly aiming at the fastest decompression speed possible.
        user-the-name 5y ago
        Arithmetic coding can be implemented in as little as maybe ten lines of code. It is far simpler than Huffman coding.
        hexxagone 5y ago
        The Huffman encoding loop is 2 lines and decoding loop is 4 lines of branchless code. Do you have an example of branchless arithmetic encoder or decoder ?
- hexxagone 5y ago
  You mean like zstd and brotli ? Is there any new LZ codec not using Huffman ?
  - retrac 5y ago
    It was my understanding Zstd used neither Huffman or AC but something else: https://en.wikipedia.org/wiki/Asymmetric_numeral_systems https://en.wikipedia.org/wiki/Asymmetric_numeral_systems Edit: It uses a variety of entropy encodings for different data structures, Huffman is one of them. My apologies for the confusing initial comment.
akkartik 5y ago
Does anyone have recommendations for learning the xz format? Particularly as used by the ZIM archival format: https://en.wikipedia.org/wiki/ZIM_(file_format) https://en.wikipedia.org/wiki/ZIM_(file_format)
- adzm 5y ago
  lzmautils / xz utils is probably your best bet. They have some documentation for sure but it's a complicated format so the source is invaluable.
meiji163 5y ago
I wonder if LZ would still be standard, if not for the inertia of gzip/zip? There are surely better and comparably fast algorithms (paq, ppm, etc.)
- axiolite 5y ago
  zip/gzip are LZ algorithms, as mentioned near the top of the article. Based on LZ77 to be exact. Did you perhaps mean LZW (gif & compress), which was based on LZ78? zlib isn't really dominant, today. lzma seems to have overtaken it for anything destined for public distribution.
  - wolf550e 5y ago
    lzma is slow to decompress. Unless the bandwidth / storage costs are the primary concern, zstd has good enough compression ratio and the very fast decompression makes everything much nicer. Built-in threaded compression, long range compression, binary diff, dictionary compression, etc. are a bonus.
    - axiolite 5y ago
      > zstd has good enough compression ratio I never understood zstd. It's basically lzma+gzip+lz4 packed together. Show me any zstd level that has significantly different speed and data size than one of the levels of those three can't match.
      - dnr 5y ago
        Isn't that exactly the point, and why it's so great? It's a single algorithm that's tune-able across that wide range of speed/ratio trade-offs using a single parameter. So you can just use one thing for almost every application instead of picking between three different things. (Yes, I know that one parameter controls multiple different settings internally, so there are multiple dimensions if you're willing to dig that deep.) Anyway, my recollection from looking at benchmarks a while ago: zstd used at similar ratios to lzma compresses in similar time but decompresses much faster, and it's also faster than gzip when set to comparable ratios to that. lz4 is still faster than the fastest zstd modes, and lzma at the most extreme settings still gets better ratios that the best zstd can do. But there's a huge wide swath in the middle where zstd beats them all, and that's quite valuable.
rurban 5y ago
I had to implement recently an oldstyle lz77 en/decoder to handle an old fileformat, and it was surprisingly simple. Even the encoder
retrac 5y ago
There's quite a lot of retro modern LZ activity too! LZ turns out to be amazing on old machines, often only a couple times slower than a block copy. Optimal compressors and control over the algorithm have led to some very tight demos. https://www.brutaldeluxe.fr/products/crossdevtools/lz4/index.html https://www.brutaldeluxe.fr/products/crossdevtools/lz4/index... LZ4 Data Compression - a rather long and in-depth article looking at LZ4 on the 65816 for the Apple IIgs with a decompressor that exploits that processor's block copy. https://github.com/emmanuel-marty/lzsa https://github.com/emmanuel-marty/lzsa - LZSA - a LZ4-like modern LZ that's more efficient both in speed and compression to LZ4 (at least on the 8 bitters it targets) - includes a neat chart of speed/compression trade-offs on a ZX Spectrum with a variety of algorithms
nathell 5y ago
"Managing Gigabytes" by Witten et al is _the_ book that got me into the field of compression back in the day. Granted, it’s a bit dated now as there’s been a lot of progress in the field, but I’d still heartily recommend it to newcomers.
nickdothutton 5y ago
Only partly related, since it deals with a specific type of data (English language Wikipedia), some of you might enjoy reading about the Hutter Prize: https://en.wikipedia.org/wiki/Hutter_Prize https://en.wikipedia.org/wiki/Hutter_Prize
nayuki 5y ago
> First, we just shorten any symbols that are longer than our maximum code length — 11 — to that value. This means that our tree will no longer be a Huffman tree, so we need to do a fixup pass to redistribute the error we've introduced. This can in fact be solved directly and optimally: https://en.wikipedia.org/wiki/Package-merge_algorithm https://en.wikipedia.org/wiki/Package-merge_algorithm ; https://en.wikipedia.org/wiki/Huffman_coding#Length-limited_Huffman_coding https://en.wikipedia.org/wiki/Huffman_coding#Length-limited_...
- pwrrr 5y ago
  I've spend hours trying to understand how you apply this theory. The internet is surprisingly absent of actual examples showing how it's done. The best I've found that explains the packag-merge is this page: https://create.stephan-brumme.com/length-limited-prefix-codes/ https://create.stephan-brumme.com/length-limited-prefix-code...
pwrrr 5y ago
I just made a huffman encoder on the c64, for fun. I need understand how you go from the variable length codes of huffman, to suddenly fixed lenght codes, because you don't want the codes to be above a certain length. hmm...

122 points by imadr 5y ago

dang 5y ago

Discussed at the time: Modern LZ Compression - https://news.ycombinator.com/item?id=19064791 https://news.ycombinator.com/item?id=19064791 - Feb 2019 (4 comments)

user-the-name 5y ago

"Modern", but uses Huffman coding? No LZ implementation aiming for high compression in the last decade has used Huffman.

chriswarbo 5y ago
> For our goal of a high compression LZ variant, we will want to Huffman code our symbols (zstd actually uses FSE, a variant of arithmetic coding to do this, but we will cover that in a future post).
- user-the-name 5y ago
  But why? Why spend that much effort introducing a method that is basically entirely outdated at this point, and is also fairly complicated?
  - hexxagone 5y ago
    Huffmann is rather simple and hard to beat in decompression speed.
    - vardump 5y ago
      For high entropy data (=somewhat random data), FSE is quite comparable to Huffman in compression speed. For low entropy (lots of high probability symbols, like zeroes), Huffman is about 2-3x faster. But on the flipside, FSE achieves markedly higher compression ratio. I think FSE is worth the speed tradeoff vs Huffman in most cases.
      - hexxagone 5y ago
        "FSE achieves markedly higher compression ratio". I do not thin it is true, FSE/ANS achieves slightly better ratios in general. Zstd uses both Huffman (for large alphabets) and FSE (for small alphabets).
    - user-the-name 5y ago
      Arithmetic coding is much, much simpler. And decompression speed is not a limiting factor in most applications of data compression like this.
      - hexxagone 5y ago
        "Arithmetic coding is much, much simpler." Let us agree to disagree. "And decompression speed is not a limiting factor in most applications of data compression like this". It depends on the application. Zstd and Brotli are certainly aiming at the fastest decompression speed possible.
        user-the-name 5y ago
        Arithmetic coding can be implemented in as little as maybe ten lines of code. It is far simpler than Huffman coding.
        hexxagone 5y ago
        The Huffman encoding loop is 2 lines and decoding loop is 4 lines of branchless code. Do you have an example of branchless arithmetic encoder or decoder ?
hexxagone 5y ago
You mean like zstd and brotli ? Is there any new LZ codec not using Huffman ?
- retrac 5y ago
  It was my understanding Zstd used neither Huffman or AC but something else: https://en.wikipedia.org/wiki/Asymmetric_numeral_systems https://en.wikipedia.org/wiki/Asymmetric_numeral_systems Edit: It uses a variety of entropy encodings for different data structures, Huffman is one of them. My apologies for the confusing initial comment.

akkartik 5y ago

Does anyone have recommendations for learning the xz format? Particularly as used by the ZIM archival format: https://en.wikipedia.org/wiki/ZIM_(file_format) https://en.wikipedia.org/wiki/ZIM_(file_format)

adzm 5y ago
lzmautils / xz utils is probably your best bet. They have some documentation for sure but it's a complicated format so the source is invaluable.

meiji163 5y ago

I wonder if LZ would still be standard, if not for the inertia of gzip/zip? There are surely better and comparably fast algorithms (paq, ppm, etc.)

axiolite 5y ago
zip/gzip are LZ algorithms, as mentioned near the top of the article. Based on LZ77 to be exact. Did you perhaps mean LZW (gif & compress), which was based on LZ78? zlib isn't really dominant, today. lzma seems to have overtaken it for anything destined for public distribution.
- wolf550e 5y ago
  lzma is slow to decompress. Unless the bandwidth / storage costs are the primary concern, zstd has good enough compression ratio and the very fast decompression makes everything much nicer. Built-in threaded compression, long range compression, binary diff, dictionary compression, etc. are a bonus.
  - axiolite 5y ago
    > zstd has good enough compression ratio I never understood zstd. It's basically lzma+gzip+lz4 packed together. Show me any zstd level that has significantly different speed and data size than one of the levels of those three can't match.
    - dnr 5y ago
      Isn't that exactly the point, and why it's so great? It's a single algorithm that's tune-able across that wide range of speed/ratio trade-offs using a single parameter. So you can just use one thing for almost every application instead of picking between three different things. (Yes, I know that one parameter controls multiple different settings internally, so there are multiple dimensions if you're willing to dig that deep.) Anyway, my recollection from looking at benchmarks a while ago: zstd used at similar ratios to lzma compresses in similar time but decompresses much faster, and it's also faster than gzip when set to comparable ratios to that. lz4 is still faster than the fastest zstd modes, and lzma at the most extreme settings still gets better ratios that the best zstd can do. But there's a huge wide swath in the middle where zstd beats them all, and that's quite valuable.

rurban 5y ago

I had to implement recently an oldstyle lz77 en/decoder to handle an old fileformat, and it was surprisingly simple. Even the encoder

retrac 5y ago

There's quite a lot of retro modern LZ activity too! LZ turns out to be amazing on old machines, often only a couple times slower than a block copy. Optimal compressors and control over the algorithm have led to some very tight demos. https://www.brutaldeluxe.fr/products/crossdevtools/lz4/index.html https://www.brutaldeluxe.fr/products/crossdevtools/lz4/index... LZ4 Data Compression - a rather long and in-depth article looking at LZ4 on the 65816 for the Apple IIgs with a decompressor that exploits that processor's block copy. https://github.com/emmanuel-marty/lzsa https://github.com/emmanuel-marty/lzsa - LZSA - a LZ4-like modern LZ that's more efficient both in speed and compression to LZ4 (at least on the 8 bitters it targets) - includes a neat chart of speed/compression trade-offs on a ZX Spectrum with a variety of algorithms

nathell 5y ago

"Managing Gigabytes" by Witten et al is _the_ book that got me into the field of compression back in the day. Granted, it’s a bit dated now as there’s been a lot of progress in the field, but I’d still heartily recommend it to newcomers.

nickdothutton 5y ago

Only partly related, since it deals with a specific type of data (English language Wikipedia), some of you might enjoy reading about the Hutter Prize: https://en.wikipedia.org/wiki/Hutter_Prize https://en.wikipedia.org/wiki/Hutter_Prize

nayuki 5y ago

> First, we just shorten any symbols that are longer than our maximum code length — 11 — to that value. This means that our tree will no longer be a Huffman tree, so we need to do a fixup pass to redistribute the error we've introduced. This can in fact be solved directly and optimally: https://en.wikipedia.org/wiki/Package-merge_algorithm https://en.wikipedia.org/wiki/Package-merge_algorithm ; https://en.wikipedia.org/wiki/Huffman_coding#Length-limited_Huffman_coding https://en.wikipedia.org/wiki/Huffman_coding#Length-limited_...

pwrrr 5y ago
I've spend hours trying to understand how you apply this theory. The internet is surprisingly absent of actual examples showing how it's done. The best I've found that explains the packag-merge is this page: https://create.stephan-brumme.com/length-limited-prefix-codes/ https://create.stephan-brumme.com/length-limited-prefix-code...

pwrrr 5y ago

I just made a huffman encoder on the c64, for fun. I need understand how you go from the variable length codes of huffman, to suddenly fixed lenght codes, because you don't want the codes to be above a certain length. hmm...