Any theoretical limit to compression?

information-theory data-compression compression
David picture David · Dec 2, 2010 · Viewed 13.8k times · Source

Imagine that you had all the supercomputers in the world at your disposal for the next 10 years. Your task was to compress 10 full-length movies losslessly as much as possible. Another criteria was that a normal computer should be able to decompress it on the fly and should not need to spend much of his HD to install the decompressing software.

My question is, how much more compression could you achieve than the best alternatives today? 1%, 5%, 50%? More specifically: is there a theoretical limit to compression, given a fixed dictionary size (if it is called that for video compression as well)?

Answer

Riedsio picture Riedsio · Dec 2, 2010

The limits of compression are dictated by the randomness of the source. Welcome to the study of information theory! See data compression.

Related questions

What is the computer science definition of entropy?

I've recently started a course on data compression at my university. However, I find the use of the term "entropy" as it applies to computer science rather ambiguous. As far as I can tell, it roughly translates to the "randomness" …

Read More
How do I compute the approximate entropy of a bit string?

Is there a standard way to do this? Googling -- "approximate entropy" bits -- uncovers multiple academic papers but I'd like to just find a chunk of pseudocode defining the approximate entropy for a given bit string of arbitrary length. (…

Read More
Optimal way to compute pairwise mutual information using numpy

For an m x n matrix, what's the optimal (fastest) way to compute the mutual information for all pairs of columns (n x n)? By mutual information, I mean: I(X, Y) = H(X) + H(Y) - H(X,Y) …

Read More