I want to develop a previous answer to Is there a known maximum for how much a string of 0's and 1's can be compressed?.

I've looked at the Hutter Prize and various compression benchmarks. The compression records are graphed below over a 12 year period. The red curve is an exponential fit, which seems to be asymptotic to something much greater than zero (10MB?). The test file (enwik8) is a bulk extract from Wikipedia, and I don't think that Mr Kolmogorov can help us here.

graph

I'm not overtly asking what the limit is. I'm just asking is there (or could there possibly be) a limit to data compression without Mr. Kolmogorov, whilst using contemporary science? Intuitively and as the fitted curve suggests, there must be some limit as the data can't be compressed to 1 bit. Can anyone expand on any research regarding how close we might be to a minimum value for losslessly compressing enwik8? Is another 25% improvement possible? Is there any active research in this field or is the Hutter team leading the world?

  • Shannon entropy does take correlations into account. The source coding theorem states that Shannon entropy is the information content in the sense of number of bits that need to be transmitted in order to communicate with a vanishing error probability. – Yuval Filmus Nov 24 '17 at 10:13
  • Your dismissal of kolmogorov is sad. It does indeed have the answers you are looking for. – Ray Dec 1 '17 at 19:02
  • @Ray I don't understand your sorrow. This isn't a hypothetical question. 1) How can KC possibly apply to natural data? And if it did, everyone agrees that it's not computable anyway so what's the point of mentioning it in a real world example? 3) How can we determine if there is a limit of compression for Hutter Prize's file enwik8? Or how close we might be to it as of today? – Paul Uszak Dec 3 '17 at 2:54
  • You're not the first to think non-computability = impractical or even useless. But it can be useful. In particular to random, "non-algorithmic" data. Do you know what kolmogorov complexity says about the compressability of random data? – Ray Dec 4 '17 at 20:13

For any fixed piece of data, you can create an encoding where that specific piece of data is encoded by 1 (or possibly zero) bits. So yes you can most definitely compress things down to 1 bit. This is, of course, silly. We want to know how the compression algorithm behaves on multiple pieces of data because we want to use the same algorithm (or the same shared piece of data) multiple times.

Any compression algorithm must be bigger on some inputs than the original data. In fact, if you consider every possible input there is no net compression but there might be a net increase in size. So if we look at everything compression isn't even possible. The trick is that some data is more probable than other data and we can design algorithms that are smaller in the probable case. So each individual algorithm only really has a "compression ratio" if you can give a probability distribution over the inputs, then you can say what the expected output size is or what the expected compression ratio is. If your probability distribution has maximum entropy you'll see an expected compression ratio of at least 1. Importantly the entropy of this distribution tells us how much we can compress this sort of data. You don't get to just throw it out; it always applies.

Shannon's source coding theorem tells us what the theoretical limits are for compression algorithms not just compression algorithms on streams of data of a particular sort. Say you have some data with some distribution then you can compute how "good" this compression algorithm is by sampling data and seeing what the compression ratio is on average. Well, this is the same thing as compressing one giant file that meets Shannon's source coding theorem's requirements! So the entropy of the data still tells us how much we can compress it on average.

If your data is such that it's the concatenation of a fixed number of independent fixed size samples then Huffman encoding is optimal no matter what distribution the fixed size samples come from. 1) these properties seldom hold in practice and 2) when they do the optimality will only kick in for very large data. For instance, say you sample a bunch of IEEE double precision floating point numbers from an approximation of a normal distribution. Huffman encoding is technically optimal in this case but you're unlikely to see the same data more than once unless your data set is huge. I think other compression algorithms are known to be optimal for different groups of distributions over data but you'll have to do some digging to find them; I am not aware of any others off the top of my head. So as long as your data has a certain known distribution that fits one of the cases we know the optimal algorithm for AND your data is sufficiently large (or the entropy of your distribution sufficiently low) so as to have this result even be meaningful.

Generally, we don't even know what the distribution of the data is! We can make statistical inferences based on the data we have but properly fitting a probability distribution is a hard problem. Without specifying a probability distribution we don't have a sensible way to specify how good a compression algorithm is. The quality of practical compression algorithms is basically just due to algorithm designers being good at guessing what sorts of distributions your data might be sampled from and also being good at fitting which specific distribution it was sampled from in cases where that makes sense. For instance, the gzip algorithm effectively wagers that your data will have repeated values in it (especially after some transformations are performed on it). This is clearly just a guess the designers made but it happens to be a damned good guess in practice. If you assume that your data is a stream of independently sampled symbols from the same distribution then you can fit the distribution and construct a Huffman encoding for the data; this has a lot of flaws in practice but it's a lot better than nothing in practice as well. There is no reason in general that that has to be true.

So is there a limit? Well given the only consistent notion of a "compression ratio" that I know of the answer is given by Shannon's source coding theorem.

  • You've made this sound as if you can just run a little equation (Shannon's) and calculate a max. compression. This is so clearly wrong and flies in the face of all the evidence. How do you explain that gzip is rubbish compared to better algorithms, the existence of the Hutter Prize and that NIST doesn't recognise Shannon for entropy measurement? – Paul Uszak Nov 24 '17 at 11:16
  • 3
    Like I said, we generally don't know the distribution our data is sampled from so we can't calculate entropy generally. The reason one algorithm is better than another is mostly just that one guesses the distribution of data a bit better and/or exploits that distribution better. We can sample a bunch of data and use that to get a good empirical guess as to how good an algorithm is but we can't generally calculate the entropy of our data. Empirical results don't tell us theoretical limits. You asked for the theoretical limit. There's no real way to measure this limit in practice, unfortunately. – Jake Nov 25 '17 at 18:10
  • So in a few years time, I'll be able to compress my entire 1TB hard drive of educational material down to 1KB as the algorithms get better? – Paul Uszak Dec 4 '17 at 22:57
  • 2
    I wouldn't say that. If we look at entropy of files on everyone's hard drive I'd guess there is far far far more than 1KB of entropy. – Jake Dec 4 '17 at 23:47
  • This is a very good answer. Nitpick: Huffman encoding is only optimal if the probabilities are rational with power of two denominators or if you restrict yourself to prefix-free setting. – Solomonoff's Secret Aug 9 at 23:18

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.