18
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 27
    $\begingroup$ Shannon proved that you cannot compress below the Shannon limit. $\endgroup$
    – Yuval Filmus
    Sep 9 '18 at 18:15
  • 11
    $\begingroup$ You can go below the Shannon limit with lossy compression. Shannon only showed you cannot compress below the limit without losing information. @YuvalFilmus. Like, on an RGB image, you can throw away the low-order bits of the R,G,B components. $\endgroup$
    – smci
    Sep 10 '18 at 4:56
  • $\begingroup$ Relevant: cs.stackexchange.com/a/44643/26146 $\endgroup$
    – Quuxplusone
    Sep 10 '18 at 6:37
  • 7
    $\begingroup$ @smci That's largely irrelevant in any discussion about compression theory. Obviously I can throw away every bit and call it compression. $\endgroup$
    – pipe
    Sep 10 '18 at 12:24
  • 1
    $\begingroup$ Let's say I have a big file like an image. Now in the model I map the entire image to "1" ha..I have compressed below the Shannon limit as the entire image is compressed to "1"...... $\endgroup$
    – Pieter B
    Sep 11 '18 at 8:36
36
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ To make a practical example, if you know your data consists of a single letter repeated N times, you can achieve arbitrarily large compression rates (i.e. going from 10 billions 'a' to a tuple ('a', 10000000) ) $\endgroup$
    – Ant
    Sep 10 '18 at 19:51
12
$\begingroup$

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.

Improve this answer
$\endgroup$
11
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$

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