HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
canshannonsizethancompressionlimitsmallercompresseddata

Problem

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:

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

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

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

-
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?

Solution

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.

Context

StackExchange Computer Science Q#97148, answer score: 38

Revisions (0)

No revisions yet.