7 ms·

Minimalist Guide to Lossless Compression (2019)

99 points by marklit 5y ago

efficientsticks 5y ago
Could anyone explain why LZ77 is preferred by implementors versus LZ78? It seems important for compressibility to prepare the data for maximum self-similarity, in addition to the LZ algorithms (as evidenced by the sort in this article). Could someone point towards a good modern summary of the approaches or heuristics?
- commandlinefan 5y ago
  I was going to answer "patents" because that's what I had read in the past (that LZ '78 was encumbered by patents while LZ '77 was not), but this wikipedia talk page: https://en.wikipedia.org/wiki/Talk:LZ77_and_LZ78#preference_of_LZ77_versus_LZ78_algorithms https://en.wikipedia.org/wiki/Talk:LZ77_and_LZ78#preference_... suggests that it's not just patent encumbrances.
- pornel 5y ago
  LZW just doesn't compress that well. In LZW you only can use a dictionary built gradually from length-limited scraps of the previous data, but in LZ77 you can directly reference any of the previous data of any length (within implementation limits).
absoflutely 5y ago
>Entropy, an Information Theory term coined by Claude Shannon in 1948, describes the minimum number of bits, on average, needed to encode a dataset. Shannon didn't coin the term entropy. He borrowed it from the analogous definition in thermodynamics.
greypowerOz 5y ago
>"Also, consider that if you can only read at 100 MB/s off a mechanical drive but your CPU can decompress data at ~500 MB/s then the mechanical drive is able to provide 5x the throughput you'd otherwise expect thanks to compression." I'd not really thought of that aspect before... My old brain is hard-coded to save cpu cycles ... Time to change my ways :)
- magicalhippo 5y ago
  Everything old is new again, so maybe you're just in time. Consider we have NVMe drives which can read and write 4-5 GB/s[1], that whole equation changes again... [1]: https://www.anandtech.com/bench/SSD21/3017 https://www.anandtech.com/bench/SSD21/3017
  - 1_player 5y ago
    zstd at compression level 1 can do ~2GB/s per core, and as time goes on and processors get more and more cores, compressing data by default is a valid proposition. In fact, if you install Fedora 35 on btrfs, zstd:1 is enabled by default, using fs-level heuristics to decide when and when not to compress, reducing write amplification on SSD drives and gaining some space for free with negligible performance impact, which is nice. My 8GB ~/src directory on encrypted btrfs on NVMe uses 6GB on disk and I can easily saturate the link while reading from it. Computers are plenty fast.
    - magicalhippo 5y ago
      > zstd at compression level 1 can do ~2GB/s per core So unless you can multithread that workload, it's already behind by a factor of 2. > Computers are plenty fast. My point was you can no longer assume the disk is significantly slower, at least for streaming workloads. You can often still win by spending CPU cycles doing clever stuff, but it's not several orders of magnitude difference like it used to be.
      - willis936 5y ago
        Most zstd implementations are multithreaded for single compression and decompression tasks. My home server has 24 cores and is using 16x PCIe 3.0 for storage (16 GB/s). Through benchmarking I found that I am storage bound from zstd-3+ and compute bound from zstd-2 and zstd-1. I run zstd-3.
        1_player 5y ago
optimalsolver 5y ago
Lossless compression is apparently equivalent to general intelligence: http://mattmahoney.net/dc/rationale.html http://mattmahoney.net/dc/rationale.html
- selfhoster11 5y ago
  FLAC isn't turning into Skynet that soon. Besides, humans are lossy. We forget, make mistakes, think via heuristic.
- pornel 5y ago
  Yes, but the compression process can be split into two components: 1. modelling (you convert data to symbols and predict probabilities of seeing each symbol) 2. entropy coding (convert symbols + probabilities to minimum number of bits) The second stage is relatively simple, and basically solved. We went from Huffman's approximation to Arithmetic Coding which is theoretically ideal, and now got ANS which is close to ideal and pretty fast too. The modelling part is indeed a completely open problem, and at this point as much art as science.
  - Jasper_ 5y ago
    Most compression codecs these days have stopped using ANS because the benefits aren't worth the tradeoffs. Turns out a good arith coder is much faster.
    - hexxagone 5y ago
      "Turns out a good arith coder is much faster". Citation needed.
tobijdc 5y ago
Doesn't LZFSE stem from the Finite State Entropy library Yann Collet (LZ4, ZSTD) wrote as a base for ZSTD (together with HUFF0) and Apple just decided to use it before it was fully mature? So shouldn't LZFSE be a predecessor to ZSTD in the Tree?

