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

171–180 of 192 posts

Re: The $5000 Compression Challenge (2001)

#171

Post by anamexis »

Dylan16807 wrote: post #170
anamexis wrote: post #167

Earlier quoted context omitted.

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

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

I guess that's where we disagree. I think you don't have an order by default, you need to explicitly define it, and transmit it, and store it somehow. Which is after all, why it's not true compression. When you account for that metadata, the "compressed" data is not smaller than the original.

In the OP, the cheat was using filenames to store that data. In a tar file, it's using the tar file metadata to store it. In your email, you're storing the email metadata to keep that ordering. In all cases, order is a key thing that you need to explicitly define, transmit, and store. And in all cases, this metadata takes up more space than is saved by the whole scheme.

Re: The $5000 Compression Challenge (2001)

#172

Post by Dylan16807 »

anamexis wrote: post #171
Dylan16807 wrote: post #170

Earlier quoted context omitted.

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

> 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. 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. I guess that's where we disagr…

> I guess that's where we disagree. I think you don't have an order by default, you need to explicitly define it, and transmit it, and store it somehow.

It's files on a computer. Those always have an order. Acting like there isn't an order takes active work.

> Which is after all, why it's not true compression. When you account for that metadata, the "compressed" data is not smaller than the original.

Yeah sure, I have never disagreed on this.

> In the OP, the cheat was using filenames to store that data.

Let me make my argument extra clear, and you can tell me if you disagree with either point, and exactly how you disagree with that point:

A) OP did not do anything untoward with filenames. They did a simple loop and even threw away the actual contents of the filename. Even code that wasn't cheating would have a similar use of filenames.

B) OP's trick is not "based on" filenames, it's based on having an order. There are many ways to have an order, and their choice of using filenames is very shallowly integrated into their code.

Re: The $5000 Compression Challenge (2001)

#173

Post by gus_massa »

mhandley wrote: post #147
gus_massa wrote: post #132

Earlier quoted context omitted.

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…

Yes, I think it is quadratic. I don't claim it's practical (the original isn't practical either though), but just that the dependency on filenames isn't fundamental.

> I don't claim it's practical

Don"t interpret my comment as a complain, I was just triying to understand.

This is reposted from time to time, but I don't remember someome proposing this trick before. It's a nice idea.

Re: The $5000 Compression Challenge (2001)

#174

Post by anamexis »

Dylan16807 wrote: post #172
anamexis wrote: post #171

Earlier quoted context omitted.

> 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. 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. I guess that's where we disagr…

> I guess that's where we disagree. I think you don't have an order by default, you need to explicitly define it, and transmit it, and store it somehow. It's files on a computer. Those always have an order. Acting like there isn't an order takes active work. > Which is after all, why it's not true compression. When you account for that metadata, the "compressed" data is not smaller than the original. Yeah sure, I hav…

Sure, I disagree with this:

B) OP's trick is not "based on" filenames, it's based on having an order. There are many ways to have an order, and their choice of using filenames is very shallowly integrated into their code.

I think this is a distinction without a difference. OP's trick is based on having an order via filenames. They could have used a different trick that used something besides filenames for ordering, but they didn't.

If instead of asking if he could use multiple files, he asked if he could use a tar file, or email each file separately and specified that they should be fed to the decompressor in order, he would likely have been declined outright because the cheat is more obvious.

Re: The $5000 Compression Challenge (2001)

#175

Post by Dylan16807 »

anamexis wrote: post #174
Dylan16807 wrote: post #172

Earlier quoted context omitted.

> I guess that's where we disagree. I think you don't have an order by default, you need to explicitly define it, and transmit it, and store it somehow. It's files on a computer. Those always have an order. Acting like there isn't an order takes active work. > Which is after all, why it's not true compression. When you account for that metadata, the "compressed" data is not smaller than the original. Yeah sure, I hav…

Sure, I disagree with this: B) OP's trick is not "based on" filenames, it's based on having an order. There are many ways to have an order, and their choice of using filenames is very shallowly integrated into their code. I think this is a distinction without a difference. OP's trick is based on having an order via filenames. They could have used a different trick that used something besides filenames for ordering, b…

Okay, well I can respect that interpretation enough. I don't quite see it that way but I don't think I'm going to convince you.

Specifically I don't think it rises to the level of violating rules on filenames. That's why I think the distinction can matter.

Re: The $5000 Compression Challenge (2001)

#176

Post by l33t7332273 »

Dylan16807 wrote: post #169
l33t7332273 wrote: post #141

