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.

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.

Quite a bit. For excellent introduction to the topic, read this: 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.

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

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-... ).

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_mf3.php

There are programs that can shrink JPG losslessly by 24%:

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.