4 ms·

I always was fascinated by compression. It feels like no big progress was ever made in lossless compression. How would todays best compression algos compare to

by itry 13y ago

I always was fascinated by compression. It feels like no big progress was ever made in lossless compression. How would todays best compression algos compare to the ones used during the times of the C64? And compared to the first zip algorithm implemented in PKZIP?

Sharlin 13y ago
Well, there are clear information theoretic limits on how much you can compress something, so any improvements are necessarily going to be incremental and converging to the theoretical limit. The more special-purpose the compression algorithm, the more assumptions it can make, the better it can perform on the sort of data it's designed for, at the expense of behaving poorly in the general case. Indeed, it can be shown that any possible lossless compression algorithm, on average, will yield an output larger than its input; it's just that most "interesting" data contains plenty of redundancy that's reliably compressible.
- Someone 13y ago
  Also, it often is better to measure an improvement as relative to the maximum improvement possible, rather than as a percentage of the file size. For compression, let's say that the best possible compressor compresses a file to 30% of its size, and the current compressor reaches 50%. Then, an improvement to 45% should not be seen as 'only 5%', or as '10% smaller', but as '25% of the maximum possible improvement'. A follow-on step that gets you to 40% would be a larger improvement of 33%. That, IMO, is a reasonable way to somewhat compensate for the fact that the low hanging fruit gets plucked by those who come first. And yes, there is a problem there. That 'best possible compressor', theoretically, can produce extremely small files. Maybe your Wikipedia dump happens to be equal to the binary expansion of sin(1/e + 34/sqrt(PI)) to a few billion digits, but how are you going to find out? So, for most files, we don't really know what that best compression is.
hornetblack 13y ago
One new thing is that patents on arithmetic compression expired. Libjpeg will use now, but too much software won't understand it.
wolf550e 13y ago
Quite a bit. For excellent introduction to the topic, read this: http://mattmahoney.net/dc/dce.html http://mattmahoney.net/dc/dce.html For fast lossless compressors, see this article using an Apple II to compare the best of today's (LZ4) with what was available when the hardware was popular/new.
ye 13y ago
Compression algorithms are improving. There are compression programs out there that will beat pretty much anything famous like xz, but 99% of the time at the expense of either compression/decompression time or memory. PAQ8PX is a classic example of this - amazing compression ratios, but ridiculously slow. http://www.maximumcompression.com/data/summary_mf.php http://www.maximumcompression.com/data/summary_mf.php http://www.maximumcompression.com/data/summary_mf3.php http://www.maximumcompression.com/data/summary_mf3.php There are programs that can shrink JPG losslessly by 24%: http://www.maximumcompression.com/data/jpg.php http://www.maximumcompression.com/data/jpg.php NanoZip keeps a very good balance of speed and compression ratio, but it's so unpopular, it's not very practical.
wmf 13y ago
The low-hanging fruit was picked long ago, but there has been some interesting recent work like Snappy, PAQ, and Intel's improvements to gzip ( http://mail.madler.net/pipermail/zlib-devel_madler.net/2013-November/003087.html http://mail.madler.net/pipermail/zlib-devel_madler.net/2013-... ).

by itry 13y ago

Sharlin 13y ago

Well, there are clear information theoretic limits on how much you can compress something, so any improvements are necessarily going to be incremental and converging to the theoretical limit. The more special-purpose the compression algorithm, the more assumptions it can make, the better it can perform on the sort of data it's designed for, at the expense of behaving poorly in the general case. Indeed, it can be shown that any possible lossless compression algorithm, on average, will yield an output larger than its input; it's just that most "interesting" data contains plenty of redundancy that's reliably compressible.

Someone 13y ago
Also, it often is better to measure an improvement as relative to the maximum improvement possible, rather than as a percentage of the file size. For compression, let's say that the best possible compressor compresses a file to 30% of its size, and the current compressor reaches 50%. Then, an improvement to 45% should not be seen as 'only 5%', or as '10% smaller', but as '25% of the maximum possible improvement'. A follow-on step that gets you to 40% would be a larger improvement of 33%. That, IMO, is a reasonable way to somewhat compensate for the fact that the low hanging fruit gets plucked by those who come first. And yes, there is a problem there. That 'best possible compressor', theoretically, can produce extremely small files. Maybe your Wikipedia dump happens to be equal to the binary expansion of sin(1/e + 34/sqrt(PI)) to a few billion digits, but how are you going to find out? So, for most files, we don't really know what that best compression is.

hornetblack 13y ago

One new thing is that patents on arithmetic compression expired. Libjpeg will use now, but too much software won't understand it.

wolf550e 13y ago

Quite a bit. For excellent introduction to the topic, read this: http://mattmahoney.net/dc/dce.html http://mattmahoney.net/dc/dce.html For fast lossless compressors, see this article using an Apple II to compare the best of today's (LZ4) with what was available when the hardware was popular/new.

ye 13y ago

Compression algorithms are improving. There are compression programs out there that will beat pretty much anything famous like xz, but 99% of the time at the expense of either compression/decompression time or memory. PAQ8PX is a classic example of this - amazing compression ratios, but ridiculously slow. http://www.maximumcompression.com/data/summary_mf.php http://www.maximumcompression.com/data/summary_mf.php http://www.maximumcompression.com/data/summary_mf3.php http://www.maximumcompression.com/data/summary_mf3.php There are programs that can shrink JPG losslessly by 24%: http://www.maximumcompression.com/data/jpg.php http://www.maximumcompression.com/data/jpg.php NanoZip keeps a very good balance of speed and compression ratio, but it's so unpopular, it's not very practical.

wmf 13y ago

The low-hanging fruit was picked long ago, but there has been some interesting recent work like Snappy, PAQ, and Intel's improvements to gzip ( http://mail.madler.net/pipermail/zlib-devel_madler.net/2013-November/003087.html http://mail.madler.net/pipermail/zlib-devel_madler.net/2013-... ).