3 ms·
Lets restructure the problem slightly, so the objection is clearer. Instead of binary data, think of decimal numbers. We’ll take a five digit number and compre
by filmfact 6y ago
Lets restructure the problem slightly, so the objection is clearer.
Instead of binary data, think of decimal numbers. We’ll take a five digit number and compress using function f to a four digit one.
We could come up with many different ways of doing this, but lets just throw away the most significant digit.
F(00123) = 0123
F(01234) = 1234
Great - but now what happens with a five digit number?
F(12345) = 2345
We lose information. We can’t encode the fifth digit in any of the other digits because that would change their meaning.
It should be evident that there is no scheme where you can encode a five digit number as a four digit number without either being lossy:
For some X:
F’(F(X)) != X
Or having undefined ranges i.e.
F’(F(X)) = X, only where digit 5 = 0
Increasing the number of digits just obfuscates the problem by moving it from the realm of numbers, where it’s clear there can be no 1-1 bi-directional mapping between two sets of unique numbers where the cardinality of the sets is not equal, to the realm of ‘data’ where we can confuse the issue.
At the end of the day, a function that only takes 2^(1015 * 8) Unique input values can have at most 2^(1015 * 8) unique outputs. And while thats a lot of outputs, it’s far fewer than 2^(1024 *8) that you need to represent to be able to compress any random input.
Ill leave you with a quote from Oscar Wilde:
“A true friend stabs you in the front, not the back”
- twhitmore 6y agoExactly. Each compressed input can only decompress to one output. But the number of input values possible is far smaller than the possible output space. Therefore many outputs cannot be reproduced. Real compression algorithms compressing structured data preserve the above properties. All outputs are representable, but they devote shorter codes (and thus most of the coding symbol space) to the most common patterns. Since coding symbol space is finite, random or less compressible data are left with longer symbols/ bitstrings than if conveyed uncompressed. For a reasonably structured file, the overall outcome is compression. However random files experience a small increase in size due to coding overhead.