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

161–170 of 192 posts

Re: The $5000 Compression Challenge (2001)

#161

Post by anamexis »

Dylan16807 wrote: post #160
anamexis wrote: post #158

Earlier quoted context omitted.

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?

The whole point of the filename discussion is that it's a trick to "compress" the data, such that the sum of the file size of the input files is smaller than the file size of the decompressed output file.

Neither of your ideas work with this.

In terms of just transferring the files in order, then you need to delineate the start and end of each file, which will take more space than the byte you are removing. Same with the tar file.

Re: The $5000 Compression Challenge (2001)

#162

Post by Dylan16807 »

anamexis wrote: post #161
Dylan16807 wrote: post #160

Earlier quoted context omitted.

> 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?

The whole point of the filename discussion is that it's a trick to "compress" the data, such that the sum of the file size of the input files is smaller than the file size of the decompressed output file. Neither of your ideas work with this. In terms of just transferring the files in order, then you need to delineate the start and end of each file, which will take more space than the byte you are removing. Same with…

> The whole point of the filename discussion is that it's a trick to "compress" the data

I think you've fundamentally misunderstood my point.

You seem to think I'm trying to make it work without a trick, but I'm not doing that. I'm saying yes there is a trick, but the trick is not based around filenames. The trick needs a sequence of variable-size blobs of bytes, and there's a lot of ways to maintain a sequence.

Re: The $5000 Compression Challenge (2001)

#163

Post by anamexis »

Dylan16807 wrote: post #162
anamexis wrote: post #161

Earlier quoted context omitted.

The whole point of the filename discussion is that it's a trick to "compress" the data, such that the sum of the file size of the input files is smaller than the file size of the decompressed output file. Neither of your ideas work with this. In terms of just transferring the files in order, then you need to delineate the start and end of each file, which will take more space than the byte you are removing. Same with…

> The whole point of the filename discussion is that it's a trick to "compress" the data I think you've fundamentally misunderstood my point. You seem to think I'm trying to make it work without a trick, but I'm not doing that. I'm saying yes there is a trick, but the trick is not based around filenames. The trick needs a sequence of variable-size blobs of bytes, and there's a lot of ways to maintain a sequence.

The trick in the OP is absolutely based around filenames, as a source of ordering the input files. I agree that you can use the same idea if you can order the files a different way, but I don't understand why that is significant.

Re: The $5000 Compression Challenge (2001)

#164

Post by ttshaw1 »

hinkley wrote: post #154
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 la…

If they're trying to dissuade "universal compressors" then Mike needed to ask for the algorithm first, and then generate his file. If you tell me "I bet you can't compress this file!" then I can do whatever I want to write some stupid one-off compressor to shave a byte off and take your money.

Re: The $5000 Compression Challenge (2001)

#165

Post by Dylan16807 »

anamexis wrote: post #163
Dylan16807 wrote: post #162

Earlier quoted context omitted.

> The whole point of the filename discussion is that it's a trick to "compress" the data I think you've fundamentally misunderstood my point. You seem to think I'm trying to make it work without a trick, but I'm not doing that. I'm saying yes there is a trick, but the trick is not based around filenames. The trick needs a sequence of variable-size blobs of bytes, and there's a lot of ways to maintain a sequence.

The trick in the OP is absolutely based around filenames, as a source of ordering the input files. I agree that you can use the same idea if you can order the files a different way, but I don't understand why that is significant.

Because it seems very unfair to call it "filename shenanigans". The filenames are only there to point the script at the right file. Filename shenanigans would be something like putting actual bytes into the filename.

If you patched `cat` to ignore filename and just spit out each file as given, the script would still work without a single change. If you slightly changed the script to loop over the results of `ls`, it could still be compatible with scrambled filenames.

A script that didn't cheat would also be using filenames to a similar level.

In other words the filenames are a completely fair implementation detail. And that detail can be swapped out without changing the trick in any meaningful way.

The trick is based on having a series of variable-sized blobs of bytes. That's all it needs. If I use javascript instead of sh, and my decompressor is `[...s].join('5')`, I'm using the same trick.

Re: The $5000 Compression Challenge (2001)

#166

Post by fragmede »

teo_zero wrote: post #122
GuB-42 wrote: post #113

Earlier quoted context omitted.

For a truly random file, your 1/50 compression scheme that will make it smaller than the original will only make it smaller by 5 or 6 bits, maybe more if you are lucky, but it is an exponential, so realistically, you won't be able to save more than a byte or two, and you can't write that decompressor in two bytes. The only way to win is to reverse the random number generator used to create the contest file, or to exp…

> The only way to win is to reverse the random number generator used to create the contest file In that case Mike, the contest creator, may declare the result invalid because you haven't satisfied the intent of the challenge.

