3 ms·
Lossless compression works by exploiting redundancy in the data. If I want to compress a text file that contains the word 'uncharacteristically' 1000 times, I
by bradleyjg 14y ago
Lossless compression works by exploiting redundancy in the data.
If I want to compress a text file that contains the word 'uncharacteristically' 1000 times, I can simply replace ever occurrence with the a certain short unused byte sequence and record the mapping in the header.
Similarly in an image file, if there is a block of 50 pixels that are all the same color, I can replace that block with a special byte sequence and map the coordinates and color in the header.
But if I have truly random data, there are no patterns to exploit. The shortest means of representing random data - is the data itself.
This is provable using information theory (which in a way is a branch of thermodynamics).
- lurker14 14y agonitpick: There is no such thing as a truly random piece of data. "Truly random" is only meaningful in the limit as the file size goes to infinity. The string "000000" could be generated by a truly random process just as well as any any other.
- bradleyjg 14y agoI meant Kolmogorov randomness which is defined via incompressibility.
- lurker14 14y agoFair enough, but Kolmogorov randomness is an existence concept, not a constructive concept, so I find it weird to talk about having such a string in this case where a real person sets about to generate a concrete file. Can you generate a Kolmogorov random file on your particular Unix system? That requires specifying what "your Unix system" rather rigorously, which seems unpleasant.
- deleted 14y ago[deleted]