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

The $5000 Compression Challenge (2001)

patrickcraig.co.uk

Post reply on HN
Print view View original

31–40 of 192 posts

Re: The $5000 Compression Challenge (2001)

#31

Post by Supermancho »

stavros wrote: post #27
Supermancho wrote: post #4

> It's not my fault that a file system uses up more space storing the same amount of data in two files rather than a single file. It's not interesting to see people play word games with each other in the HN comments, so why is it interesting to see this kind of disingenuous behavior? Trolls have always existed. I don't get what's interesting about it.

As Patrick said, if he had gotten a 1000-byte file and sent a 999-byte file/decompressor file back, nobody would have counted the inode data as a part of the solution. Why count it now?

Because the solution specifically was for 1 file submitted, 2 files back (compressed and decompressor). This topic ise the next level trolling that went on. The summary and ng faw, explained why these file metagames aren't useful. They obscure the lack of a compression strategy (eg if the inode equivalent was 2ft of tape) by nature of dispersing information into the fs.

Re: The $5000 Compression Challenge (2001)

#32

Post by guepe »

changoplatanero wrote: post #21
kittoes wrote: post #20

Earlier quoted context omitted.

What if we didn't even attempt to compress the file? Theoretically, there is a random number generator + seed combination that would output the same bytes as the source file.

Neat idea but chances are the length of the seed is equal to the length of the original file.

There is a polynomial expression that will match the file. I wonder if expressing it would be compressible to a lower size than original file? [edit] I’m wrong - not all sequences can be expressed with a polynomial.

Re: The $5000 Compression Challenge (2001)

#33

Post by stavros »

Supermancho wrote: post #31
stavros wrote: post #27

Earlier quoted context omitted.

As Patrick said, if he had gotten a 1000-byte file and sent a 999-byte file/decompressor file back, nobody would have counted the inode data as a part of the solution. Why count it now?

Because the solution specifically was for 1 file submitted, 2 files back (compressed and decompressor). This topic ise the next level trolling that went on. The summary and ng faw, explained why these file metagames aren't useful. They obscure the lack of a compression strategy (eg if the inode equivalent was 2ft of tape) by nature of dispersing information into the fs.

> Because the solution specifically was for 1 file submitted, 2 files back (compressed and decompressor).

Patrick:

I meant can I send you a decompressor 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

Mike:

Sure.

Re: The $5000 Compression Challenge (2001)

#34

Post by ccleve »

lambdaone wrote: post #28
dmurray wrote: post #14

Earlier quoted context omitted.

I think you can make some argument about why this isn't possible at 50:1 odds. A plausible "decompressor" is at least, say, 30 or 100 bytes, so the random file needs to have 30 bytes less entropy than you expected, which happens with probability X where X This argument could do with more rigor, but I think it's correct. Give me 100 million to 1 odds, though, and I'll take my chances trying to brute force a compressor…

This is actually an extremely interesting question. 'Weak' files that are more easily compressable than others certainly exist, but with low probability. For example, the all-zeros file is a member of the set of all random 3 megabyte files, and it would certainly be possible to compress that, if by great good fortune you were lucky enough to receive it - albeit something that is unlikely to ever happen in the possibl…

I know very little about this, but a little googling suggests that the measure you're looking for is entropy, which has a mathematical definition: https://en.wikipedia.org/wiki/Entropy_(information_theory)

Re: The $5000 Compression Challenge (2001)

#35

Post by spencerflem »

Retr0id wrote: post #25
ccleve wrote: post #9

I wonder if it would have been possible to win the challenge legitimately? If a randomly-generated file happened to contain some redundancy through sheer chance, you could hand-craft a compressor to take advantage of it. This compressor would not work in general for random data, but it could work for this one particular case. It's a bet worth taking, because the payoff, 50:1 ($5,000 to $100), is pretty good. Play the…

Somewhere (discussed on HN) someone devised a "better-than-perfect" compressor. Most inputs get compressed (smaller than input), except for one input that does not. That one input is cryptographically impossible to find - or something along those lines. Unfortunately I can't find the article I'm describing here, maybe someone else can? It was a long time ago so I might be misrepresenting it slightly.

That's how all compressors work, in that likely files (eg. ASCII, obvious patterns, etc) become smaller and unlikely files become bigger.

Re: The $5000 Compression Challenge (2001)

