Can data be compressed to size smaller than Shannon data compression limit?

Question

I was reading about data compression algorithms and the theoretical limit for data compression. Recently I encountered a compression method called "Combinatorial Entropy Encoding", the main idea of this method is to encode the file as the characters presented in the file, their frequencies and the index of these characters permutation represented by the file.

These documents may help explaining this method:

https://arxiv.org/pdf/1703.08127

http://www-video.eecs.berkeley.edu/papers/vdai/dcc2003.pdf

https://www.thinkmind.org/download.php?articleid=ctrq_2014_2_10_70019

However, in the first document I've read that by using this method they could compress some text to less than the Shannon limit (They didn't consider the space needed to save the frequency of the characters and the space needed to save the meta data of the file). I thought about it and I found that this method won't be very efficient for very small files but on the other hand it may work well with large files. Actually I don't fully understand this algorithm or the Shannon limit very well, I just know it's the sum of the probability of each character multiplied by $log_2$ of the reciprocal of the probability.

So I have some questions:

1. Does this compression method really compresses files to smaller than the Shannon limit?

2. Is there any compression algorithm that compresses files to less than the Shannon limit (the answer to this question as far as I know is no)?

3. Can a compression method that compresses files to smaller than the Shannon limit ever exist?

4. If combinatorial encoding really compresses files beyond the Shannon limit, isn't it possible to compress the file again and again until we reach the file size we want?

Answer 1

Actually I don't fully understand this algorithm or the Shannon limit very well, I just know it's the sum of the probability of each character multiplied by log2 of the reciprocal of the probability.

Herein lies the crux. The Shannon limit is not some universal property of a string of text. It is the property of a string of text plus a model that provides (possibly context-dependent) probabilities of symbols. It tells us how well that model could compress the text, assuming the model is accurate.

If you use one model to compute the Shannon limit and then a different model to compress, if the second model is more accurate you can beat the original Shannon limit you had computed, but that's not really relevant.

Answer 2

It's trivially simple to show that you can compress below the Shannon limit--take a cheating compressor that has a bunch of common files assigned to tokens. Said files are stored as those tokens. (Obviously, the compressor must be very large, or be drawing on a very large library.)

The compressor will inherently be less efficient at dealing with any file that isn't in it's library, though, as it must in some way distinguish a token from a normal compression.

What you can't do is have a compressor that beats the Shannon limit on all files.

Answer 3

You first apply the model to the data, computing the sequence of probabilities, f.e. $1/2$, $1/3$, $1/6$. Then, to encode each symbol with probability $p$, you need $log_2(1/p)$ bits. And given some particular model, you can't compress data better than the Shannon entropy of probabilities produced by this particular model.

But if you apply another model, you will get another sequence of probabilities. F.e. the letter "u" is rather rare, so its probability over entire text may be 3%, and it's the probability you have to assign to this letter using an order-0 Markov model.

But in English texts, after "q" usually comes a "u", so using an order-1 model, you can assign much higher probability to "u" going after "q", thus improving the compression ratio.

Moreover, some models output less symbols than there are input ones, f.e. LZ77 replaces text repetitions with back-references, so "abababab" turns into "ab[2,8]".

When someone talks about Shannon entropy of some data rather than data compressed by a particular model, she usually means the Shannon entropy produced by an order-0 model, i.e. assigning to each symbol its probability over the entire text. Obviously, you can beat this margin by applying a more sophisticated model to the data.

Answer 4

Another possible interpretation of the text: the given compression algorithm is going to give you better compression of some texts, and worse compression on others. However, users generally care about some kinds of files (HTML pages in English, 80386 machine code) more than others (tables of truly random numbers, meaningless noise selected to minimize repetition). Any compression scheme is going to trade off being better at compressing real-world data with being worse than useless at compressing certain other kinds of strings.