The $5000 Compression Challenge

Post by kazinator » Sun, Mar 08, 2015, 5:07 AM UTC

okatzzz wrote: post #59

gamblor956 wrote: post #52

Earlier quoted context omitted.

Nope, perfectly acceptable for Goldman to keep the $100. Craig tried to play a game of semantics, and lost because semantics let Goldman weasel out by pointing to O/S meta data. The challenge clearly, repeatedly, stated that Goldman would give $5000 to anyone who could compress a datafile such that the combined size of file and decompressor was smaller than the original datafile. Craig did not compress the data store…

This interpretation is inconsistent with Goldman's own statement about the original data that "the file size is 3145728". He didn't say "the file size is 3145728 plus some file system overhead", so by file size he was thinking of the number of bytes in the file ... until he was outsmarted. It's hardly a filesystem exploit if - again by Goldman's own statement - gunzip is allowable.

Post by [deleted] » Sun, Mar 08, 2015, 5:17 AM UTC

gamblor956 wrote: post #52

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…

Nope, perfectly acceptable for Goldman to keep the $100. Craig tried to play a game of semantics, and lost because semantics let Goldman weasel out by pointing to O/S meta data. The challenge clearly, repeatedly, stated that Goldman would give $5000 to anyone who could compress a datafile such that the combined size of file and decompressor was smaller than the original datafile. Craig did not compress the data store…

Post by [deleted] » Sun, Mar 08, 2015, 5:24 AM UTC

kazinator wrote: post #61

gamblor956 wrote: post #52

Earlier quoted context omitted.

Nope, perfectly acceptable for Goldman to keep the $100. Craig tried to play a game of semantics, and lost because semantics let Goldman weasel out by pointing to O/S meta data. The challenge clearly, repeatedly, stated that Goldman would give $5000 to anyone who could compress a datafile such that the combined size of file and decompressor was smaller than the original datafile. Craig did not compress the data store…

"compress a datafile such that ..." appears to give a self-contained definition of what it means to compress in the context of the challenge. In any case, no compression algorithm makes all inputs smaller. So, just because a data encoding doesn't make a particular input case smaller doesn't imply that it's not a compression algorithm.

Post by im3w1l » Sun, Mar 08, 2015, 5:46 AM UTC

davmre wrote: post #43

phamilton wrote: post #39

Earlier quoted context omitted.

Continuing that logic: You could get 6% if you can also do the same on the end of the file. There's a 1 in 16 chance that any random sequence of data will start or end with 5 zeros. The same trick could be done for 1s to bring it up to 12%. In other words, 12% of sequences will either begin or end with 5 ones or 5 zeros. Since you can inspect the data before writing the decompressor, if we can figure out how to pad t…

Unfortunately you're confusing bits and bytes (I did the same thing too at first). Fitting a decompressor in five bits is a lot harder. :-)

Post by tlrobinson » Sun, Mar 08, 2015, 5:59 AM UTC

im3w1l wrote: post #6

I don't think it is 100% foolproof, even if no filesystem trickery is used. The random number generator used is likely not perfect and so the data should be compressible. I mean it would probably be quite difficult, but maybe possible.