Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The $5000 Compression Challenge

patrickcraig.co.uk

Post reply on HN
Print view View original

71–80 of 175 posts

Re: The $5000 Compression Challenge

#71

Post by SeoxyS »

gruntled wrote: post #26
jheriko wrote: post #2

yeah, he should have been smart enough to spot what was coming when he was asked about multiple files... or at least asked some more directed questions than 'what do you think you have that will solve this problem'

Or insisted it was a single file, tar files allowed.

Tar files have a decent amount of overhead. Source: I wrote a streaming untarring library in C for a streaming video product. You would definitely add WAY more than 1 byte of overhead per file, which is what is required for this trick to work.

Re: The $5000 Compression Challenge

#72

Post by eridius »

kazinator wrote: post #27

Mike Goldman originally wrote the challenge such that it calls for one file and one decompressor. However, when subsequently asked whether there can be multiple files, he agreed; thereby he was arguably duped. He didn't say "okay, but there will be a 256 byte size penalty per additional file", he just plainly agreed. This means that the original formula for adding the size of the solution applies: just the file sizes…

I admit I'm surprised to see this comment is still the top comment. I wrote it off when it was first written as being far too pedantic to be at all meaningful, but I guess other people are falling for the same trick.

This is pure pedantry, and it's bad pedantry at that. Your argument is that Mike agreed that multiple files could be submitted, and from that you're drawing the completely baseless conclusion that the multiple files would be considered purely based on their filesize. According to a straightforward reading of the challenge, only the filesize of the decompressor and compressed file would matter. But when Mike agreed to multiple compressed files, nowhere did anyone state that only the filesize of the additional compressed files would matter.

And it should be pretty obvious to anyone that you cannot simply accept just the filesize of the multiple compressed files. Because the only point in using multiple files is to try and hide extra data in either the number of files or their filenames. And that obviously violates the entire point of the challenge.

If you want to take Patrick's multiple files approach to its logical conclusion, you may as well submit a bunch of zero-sized files where all of the data is stored in the filename (perhaps with an integral prefix for sorting purposes) and have your decompressor just be some variant on `echo` that strips the prefix and echoes the rest of the filename (without space separation). That way you could claim infinite compression!

---

If you're still not convinced, then how about this: nowhere did Mike agree that he would not rename the decompressor or compressed file(s) prior to running the program. And a trivial renaming would have broken Patrick's "decompressor". That alone should cause his entry to obviously be a failure.

Re: The $5000 Compression Challenge

#74

Post by imron »

kazinator wrote: post #27

Mike Goldman originally wrote the challenge such that it calls for one file and one decompressor. However, when subsequently asked whether there can be multiple files, he agreed; thereby he was arguably duped. He didn't say "okay, but there will be a 256 byte size penalty per additional file", he just plainly agreed. This means that the original formula for adding the size of the solution applies: just the file sizes…

>So he is wrong to keep the $100 in any case.

Regardless of the results of the challenge, at the end of everything Goldman offered in good faith to return the $100 and Craig said he could keep it.

Re: The $5000 Compression Challenge

#76

Post by function_seven »

compbio wrote: post #38

A trick similar to the recursive Barf compressor (add information to the filename). http://mattmahoney.net/dc/barf.html A longer running challenge is http://www.drdobbs.com/architecture-and-design/the-enduring-... No entry fee, $100 prize, and just as unfair. A completely serious compression challenge with serious consequences for AI and NLP: http://prize.hutter1.net/ up to 50.000$ prize money, but severe restriction…

> If Goldman wants his file to be random, any random file should do. Why does he want exactly his own random file?

Maybe because the file was XOR'd with a secret one time pad?

Re: The $5000 Compression Challenge

#77

Post by seandougall »

eridius wrote: post #72
kazinator wrote: post #27

Mike Goldman originally wrote the challenge such that it calls for one file and one decompressor. However, when subsequently asked whether there can be multiple files, he agreed; thereby he was arguably duped. He didn't say "okay, but there will be a 256 byte size penalty per additional file", he just plainly agreed. This means that the original formula for adding the size of the solution applies: just the file sizes…

I admit I'm surprised to see this comment is still the top comment. I wrote it off when it was first written as being far too pedantic to be at all meaningful, but I guess other people are falling for the same trick. This is pure pedantry, and it's bad pedantry at that. Your argument is that Mike agreed that multiple files could be submitted, and from that you're drawing the completely baseless conclusion that the mu…

> completely baseless conclusion that the multiple files would be considered purely based on their file size

You mean, like...

> I meant can I send you a compressor and several compressed files whose total file size is less than the original uncompressed file and from which I can regenerate the original uncompressed file.

(to which Mike agreed)?

Re: The $5000 Compression Challenge

#78

Post by function_seven »

btown wrote: post #60
mrfusion wrote: post #51

I'm confused about the challenge. Why wouldn't simply using gzip work? I must be missing something obvious.

If you're given perfectly random data, gzipping it will (almost) never reduce the size so much that you could fit the gunzip binary in the reduced space. In the extremely rare occurrence that the generated random data has, say, a repeated string longer than the gunzip binary, the challenger could be on guard for that and just regenerate random data until that's not the case. To be more formal, the challenger is findi…

> that you could fit the gunzip binary in the reduced space

What's funny is that Patrick (the challenger) asked if a bash script consisting solely of a call to gunzip would suffice as the decompressor. In other words, all he had to do was compress the file by more than the amount of the script. Mike allowed it, knowing that even a tiny "decompressor" that really just called out to the real thing, would still be larger than the compression achievable on a well-crafted random blob.

Re: The $5000 Compression Challenge

#79

Post by coldtea »

compbio wrote: post #38

A trick similar to the recursive Barf compressor (add information to the filename). http://mattmahoney.net/dc/barf.html A longer running challenge is http://www.drdobbs.com/architecture-and-design/the-enduring-... No entry fee, $100 prize, and just as unfair. A completely serious compression challenge with serious consequences for AI and NLP: http://prize.hutter1.net/ up to 50.000$ prize money, but severe restriction…

>If Goldman wants his file to be random, any random file should do. Why does he want exactly his own random file?

Because not all random files are equally random? DUH! He had to ensure there's no bias in the distrubution, use a good random generation, check for skewed data etc...

Re: The $5000 Compression Challenge

#80

Post by function_seven »

davmre wrote: post #48
martinko wrote: post #31

Earlier quoted context omitted.

>you'd need a method that can compress a random file with at least 2% ($100/5000) probability No, you'd need to be able to create a custom algo for that file with that probability. Quite a difference.

The "custom algorithm" thing is a red herring. You'll need to use some method to come up with your custom algorithm, once you see the input file, and whatever method you choose is itself a compression procedure, targeted at a fixed decoder which is essentially a Bash shell with a C compiler (* ). If you intend to treat different inputs differently (e.g., "if it contains the string "AB", I'll use this algorithm, if it…

> If you intend to treat different inputs differently (e.g., "if it contains the string "AB", I'll use this algorithm, if it has more zeros than ones, I'll use this other one, etc"), this just means that your compression procedure contains some 'if' statements. The laws of information theory don't care whether your compression procedure is actually a computer program or just implicitly encoded into human actions; it's still impossible to reliably represent random data with fewer than the usual number of bits.

While you're obviously correct about the information theory aspect of this, in this particular challenge, the contestant enjoys the privilege of pruning his decompressor to match just the one file. All the other "if" statements can be thrown away. So now a lossy algorithm can be used, that just happens not to be lossy on that one particular file.

Post reply on HN