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

161–170 of 175 posts

Re: The $5000 Compression Challenge

#161

Post by andrewaylett »

prettyrandom100 wrote: post #145
brongondwana wrote: post #102

Earlier quoted context omitted.

Except if the hash is smaller than the source data, then with a good hash, there will be multiple source datasets that hash to the same result, which makes your decompression program unreliable. You could well bruteforce the wrong answer.

Do you mean that there could be two 3K files with the same sha256 hash and the probability of hitting the collision is greater than the probability of finding the correct hash for the file ? Let's divide the 3 mb file into 1000 parts, each having a ~3k size. Take sha256 hash of all 1000 parts and sha256 hash of the actual file. The size of these hashes are less than the actual file + leaves ample room for a decompres…

It's not that there might be a collision, but that collisions are guaranteed. How many 3Mb files are there? 2^(3M8) = 2^25165824. How many distinct hashes are there? 2^(2561001) = 2^256256.

By the pigeonhole principle, we can't fit 2^25165824 objects into 2^256256 holes; indeed each file will have on average 2^24909568 other files that share the same set of 1001 sha256 hashes.

The reason that we are able to work with hashes, and that compression works in practice, is that we don't have to deal with every 3M file. Most of these files are gibberish and will never be seen, and finding two files that match even one hash is incredibly difficult. But once we start talking about brute-forcing, we start encountering problems -- and having to dedicate an awful lot of processing power to the problem isn't the biggest one...

Re: The $5000 Compression Challenge

#162

Post by compbio »

DanBC wrote: post #116
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…

> Why does he want exactly his own random file? He's running a model and needs to use the same random data each time.

Then he can wait for the RNG to produce this same random data. Eventually it will produce a file which matches. A dynamic solution of sorts, because he would have to be quick to diff, before the file starts changing again.

I feel that the compressor for a true random stream is a true random generator. If I quickly show you a screen of black-and-white unpredictable noise, and ask you what it was, you'd compress/understand/recall that as "generate_noise()". I do not feel that this is lossy compression, for what did you lose? The ordering of a random file? Random files have no order to lose.

Re: The $5000 Compression Challenge

#163

Post by santoshalper »

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.…

He did offer the guy his money back. I think the challenge is all in good fun and the intent is ultimately that no money ends up changing hands.

Re: The $5000 Compression Challenge

#164

Post by Dylan16807 »

emn13 wrote: post #159
Dylan16807 wrote: post #136

Earlier quoted context omitted.

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.

Yep, file sizes alone leak sufficient information to be an issue, but it's a bit of a hypothetical because that's not what actually happened. Clearly, Mike shouldn't have allowed multiple files (or should have specified some kind of overhead for multiple files), and clearly there are other tricks Patrick could have used, but with these unfortunate rules and this submission nothing seems to require keeping file order…

What I'm trying to argue is that any justifiable objection Mike could have made would have failed.

Unjustifiable objections could have been made but screw those, because they would cause legitimate compression to fail.

Unjustifiable objections will pretty much always exist if the rules are written in English. That doesn't mean the rules are broken, it means you use judgement and follow the purpose of the rules.

Mike's fate was sealed when he allowed multiple files without an overhead penalty. He could have removed all the metadata possible, simply having the files exist as separate entities was enough to ruin him.

Re: The $5000 Compression Challenge

#165

Post by Dylan16807 »

emn13 wrote: post #160
kazinator wrote: post #62

Earlier quoted context omitted.

I suspect that if the challenge had been solved with a single file, Goldman would try to get out of paying by claiming that the program's size should include the size of the interpreter for its language, and the libraries linked to that, the size of the command line needed to invoke it (including the pointer vector and null termination), not to mention the underlying kernel ...

