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

21–30 of 175 posts

Re: The $5000 Compression Challenge

#21

Post by yk »

bagels wrote: post #10
ac29 wrote: post #8

Earlier quoted context omitted.

From the link I posted in my other comment, a thought experiment... Yes, some random files can be compressed by a given program, but not all random files. The proof is fairly simple, once you think it through: Theorem: No program can compress without loss all files of size >= N bits, for any given integer N >= 0. Proof: Assume that the program can compress without loss all files of size >= N bits. Compress with this…

The challenge was to provide a decompressor for one file, not any or all files. This proof of the impossibility of a compressor that can compress any file has been known for decades.

Actually even that is not feasible:

Assume that you split a m byte string into k byte decompressor and l byte input data. If k+l 

    sum_{i=0}^{m-1} 2^i = 2^m -1
there exists at least one string in the space of m character strings which can not be compressed by any algorithm.

Re: The $5000 Compression Challenge

#22

Post by ikeboy »

hurin wrote: post #17
bagels wrote: post #10

Earlier quoted context omitted.

The challenge was to provide a decompressor for one file, not any or all files. This proof of the impossibility of a compressor that can compress any file has been known for decades.

The problem wasn't well formulated, since it didn't clearly define what can or cannot be done to the decompresser based on knowledge of the output file. But consider a more strongly formulated problem, where you must provide the decompresser and then a file is randomly selected to be put through it - as long as it's still a matter of compressing one particular file it is statistically possible to win (especially at $…

It was well formulated; the whole point is that you can do whatever you want to the decompresser.

Re: The $5000 Compression Challenge

#26

Post by gruntled »

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.

Re: The $5000 Compression Challenge

#27

Post by kazinator »

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 added together.

Goldman should accept that he foolishly rushed into a careless amendment of his original challenge and pay the money.

That said, it obviously is cheating to have the archive format or file system hide the representation of where the removed bytes are! If a single file is produced, it has to include a table of where to insert the bytes that were taken out. If multiple files are produced, the archive format or file system stores that information for you at considerable expense.

If both people are wrong, the contest should be declared invalid and Goldman should return the $100.

If only Goldman is wrong, he should pay $5000.

Under no interpretation is Goldman strictly right and the contestant strictly wrong.

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

Re: The $5000 Compression Challenge

#28

Post by Dylan16807 »

nothrabannosir wrote: post #14

Quote from Mike: > Rather, you simply split the file into 218 parts ending with the > character "5" and then stripped that final character from each part. Thus the > "decompressor" is nothing more than a reassembler, > concatenating the parts and reappending > the character "5" after each. Well, that's exactly the definition of lossless compression. Look at e.g. how js crunch works: you create a dictionary of common…

I wonder how you got a downvote for that, it's quite accurate. A version of simplistic token replacement even has a wikipedia page http://en.wikipedia.org/wiki/Byte_pair_encoding

Re: The $5000 Compression Challenge

#29

Post by thomasahle »

AFAIK, information theory requires the _Expected_ size of a 'compressed' file be at least as large as the original.

So we could create an encoding that compressed N/50 of the strings with lg(N/50)=lg(N)-lg(50) bits. That would save us lg(50) > 5 bits with 2% chance. In this game we have 50 tries (5000$/100$) so we'd be pretty sure to win.

The correct price for this game is probably closer to 200$.

Re: The $5000 Compression Challenge

#30

Post by barrkel »

nothrabannosir wrote: post #14

Quote from Mike: > Rather, you simply split the file into 218 parts ending with the > character "5" and then stripped that final character from each part. Thus the > "decompressor" is nothing more than a reassembler, > concatenating the parts and reappending > the character "5" after each. Well, that's exactly the definition of lossless compression. Look at e.g. how js crunch works: you create a dictionary of common…

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.
Post reply on HN