Earlier quoted context omitted.

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.

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

The line about filename shenanigans being disallowed.

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

I think it’s completely clear that this FAQ was about the challenge.

Re: The $5000 Compression Challenge (2001)

#177

Post by Dylan16807 »

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.

It's a limited risk. Even if the file is compressible by one byte, it's very unlikely you can figure out how to get a decompressor functioning without plenty of bytes of overhead. And even if that problem disappears, he'd still win 99.6% of the time.

And you can get rid of that risk by requiring 100 bytes of shrink. Just measure the size right.

Re: The $5000 Compression Challenge (2001)

#178

Post by ultimafan »

sfink wrote: post #119
samatman wrote: post #110

I think Mike is correct. My reasoning by analogy follows. There's a game called Skedaddle, and a Usenet group, rec.players.skedaddle. A well-known player, Mike, offers a $5000 challenge for a feat, called the four-froot-hoot, which he believes is simply impossible to achieve. A fellow skedaddling enthusiast, Patrick, takes him up on the challenge, some baseline terms are negotiated, and Patrick presents his putative…

But the challenge wasn't for performing four-froot-hoot, the challenge was described in text and adhered to. Mike thought he was describing four-froot-hoot, but accidentally only made the challenge about four-froot. The club rules even described why four-froot was not an interesting challenge unless it were four-froot-hoot, which makes it doubly on Mike to issue the challenge for four-froot-hoot and not just four-fro…

This is really how I see it too. If this spirit was really so important to the bet (and not just vaguely implied) it should have been stated clearly. Friendly ribbing over "you won by rules but not in spirit" is one thing when it's a free wager between buddies but not with real money on the line. Falling back on a position of spirit and intent trumping hard written rules in text in real money wagers basically guarantees that the banker has no real incentive to rule fairly on a win that can cost him money if he can get away with the loss of reputation- he can always weasel out of it one way or another by acting in bad faith and engaging in pedantry during the judging. No one would ever take up someone on a bet if they could turn around last second and say, well you didn't mind-read the additional rules and stipulations I'm adding on now after the fact to our original written agreement so in actuality you lost.

Additionally Mike's behavior during the exchange makes him feel all the more untrustworthy. His condescension, playing the fool and intentionally misinterpreting the test to "win", remarks made that seem specifically placed to needle and aggravate Pat knowing there's no way to force him to pay up, and threats of accusations of fraud were a show of really poor character. At the least it would've been more of a class act (even if he never paid out) to admit that Pat outplayed him due to naivety and a self inflated sense of cleverness on Mike's part, to admit that he is not familiar with betting culture and got in over his head.

Re: The $5000 Compression Challenge (2001)

#179

Post by Dylan16807 »

l33t7332273 wrote: post #176
Dylan16807 wrote: post #169

Earlier quoted context omitted.

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.

>Which line in the FAQ are you making an analogy to? The line about filename shenanigans being disallowed. >A FAQ for the newsgroup is not automatically part of the rules for the challenge. I think it’s completely clear that this FAQ was about the challenge.

> The line about filename shenanigans being disallowed.

I don't think that person was being verbatim or summarizing well, can you find support in the actual FAQ?

The part where the FAQ calls out filenames, the example is lmfjyh.c putting the entire program in the filename. Nothing like that is happening here.

The FAQ does talk about being so strict you can't even get bit length, but that kind of strictness is clearly not being applied to Mike's challenge.

> I think it’s completely clear that this FAQ was about the challenge.

Unless I missed there being two FAQs, you have completely misread the situation.

This is the FAQ: http://www.faqs.org/faqs/compression-faq/part1/index.html

It is not about the challenge.

Re: The $5000 Compression Challenge (2001)

#180

Post by tugu77 »

Dylan16807 wrote: post #175
anamexis wrote: post #174

Earlier quoted context omitted.

Sure, I disagree with this: B) OP's trick is not "based on" filenames, it's based on having an order. There are many ways to have an order, and their choice of using filenames is very shallowly integrated into their code. I think this is a distinction without a difference. OP's trick is based on having an order via filenames. They could have used a different trick that used something besides filenames for ordering, b…

Okay, well I can respect that interpretation enough. I don't quite see it that way but I don't think I'm going to convince you. Specifically I don't think it rises to the level of violating rules on filenames. That's why I think the distinction can matter.

The rules should bar contestents from saving entropy outside the payload of the file. Whether that's in a file name or some file system data structure or in some timing side channel is insubstantial.

And once you ban that, it's impossible from an information theoretic point to win the challenge.

Post reply on HN