He may, but everyone else recognizes that he underspecified the rules of the game and in doing so is a sore loser, and to never conduct business with him because he's not a man of his word and only does things when it's convenient for him.

Re: The $5000 Compression Challenge (2001)

#167

Post by anamexis »

Dylan16807 wrote: post #165
anamexis wrote: post #163

Earlier quoted context omitted.

The trick in the OP is absolutely based around filenames, as a source of ordering the input files. I agree that you can use the same idea if you can order the files a different way, but I don't understand why that is significant.

Because it seems very unfair to call it "filename shenanigans". The filenames are only there to point the script at the right file. Filename shenanigans would be something like putting actual bytes into the filename. If you patched `cat` to ignore filename and just spit out each file as given, the script would still work without a single change. If you slightly changed the script to loop over the results of `ls`, it…

> If you patched `cat` to ignore filename and just spit out each file as given, the script would still work without a single change. If you slightly changed the script to loop over the results of `ls`, it could still be compatible with scrambled filenames.

This isn't true! If you scrambled the filenames, the files would be put together in the wrong order and the result would be incorrect. You would need to also transmit the order that the files would be put together separately, which again, together with the size of the files themselves, would be greater than the size of the output.

The key thing here is that the trick works by storing the information of how the blobs are ordered out-of-band. In the OP, that out-of-band place to store the blob order is filename. In your JS example of `[...s].join('5')`, where does the order of [...s] come from? It's not something you can hand-wave away, it's the key thing that makes the trick work.

Re: The $5000 Compression Challenge (2001)

#168

Post by hinkley »

ttshaw1 wrote: post #164
hinkley wrote: post #154

Earlier quoted context omitted.

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

If they're trying to dissuade "universal compressors" then Mike needed to ask for the algorithm first, and then generate his file. If you tell me "I bet you can't compress this file!" then I can do whatever I want to write some stupid one-off compressor to shave a byte off and take your money.

I'm not saying 'Mike' had a high-effort ask, because clearly it wasn't particularly well thought out. Just that other people were glad for any Mike at all.

Re: The $5000 Compression Challenge (2001)

#169

Post by Dylan16807 »

l33t7332273 wrote: post #141
teo_zero wrote: post #64

Mike supports $SPORT team the Compressors. He's so sure they are unbeatable that he accepts 50:1 bets against them. Patrick bets 100$ that they won't win this year's championship; Mike accepts. Later, the Compressors announce financial troubles and can't pay the fee to enter the championship, which is then won by another team. Patrick reclaims his 5000$. Mike refuses to pay saying that the Compressors have not been b…

And the FAQ for the bet said that if a team can’t afford to enter the playoffs then the bet is off.

1. Which line in the FAQ are you making an analogy to?

2. A FAQ for the newsgroup is not automatically part of the rules for the challenge.

3. If the entire FAQ is treated as rules text, then the rules directly say you cannot win, and that's not an acceptable way to do rules.

Re: The $5000 Compression Challenge (2001)

#170

Post by Dylan16807 »

anamexis wrote: post #167
Dylan16807 wrote: post #165

Earlier quoted context omitted.

Because it seems very unfair to call it "filename shenanigans". The filenames are only there to point the script at the right file. Filename shenanigans would be something like putting actual bytes into the filename. If you patched `cat` to ignore filename and just spit out each file as given, the script would still work without a single change. If you slightly changed the script to loop over the results of `ls`, it…

> If you patched `cat` to ignore filename and just spit out each file as given, the script would still work without a single change. If you slightly changed the script to loop over the results of `ls`, it could still be compatible with scrambled filenames. This isn't true! If you scrambled the filenames, the files would be put together in the wrong order and the result would be incorrect. You would need to also trans…

> This isn't true! If you scrambled the filenames

I said "could" because you'd have to either do a limited scramble or hotwire ls to use the right order despite the scrambling. Or sort by date or inode, probably.

> The key thing here is that the trick works by storing the information of how the blobs are ordered out-of-band.

Yes. That is the key, not the filenames.

> In the OP, that out-of-band place to store the blob order is filename.

It is, but the actual use of filenames is not a shenanigan, and the blob order could be easily accomplished without any particular filenames.

> In your JS example of `[...s].join('5')`, where does the order of [...s] come from? It's not something you can hand-wave away, it's the key thing that makes the trick work.

It comes from the process of loading the blobs onto the computer. I'm not trying to hand-wave it, I'm saying it doesn't need filenames or anything resembling filenames. Maybe it came from a tar. Maybe I sent each file in a separate email. All that matters is having an order, and having an order happens by default when you have multiple files. As long as you don't go out of your way to reorder things, the trick works.

Post reply on HN