#36

Post by PaulKeeble »

I would not have accepted multiple files nor scripting. Scripts offers up the entire contents of the linux operating system and this could allow you to use operating system files as partial data. To really test compression/decompression the rules need to be a lot tighter. The challenge was met and beat because the criteria was bad. It leaves open a number of dishonest approaches.

The decompression program needs to be constrained to itself and the singular file to decompress and can not utilise anything other than basic operating system functions for the purpose of reading and writing the constrained files. Any bytes the program accesses otherwise can be used as part of the total count.

It's very hard to constrain this without some form of chest being possiblemespecially if you have some years to set it up.

Re: The $5000 Compression Challenge (2001)

#37

Post by vlovich123 »

omoikane wrote: post #17

The original email thread was from 2001, and it gets posted to HN periodically: https://news.ycombinator.com/from?site=patrickcraig.co.uk For another compression challenge that is still ongoing, try "500000€ Prize for Compressing Human Knowledge" (also known as "Hutter Prize"): http://prize.hutter1.net/ https://news.ycombinator.com/item?id=37502329 - Hutter Prize for compressing human knowledge (2023-09-13, 215 comme…

I have a fundamental problem with the Hutter prize stating that intelligence is related to compression & then sponsoring a prize for lossless compression. Intelligence is related to lossy compression. Lossless is mainly a mechanistic act.

Re: The $5000 Compression Challenge (2001)

#38

Post by benchmarkist »

lambdaone wrote: post #30
cortesoft wrote: post #24

Earlier quoted context omitted.

There is no general purpose compressor that can achieve compression on all random streams of bytes... but there is a possibility to compress a specific random stream of bytes, if you get lucky

Absolutely! Can this probability be quantified?

You'd have to define what you mean by luck which would be equivalent to choosing some pattern that your compressor can recognize in a random stream of bytes and then computing the probability that pattern appeared in some random byte sequence. It's not a winnable game in any practical sense because whatever compressor you choose the probability of getting a sequence from your opponent that will conform to the patterns recognizable by your compressor is essentially 0.

Re: The $5000 Compression Challenge (2001)

#39

Post by echoangle »

vlovich123 wrote: post #37
omoikane wrote: post #17

The original email thread was from 2001, and it gets posted to HN periodically: https://news.ycombinator.com/from?site=patrickcraig.co.uk For another compression challenge that is still ongoing, try "500000€ Prize for Compressing Human Knowledge" (also known as "Hutter Prize"): http://prize.hutter1.net/ https://news.ycombinator.com/item?id=37502329 - Hutter Prize for compressing human knowledge (2023-09-13, 215 comme…

I have a fundamental problem with the Hutter prize stating that intelligence is related to compression & then sponsoring a prize for lossless compression. Intelligence is related to lossy compression. Lossless is mainly a mechanistic act.

Isn’t the intelligence shown by compressing lossless the scheme you use? Applying the algorithm is the easy part, the proof of intelligence is inventing the algorithm which compresses.

Re: The $5000 Compression Challenge (2001)

#40

Post by echoangle »

PaulKeeble wrote: post #36

I would not have accepted multiple files nor scripting. Scripts offers up the entire contents of the linux operating system and this could allow you to use operating system files as partial data. To really test compression/decompression the rules need to be a lot tighter. The challenge was met and beat because the criteria was bad. It leaves open a number of dishonest approaches. The decompression program needs to be…

> Scripts offers up the entire contents of the linux operating system and this could allow you to use operating system files as partial data.

I also thought about this, but when thinking more about the argument by the challenge creator, I understood that the data in the OS doesn’t help you.

If you’re given a file with 100 bits, there are 2^100 possibilities. If you want to compress to 99 bits, there are only 2^99 possible compressed outputs. So when generating and trying to compress every 100 bit file, you’re not going to be able to compress half of them. The external data doesn’t help you unless you get to modify it after receiving the file to compress. If you can get patched merged into the Linux kernel, you could use the data, but if the data is fixed, you can’t reference the data with less data than the original file (for some cases atleast).

Edit: actually, when thinking about it: you could actually use the OS as another few bits of out of band information you get for free, which makes it possible again. If you have 8 different OS to choose from, you could use their differences to compress any file. At least theoretically, the 3 bits you gain practically probably aren’t enough to make a difference.

Post reply on HN