99 points by marklit 5y ago

Could anyone explain why LZ77 is preferred by implementors versus LZ78? It seems important for compressibility to prepare the data for maximum self-similarity, in addition to the LZ algorithms (as evidenced by the sort in this article). Could someone point towards a good modern summary of the approaches or heuristics?

commandlinefan 5y ago
I was going to answer "patents" because that's what I had read in the past (that LZ '78 was encumbered by patents while LZ '77 was not), but this wikipedia talk page: https://en.wikipedia.org/wiki/Talk:LZ77_and_LZ78#preference_of_LZ77_versus_LZ78_algorithms https://en.wikipedia.org/wiki/Talk:LZ77_and_LZ78#preference_... suggests that it's not just patent encumbrances.
pornel 5y ago
LZW just doesn't compress that well. In LZW you only can use a dictionary built gradually from length-limited scraps of the previous data, but in LZ77 you can directly reference any of the previous data of any length (within implementation limits).

absoflutely 5y ago

>Entropy, an Information Theory term coined by Claude Shannon in 1948, describes the minimum number of bits, on average, needed to encode a dataset. Shannon didn't coin the term entropy. He borrowed it from the analogous definition in thermodynamics.

greypowerOz 5y ago

>"Also, consider that if you can only read at 100 MB/s off a mechanical drive but your CPU can decompress data at ~500 MB/s then the mechanical drive is able to provide 5x the throughput you'd otherwise expect thanks to compression." I'd not really thought of that aspect before... My old brain is hard-coded to save cpu cycles ... Time to change my ways :)

magicalhippo 5y ago
Everything old is new again, so maybe you're just in time. Consider we have NVMe drives which can read and write 4-5 GB/s[1], that whole equation changes again... [1]: https://www.anandtech.com/bench/SSD21/3017 https://www.anandtech.com/bench/SSD21/3017
- 1_player 5y ago
  zstd at compression level 1 can do ~2GB/s per core, and as time goes on and processors get more and more cores, compressing data by default is a valid proposition. In fact, if you install Fedora 35 on btrfs, zstd:1 is enabled by default, using fs-level heuristics to decide when and when not to compress, reducing write amplification on SSD drives and gaining some space for free with negligible performance impact, which is nice. My 8GB ~/src directory on encrypted btrfs on NVMe uses 6GB on disk and I can easily saturate the link while reading from it. Computers are plenty fast.
  - magicalhippo 5y ago
    > zstd at compression level 1 can do ~2GB/s per core So unless you can multithread that workload, it's already behind by a factor of 2. > Computers are plenty fast. My point was you can no longer assume the disk is significantly slower, at least for streaming workloads. You can often still win by spending CPU cycles doing clever stuff, but it's not several orders of magnitude difference like it used to be.
    - willis936 5y ago
      Most zstd implementations are multithreaded for single compression and decompression tasks. My home server has 24 cores and is using 16x PCIe 3.0 for storage (16 GB/s). Through benchmarking I found that I am storage bound from zstd-3+ and compute bound from zstd-2 and zstd-1. I run zstd-3.
      - 1_player 5y ago

optimalsolver 5y ago

Lossless compression is apparently equivalent to general intelligence: http://mattmahoney.net/dc/rationale.html http://mattmahoney.net/dc/rationale.html

selfhoster11 5y ago
FLAC isn't turning into Skynet that soon. Besides, humans are lossy. We forget, make mistakes, think via heuristic.
pornel 5y ago
Yes, but the compression process can be split into two components: 1. modelling (you convert data to symbols and predict probabilities of seeing each symbol) 2. entropy coding (convert symbols + probabilities to minimum number of bits) The second stage is relatively simple, and basically solved. We went from Huffman's approximation to Arithmetic Coding which is theoretically ideal, and now got ANS which is close to ideal and pretty fast too. The modelling part is indeed a completely open problem, and at this point as much art as science.
- Jasper_ 5y ago
  Most compression codecs these days have stopped using ANS because the benefits aren't worth the tradeoffs. Turns out a good arith coder is much faster.
  - hexxagone 5y ago
    "Turns out a good arith coder is much faster". Citation needed.

tobijdc 5y ago

Doesn't LZFSE stem from the Finite State Entropy library Yann Collet (LZ4, ZSTD) wrote as a base for ZSTD (together with HUFF0) and Apple just decided to use it before it was fully mature? So shouldn't LZFSE be a predecessor to ZSTD in the Tree?