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

131–140 of 175 posts

Re: The $5000 Compression Challenge

#131

Post by emn13 »

Dylan16807 wrote: post #32
barrkel wrote: post #30

Earlier quoted context omitted.

The EOF is not at a cost of zero bytes; it costs as much as storing the length of each constituent file. The extra space used is in the file system accounting.

It's at a cost of 0 competition score bytes. Mike screwed up by allowing an alphabet of 257 symbols and then only counting 256 of them. Pretty much any compression or repacking algorithm could have been used at that point.

In return, Patrick screwed up in wanting to use the extra filesystem metadata, but he failed to actually ensure that it would be left unaltered. Only the file contents were to be left untouched.

Re: The $5000 Compression Challenge

#132

Post by emn13 »

bo1024 wrote: post #81
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…

> A longer running challenge is http://www.drdobbs.com/architecture-and-design/the-enduring-... . No entry fee, $100 prize, and just as unfair. At the 10-year scale, a whole new set of tricks opens up. Invent a sufficiently popular programming language, or contribute a lot to the linux kernel, and start surreptitiously hiding bits of the file on his OS (the easiest would be for you language to have a builtin function…

That was explicitly forbidden :-)

Re: The $5000 Compression Challenge

#133

Post by oneeyedpigeon »

emn13 wrote: post #129
cnvogel wrote: post #112

Earlier quoted context omitted.

We probably agree that any program should be allowed to uniquely identify the files making up the input data. And if Mike would have spotted the (other) more obvious loophole, which is to store input data in only the filenames, he could have given this (possibly the only) sensible answer: "Yes, multiple files whose summed up size + the size of the decompressor are smaller than the original file are ok. But the files…

But that's not what happened. Patrick , not Mike, changed the rules, and he intentionally introduced a loophole. But in doing so, he failed to specify that file names were to be left unaltered. I think it's fair that if you make intentionally tricky rules, you not be surprised when your own loopholes are exploited. Providing multiple files with the (deceptive) intention of storing data via filesystem metadata, but th…

This is exactly why such challenges are always entirely unsatisfactory and nothing but a pointless distraction. There might be some point in providing entertainment to both parties if the pedantry war weren't entered into, but the nature of the challenge all but guarantees that will happen.

Mike will always be able to find an excuse not to pay. If Parrick had imposed the 'no file renaming' condition, Mike could have found another way in which to break his submission with a counter loophole.

This type of challenge should never be made or accepted, if financial incentives are involved, without an impartial adjudicator.

Re: The $5000 Compression Challenge

#134

Post by emn13 »

im3w1l wrote: post #47
a_e_k wrote: post #45

Earlier quoted context omitted.

From random.org, used as a source for the data: > RANDOM.ORG offers true random numbers to anyone on the Internet. The randomness comes from atmospheric noise, which for many purposes is better than the pseudo-random number algorithms typically used in computer programs.

Ah missed that. Yeah then it may be good enough randomness.

But yeah - it may well be not entirely random, and if someone actually managed to build a compressor based off any slight bias, I think they deserve the 5000 :-).

Re: The $5000 Compression Challenge

#135

Post by hackhat »

He also doesn't state that the output should be right at first decompression try. By using this you could encode multiple bits and then generate various wrong archives, knowing that after 1000000 tries he would get a correct decompressed file.

Re: The $5000 Compression Challenge

#136

Post by Dylan16807 »

emn13 wrote: post #128
scintill76 wrote: post #41

Earlier quoted context omitted.

> He didn't say "okay, but there will be a 256 byte size penalty per additional file", he just plainly agreed. Exactly. IMO the challenge-setter is the one being more unfair here, since his metadata-based reason to reject the solution applies to submissions made under the original rules too. He accepted an amendment without counter-amending to cover that loophole, so if he stands by his word, he has to pay up. It cas…

Note that he never guaranteed to leave the files with the same file names, and without that, Patrick's trick wouldn't have worked. Given the fact that Patrick made the rules concerning multiple files, and that they were intentionally tricky, I think it's fair to interpret them in that spirit - as a trick. Notably, even without the ordering there is still some information leakage purely in terms of file sizes, but tha…

He could have ordered the files by size pretty easily. Trick still would have worked. No fancy requirements needed. Just making the files available in any manner.

And yes there needs to be a way to know which file(s) are the compressed data, that loophole would disqualify any entry.

Re: The $5000 Compression Challenge

#137

Post by DougBTX »

emn13 wrote: post #126
paulsecwhatt wrote: post #95

I absolutely believe Mike should have paid Patrick. On the simple premise that since Mike was hosting a bet that he KNEW was impossible (i.e. under no circumstance, ever, would he have to pay the 5000$), then literally the only point of the game is to find any loopholes. Otherwise it's just Mike preying on unsuspecting victims. If you design an impossible game, the only possible thing for anyone to do is to break it.…

Mike's responses could have been better, but in the correspondence I see no guarantee that the files will be presented in order, or with the same file names, or in an otherwise empty directory. That sounds close to cheating, but I think it's exactly in the spirit of both the original challenge by Mike and the response by Patrick. After all, the original challenge didn't mention multiple files (so it's not surprising…

The "compressed" files includes a header file which records the original file name and the number of parts which make up the compressed file, so it doesn't depend on directory listing to re-combine the parts.

Re: The $5000 Compression Challenge

#138

Post by gruntled »

SeoxyS wrote: post #71
gruntled wrote: post #26

Earlier quoted context omitted.

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.

But it rules out other kinds of tricks like storing info in file names. If all the metadata is counted in the length of the tar file, these tricks don't stand a chance. There's way more than 1 byte of overhead per file in the file system and Mike needed a rule that counts all of them.

Re: The $5000 Compression Challenge

#139

Post by seanc722 »

x0x0 wrote: post #91
snowwrestler wrote: post #42

The point of the challenge was to tempt people who do not understand compression as well as Mike into putting themselves into a position for Mike to mock and/or shame them. From that respect, it seems to me like it was a trick. In my experience, people who set up such tricks do not usually respond well when the tables are turned. There are some people in the world who take it personally when other people don't unders…

Why do you think that rather than Mike is genuinely interested in novel compression methodologies, and willing to pay some money to make interested people attempt to discover them?

I would say the update he posted to the news group rules this out.

Re: The $5000 Compression Challenge

#140

Post by DanBC »

Bentota wrote: post #122

Why wouldn't binary run length encoding work here? E.g. "compressing" 11100110 to 30020 for example?

Compression relies on entropy. There's not enough entropy in the random file your your run-length encoding to work.

I think the data is available so you can always try to beat the bet.

Post reply on HN