I don't know goldman, and I bet you don't either - but there's a pretty big difference between this solution (which clearly cheats the aim of the challenge, and a solution that actually compresses. People hate to reward cheaters, even if it's a fun kind of cheat from the outside. But that doesn't mean he wouldn't have payed out for a real solution, which likely would have been quite interesting (and not quite as impo…

What does "actually" compressing mean?

Replacing every "5" with EOF is apparently bad.

What if he replaced every "5z" with EOF? Fewer bytes there.

What if he had a variant of LZ77 doing dictionary encoding followed by a range encoder that outputs symbols in the range -1 through 255? Even counting the EOF as a character, this would give an output 2K characters smaller. Sounds like compression to me. It's finding common sequences and uncommon sequences and rescaling them based on probability to remove redundancy.

Re: The $5000 Compression Challenge

#166

Post by prettyrandom100 »

andrewaylett wrote: post #161
prettyrandom100 wrote: post #145

Earlier quoted context omitted.

Do you mean that there could be two 3K files with the same sha256 hash and the probability of hitting the collision is greater than the probability of finding the correct hash for the file ? Let's divide the 3 mb file into 1000 parts, each having a ~3k size. Take sha256 hash of all 1000 parts and sha256 hash of the actual file. The size of these hashes are less than the actual file + leaves ample room for a decompres…

It's not that there might be a collision, but that collisions are guaranteed . How many 3Mb files are there? 2^(3M 8) = 2^25165824. How many distinct hashes are there? 2^(256 1001) = 2^256256. By the pigeonhole principle, we can't fit 2^25165824 objects into 2^256256 holes; indeed each file will have on average 2^24909568 other files that share the same set of 1001 sha256 hashes. The reason that we are able to work w…

There is just one 3MB file and we divide that file into 1000 parts. I agree there will be collision per hash (for each part). But I'm skeptical that all 1000 hashes will produce such bits so that the final file will cause collision on the hash of the original file (remember we do have hash of the original file). If the final hash does not match the hash of original file we would have to recompute all the hashes again by randomly generating the bits for each 1000 file-parts. Do you mean to say that the collisions are guaranteed and that the collision inside any file-part will also cause a collision in the original file hash when the parts are combined ?

Re: The $5000 Compression Challenge

#167

Post by eridius »

ghayes wrote: post #87
eridius wrote: post #83

Earlier quoted context omitted.

Since this is still a pedantry argument: Mike agreed that Patrick could send multiple files, but Mike never agreed that these files would be accepted as a winning submission. Furthermore, Mike never agreed that the filenames of the files would be considered to be meaningful data (without contributing to the filesize calculation).

> Mike agreed that Patrick could send multiple file, but Mike never agreed that these files would be accepted as a winning submission Then what is "agreeing"? These two sentences appear logically inconsistent.

Huh? Patrick asked if he could send multiple files. Mike said yes. Again, since the context of this is pedantic arguments, agreeing that Patrick could send multiple files is not the same as agreeing that Mike would consider the multiple files to be a winning submission.

Re: The $5000 Compression Challenge

#168

Post by eridius »

oneeyedpigeon wrote: post #133
emn13 wrote: post #129

Earlier quoted context omitted.

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…

It's only a pointless distraction when people see these challenges and treat them as a game to be tricked. Mike already made it clear the challenge is not about financial compensation (and offered to give Patrick the $100 back even though Patrick did not win, under the very generous assumption that Patrick innocently misunderstood the challenge instead of deliberately tried to subvert it).

The point of a challenge like this is the same as the point of the Randi challenge: to provide a means to demonstrate that impossible claims are impossible (in this case, that of being able to compress truly random data, and in the case of the Randi challenge, supernatural/magical abilities such as ESP). After all, if any such claim were valid, then the claimant would be able to defeat the challenge, assuming that the stated rules are fair (and they are).

Which is to say, the point of a challenge like this is not actually to have anyone enter. It's just to be.

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

Did you read the whole page? Mike did offer an impartial adjudicator:

> I would gladly submit any such submission to an impartial ombudsman to determine the question of whether data compression has occurred.

Re: The $5000 Compression Challenge

#169

Post by DanBC »

compbio wrote: post #162
DanBC wrote: post #116

Earlier quoted context omitted.

> Why does he want exactly his own random file? He's running a model and needs to use the same random data each time.

Then he can wait for the RNG to produce this same random data. Eventually it will produce a file which matches. A dynamic solution of sorts, because he would have to be quick to diff, before the file starts changing again. I feel that the compressor for a true random stream is a true random generator. If I quickly show you a screen of black-and-white unpredictable noise, and ask you what it was, you'd compress/unders…

When you're running a reproducible science experiment it's probably a good idea to include the actual data. For random noose this could be the generator and seed and then some good hashes but only if the experimentor used a generator and seed - if the experimentor just grabs noise from somewhere and uses that you want the actual data as part of reproducibility.

Re: The $5000 Compression Challenge

#170

Post by jakobegger »

compbio wrote: post #153
jakobegger wrote: post #111

Earlier quoted context omitted.

Bruteforcing a solution until hashes match doesn't work. If you try to bruteforce X bits and use a hash of size Y for validation, you will get 2^(X-Y) possible solutions. (I made the same mistake some time ago when I tried to bruteforce a 4 byte RC4 key with 3 known bytes in the plain text; I found 256 solutions.)

Yes, if you want to be sure that your solution is correct, you must run the compressor yourself. Then you count the number of collisions it takes to happen upon the correct solution and feed this counter to your decompressor. But then you place the burden of solving the halting problem on yourself and then you got more serious problems than compressing random data.

But your counter will need (X-Y) bits of storage, so you'll need to store Y + (X-Y) bits, or a total of X bits, and you have saved nothing.
Post reply on HN