Hacker News Reader

Comment by CJefferson | Hacker News Reader

You mean, why didn't he write a simple compression algorithm which actually shrunk the data?

The short answer is, it was (almost certainly) impossible. You cannot compress random data. The only reason files you compress normally seem to compress is almost every file you come across normally contains some structure and therefore some redundancy.

View on HN

It is not random, input file is constant. Surely you can write an algorithm to compress a specific file.

But the sum of your decompression program and compressed file would then be larger than the original data file.

Mike's contest didn't limit the total size of the (input, random) data file, so you could make it arbitrarily large to make the cost of the decompression program arbitrarily small.

> [...] the contestant will send me a decompressor and a compressed file, which will together total in size less than the original data file, and which will be able to restore the compressed file to the original state.

If the data file is truly random, then there is no decompression program + compressed file that would be smaller than the original random file. That's the entire point.

I'm not saying you could! I am only rebutting your earlier line of reasoning.

IF you could write an algorithm that would compress a specific block of random data by any non-zero percentage, and IF you can make the original random data arbitrarily large, THEN the overall size of the code to implement this algorithm would not matter, because you could amortize it over an arbitrarily large random data file.

However I am not claiming that such an algorithm to compress a specific block of random data exists! However other people are arguing that this is indeed theoretically possible: http://news.ycombinator.com/item?id=5025527

What if the rng generates a file with massive redundancy by chance. Doesn't make it any less "truly random."

Then how would you find redundancy in arbitrarily large random data?

See my comment http://news.ycombinator.com/item?id=5025527 This is a misunderstanding of the pigeonhole principle, which only applies to a specific compression algorithm. It does NOT apply if you get to write a custom algorithm for this data set.

There are always redundancies in random data. If you can pick them out ahead of time with a custom algorithm it's certainly possible to "compress" it.

Edit: I think I may be wrong here.

...except in this case a complex custom algorithm will make the decompressor bigger which will count against your total size.

Except, that 'specific compression algorithm' could be "attach an x86 program to your compressed data, which I will run", which then covers all algorithms you might care to submit.

It is not possible, without some amount of luck. The reason is, that you can think of the data + decompressor as a program which contains the data as some binary blob. There are less than 2^s different possible executables, where s is the filesize of the compressor together with the compressed data. And therefore 2^s different outputs. On the other hand, there are 2^l different original files (l is the filesize). Therefore only a few files can be compressed to a smaller file size. To be precise, you can compress at best 2^s files out of the 2^l ones by l-s bits.

Thinking a bit further, for a file of length l, the probability getting a file that can be compressed is smaller than

\sum_{k=1}^{l-1} 2^{-k} [1]

which approaches 1 for l against infinity. ( So just based on the upper limit, your odds seem to get better for longer programs. :)

[1]rendered formula for the equation (hope this works): http://latex.codecogs.com/gif.latex?\sum_{k=0}^{l-1}%202^{-k...

Reply on news.ycombinator.com