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

151–160 of 192 posts

Re: The $5000 Compression Challenge (2001)

#151

Post by Dylan16807 »

gus_massa wrote: post #132
mhandley wrote: post #101

Earlier quoted context omitted.

You could do the same spitting trick but only split at progressively increasing file lengths at the character '5'. The "compression" would be worse, so you'd need a larger starting file, but you could still satisfy the requirements this way and be independent of the filenames. The decompressor would just sort the files by increasing length before merging.

Nice idea, but doesn't this require a linear increase of the length of the partial files and a quadratic size of the original file? If the length of a file is X, then in the next file you must skip the first X characters and look for a "5" that in average is in the X+128 position. So the average length of the Nth file is 128*N and if you want to reduce C bytes the size of the original file should be ~128 C^2/2 (inste…

It does, but that's fine. He only needs to save 150-200 bytes and the file is 3MB. 128*200²/2 is 2.5MB Though I think it would be 256* here? Still, it can be made to work.

Re: The $5000 Compression Challenge (2001)

#152

Post by Dylan16807 »

mafuy wrote: post #129
Dylan16807 wrote: post #94

Earlier quoted context omitted.

> such that the files sort differently But if you change them without making them sort differently, everything is fine. He depends on the order, not the filenames. You could even remove the filenames entirely, as long as you patch the code to account for such a strange environment.

Not really a good point. If the order of bytes does not matter, then I can compress any file of your liking to O(log n) size :P

Wait, whose point are you saying is not good?

I'm saying order does matter and it's the only thing that matters about the separate files using this code.

Re: The $5000 Compression Challenge (2001)

#153

Post by anamexis »

Dylan16807 wrote: post #152
mafuy wrote: post #129

Earlier quoted context omitted.

Not really a good point. If the order of bytes does not matter, then I can compress any file of your liking to O(log n) size :P

Wait, whose point are you saying is not good? I'm saying order does matter and it's the only thing that matters about the separate files using this code.

I think the question is, if you remove the filenames entirely, how do you keep the parts ordered?

(Someone else suggested sorting them by file size.)

Re: The $5000 Compression Challenge (2001)

#154

Post by hinkley »

ball_of_lint wrote: post #107

This strategy or something like it legitimately wins the challenge. The challenge (based on expected value) is not to find some compression scheme that will compress 100% or even 50% of files to less than their original size. Instead it's to find any (set of) compression schemes that will compress more than 1/50 = 2% of arbitrary random files to less than their original size. You can construct such a program essentia…

No. You sound as if you’re familiar with the culture but it’s clear that you’re not.

The problem with comp.compression was always that its Eternal September is new people showing up every week claiming they’ve found a universal compression algorithm that compresses everything - the perpetual motion machine of information theory. Having gotten tired of explaining to people who think they’re fighting “dogma” not the laws of the universe, people start trying to find other ways to make them put up or shut up, so they could have some peace and quiet.

Like sending them a file full of RNG output and wait for them to realize this was their teachable moment.

Winning the challenge - without engaging in out of band bullshit (compressor + output should be the giveaway) doesn’t prove you have found a universal compression algorithm. It only proves the RNG is flawed. Which would be very interesting but not break Shannon.

The problem is compressor + file means “no out of band data” to a reasonable person and we have already established we are dealing with unreasonable people.

Not

> My main motivation was to "out-trick the tricker". I thought the chances of me making any money were very remote.

Re: The $5000 Compression Challenge (2001)

#155

Post by Jerrrry »

patmcc wrote: post #118
vlovich123 wrote: post #37

Earlier quoted context omitted.

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.

Intelligence is knowing what you can lose, and losing that and no more.

I like this definition for a "proto"-intelligent trait.

Re: The $5000 Compression Challenge (2001)

#156

Post by Jerrrry »

vlovich123 wrote: post #148
echoangle wrote: post #39

Earlier quoted context omitted.

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.

Yes, you are proving intelligence if you invent the algorithm which compresses. If the prize was for inventing an algorithm that could then build the lossless compression scheme itself then you'd be onto something. But the prize is for the human who invents the better compression algorithm and proof of intelligence of the human would be self-evident.

Why are you explicitly saying "human"...

Re: The $5000 Compression Challenge (2001)

#157

Post by Dylan16807 »

anamexis wrote: post #153
Dylan16807 wrote: post #152

Earlier quoted context omitted.

Wait, whose point are you saying is not good? I'm saying order does matter and it's the only thing that matters about the separate files using this code.

I think the question is, if you remove the filenames entirely, how do you keep the parts ordered? (Someone else suggested sorting them by file size.)

You have to be storing them outside a traditional filesystem to not have filenames, so the way you keep them ordered depends on what your storage mechanism is.

For example, you could store them in a Set object in many programming languages, one that preserves insertion order. Or you could be extracting them one by one from a tar file that has blank filenames stored in it.

Re: The $5000 Compression Challenge (2001)

#158

Post by anamexis »

Dylan16807 wrote: post #157
anamexis wrote: post #153

Earlier quoted context omitted.

I think the question is, if you remove the filenames entirely, how do you keep the parts ordered? (Someone else suggested sorting them by file size.)

You have to be storing them outside a traditional filesystem to not have filenames, so the way you keep them ordered depends on what your storage mechanism is. For example, you could store them in a Set object in many programming languages, one that preserves insertion order. Or you could be extracting them one by one from a tar file that has blank filenames stored in it.

For the Set example, where would the insertion order come from? For the tar file, the tar file would be larger than the input file it's supposed to be "compressing".

Re: The $5000 Compression Challenge (2001)

#159

Post by hinkley »

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…

Human communication is full of forward error correction. So much of it that we can compress text at around 10:1. When compression first got big we could already manage more than 8:1, which makes it very useful in an era before digital photography was big. We developed lossy compression for media.

4k is 8.3 megapixels, at least 24 bits per pixel, and 24 frames a second about 4.8 Gbps if you include the audio. Netflix streams at 15.6Mbps, which is more than 300:1. We talked here a couple years ago about how HBO redid their “dead channel” intro to make the “white noise” compatible with video compression so it didn’t look like ass.

Re: The $5000 Compression Challenge (2001)

#160

Post by Dylan16807 »

anamexis wrote: post #158
Dylan16807 wrote: post #157

Earlier quoted context omitted.

You have to be storing them outside a traditional filesystem to not have filenames, so the way you keep them ordered depends on what your storage mechanism is. For example, you could store them in a Set object in many programming languages, one that preserves insertion order. Or you could be extracting them one by one from a tar file that has blank filenames stored in it.

For the Set example, where would the insertion order come from? For the tar file, the tar file would be larger than the input file it's supposed to be "compressing".

> For the Set example, where would the insertion order come from?

It would come from however the files were transferred from competitor computer to verifier computer.

> For the tar file, the tar file would be larger than the input file it's supposed to be "compressing".

It sure would be! I don't see how that's relevant to the filename discussion though?

Post reply on HN