Hacker News Reader

Comment by ars | Hacker News Reader

The pigeonhole principle only applies to a specific compression algorithm.

If you get to custom write the algorithm for the data you can arrange things so that for this datafile it will be smaller, yet larger for any other file, and still meet the principle.

i.e. this is not actually impossible. If you can find ANY redundancy in the data, and you can code a very small decompresser specifically for that, you can probably win.

And due to the nature of randomness, there are always numeric streaks, and other patterns in the data. The larger the datafile the better the chance of finding some sort of pattern or streak.

The decompresser does not have to be large either - it would be perfectly legal to use a perl script for example. (i.e. so you don't have to use space writing IO handling code).

Edit: I suspect I may be wrong here.

View on HN

No.

Let's say you have a file of size X. You want to write a program of size Y which will decompress an X-Y-1 sized file back to the original program. Does such a program and file exist for every file of size X?

Using the pigeon hole principle, we can see that it does not. There are 2^X files of size X, but only 2^(X-1) inputs of length Y+X-Y-1. Therefore, not every file can be compressed this way. It doesn't matter what your decompressor is written in or how, you still can't do it.

This is correct for the general case, but I think his argument is that for any specific file you can (almost certainly) find some redundancy and so find an algorithm to compress that specific file.

That is exactly my argument.

But now I think I'm wrong because what if you take the new data (i.e. the decompressor plus the compressed data), and try to compress that.

You can't compress indefinitely because presumably your algorithm does not shrink in size. If your algorithm was 200 bytes, you could never successfully use it to compress a 199 byte file.

If this were possible, there would be a minimum file size, beyond which further compression were impossible.

I feel like the reason this might be possible is that there is information contained in a program that is not contained in that language's files. Specifically, in how the operating system treats those bits. In other words, the same decompressor + data file combo could have different but deterministic results depending on which operating system or machine executes it. We can therefore escape the pigeon hole's grip.

That doesn't help, because at the end of the day we are running on a specific os and machine. And given that machine, there exists a file of size X which it is not possible to compress because of the pigeon hole principle.

Right, but if we find that we do have a file which is impossible to compress, we could just switch to a system where it does work. There may even be operating system variables you could change which would change the output of the program. The guy asked: "Does it have to run on any machine or is just one machine ok." But did not get an answer.

I agree, for any specific machine configuration there exist non-compressible files, but I don't think we are so restricted. *Edit, it might also be possible to include in your compression algorithm the logic: change the OS into a state where this file is compressible.

Obviously you can create a machine which already has the original file on it, and have your "decompressor" simply print out that file.

I think that it was an unwritten requirement that it would work on Goldman's computer, and I think even people who say that Patrick's technique was legit would agree with that.

I see your point.

Mike says in the article: "Flagging any slightly compressible portion of the data stream will require more overhead bytes than will be gained in compression."

Except you don't flag it in the data stream.

You hardcode it in the decompressor.

Edit: Never mind. If I think of the decompressor as data too, then all I did was flag it at the start of the datastream rather than inline.

Have you (or anyone on HN) had a look at the random data linked in the article?

Brainstorming I came up with some ideas but those fail at first glance. "Convert it to unicode and utilise all those 0s!", "Find the sequence in Pi, give a Pi generation algo and an offset!"

It'd be interesting to see what people on HN come up with, even if their approaches do not 'win' this challenge.

Reply on news.ycombinator.com