I know that the answer is no but I'm not sure why. Here's where I started. We know that all data with length $n$ Bits and minimum $1$ Bit can be compressed, either lossless or lossy. But how do I continue? Why is it impossible to compress all the data without loss?
$\begingroup$
$\endgroup$
1
3 Answers
$\begingroup$
$\endgroup$
There are $2^n$ bitstrings of length $n$, but only $2^n-1$ bitstrings of length smaller than $n$. Hence there is no one-to-one mapping which maps every bitstring of length $n$ to a bitstring of strictly smaller length. In other words, for any (lossless) compression scheme there will always be a string which it doesn't compress.
answered Mar 31, 2018 at 9:22
$\begingroup$
$\endgroup$
1
Each string of bits can also be a number.
Then we add pigeonholes. For each possible original message create a pigeon. For a message up to $n$ bits that is $\sum^n_{i=1} {2^i}=2^{n+1}-2$ pigeons.
Now create a pigeonhole for each possible compressed message. If you have to compress (compressed message always has less bits then uncompressed) you only have $2^{n}-2$ pigeonholes.
because $2^{n+1}-2 > 2^{n}-2$ there will be pigeons sharing a hole. With lossless compression this is not allowed.
The reason compression works most of the time is that most messages that we want to compress are self redundant in some way. Compression algorithms look for those patterns and exploit them. However doing this forces other messages (that we don't generate) to become larger when using the same compressor.
answered Mar 30, 2018 at 23:27
-
1$\begingroup$ A more generic way of saying what's in your last paragraph that's more in line with the rest of your answer, is that common lossless compression algorithms make some messages smaller at the cost of making other messages larger than their uncompressed forms. It's just that messages that become larger when "compressed" are unusual in practice (unless they are already compressed). $\endgroup$ Commented Mar 31, 2018 at 1:43
$\begingroup$
$\endgroup$
2
We know that all data with length n Bits and minimum 1 Bit can be compressed...
How do we know this? This isn't true for lossless compression. In fact for strings of length n, most of them are not compressible.
-
$\begingroup$ (Knowing the length to be $n > 0$, I'd drop one leading true bit: half the bit strings got shorter (and none got longer). (I know neither a "prefix code" achieving that nor a way to prove that such doesn't exist (other than hand-waving: dropping the first bit from all bit-strings that have at least one leaves you with a larger set (+ empty string)).)) $\endgroup$ Commented Apr 1, 2018 at 15:43
-
$\begingroup$ Yeah, the prefix code gets in the way. Try it for say all strings where n<3. $\endgroup$– RayCommented Apr 2, 2018 at 16:38
either lossless or lossydon't get into lossy compression until you are sure why $n$ pigeons don't fit into $n-1$ holes with no two pigeons in the same hole. $\endgroup$