4 ms·

The "custom algorithm" thing is a red herring. You'll need to use some method to come up with your custom algorithm, once you see the input file, and whatever m

by davmre 12y ago

The "custom algorithm" thing is a red herring. You'll need to use some method to come up with your custom algorithm, once you see the input file, and whatever method you choose is itself a compression procedure, targeted at a fixed decoder which is essentially a Bash shell with a C compiler (* ). If you intend to treat different inputs differently (e.g., "if it contains the string "AB", I'll use this algorithm, if it has more zeros than ones, I'll use this other one, etc"), this just means that your compression procedure contains some 'if' statements. The laws of information theory don't care whether your compression procedure is actually a computer program or just implicitly encoded into human actions; it's still impossible to reliably represent random data with fewer than the usual number of bits. (* ) There's a little bit of leeway here because the challenge as stated isn't actually precise about the execution environment. You could probably sneak in a small number of illicit bits by negotiating out-of-band whether the decompressor is to be a C program, ELF binary, Perl script, etc. It's not obvious how to make this useful though.

function_seven 12y ago
> If you intend to treat different inputs differently (e.g., "if it contains the string "AB", I'll use this algorithm, if it has more zeros than ones, I'll use this other one, etc"), this just means that your compression procedure contains some 'if' statements. The laws of information theory don't care whether your compression procedure is actually a computer program or just implicitly encoded into human actions; it's still impossible to reliably represent random data with fewer than the usual number of bits. While you're obviously correct about the information theory aspect of this, in this particular challenge, the contestant enjoys the privilege of pruning his decompressor to match just the one file. All the other "if" statements can be thrown away. So now a lossy algorithm can be used, that just happens not to be lossy on that one particular file.
- davmre 12y ago
  I understand that the contestant gets to specify a "decompressor"; my point is that this is not information-theoretically relevant. The real decompressor in this challenge is the Linux/C runtime environment. The "decompression" program you send is really just part of the compressed payload, and whatever steps you, as a human, take to produce the compressed payload (encompassing both the code and data portions) are ultimately governed by information theoretic limitations. Another way to say this is that although you have the 'privilege' of a designing a custom decompressor for this one file, this is not really a benefit since your custom decompressor counts against the space limit. (in contrast to the typical information-theoretic setting where the channel can have an arbitrary pre-specified decoder).
  - function_seven 12y ago
    Yeah, it's not a benefit, except if the challenge-giver makes a mistake and offers a file that happens to have nicely-compressible characteristics. Basically you're spending $100 on the hopes that the file you're tasked with compressing just happens to have low enough entropy that it can be successfully compressed by more than the decompressor's size. Not a good bet to take. > my point is that this is not information-theoretically relevant. Exactly. This whole post is about the challenger trying to be clever with the rules and trying to sidestep the core information theory.

by davmre 12y ago

function_seven 12y ago

> If you intend to treat different inputs differently (e.g., "if it contains the string "AB", I'll use this algorithm, if it has more zeros than ones, I'll use this other one, etc"), this just means that your compression procedure contains some 'if' statements. The laws of information theory don't care whether your compression procedure is actually a computer program or just implicitly encoded into human actions; it's still impossible to reliably represent random data with fewer than the usual number of bits. While you're obviously correct about the information theory aspect of this, in this particular challenge, the contestant enjoys the privilege of pruning his decompressor to match just the one file. All the other "if" statements can be thrown away. So now a lossy algorithm can be used, that just happens not to be lossy on that one particular file.

davmre 12y ago
I understand that the contestant gets to specify a "decompressor"; my point is that this is not information-theoretically relevant. The real decompressor in this challenge is the Linux/C runtime environment. The "decompression" program you send is really just part of the compressed payload, and whatever steps you, as a human, take to produce the compressed payload (encompassing both the code and data portions) are ultimately governed by information theoretic limitations. Another way to say this is that although you have the 'privilege' of a designing a custom decompressor for this one file, this is not really a benefit since your custom decompressor counts against the space limit. (in contrast to the typical information-theoretic setting where the channel can have an arbitrary pre-specified decoder).
- function_seven 12y ago
  Yeah, it's not a benefit, except if the challenge-giver makes a mistake and offers a file that happens to have nicely-compressible characteristics. Basically you're spending $100 on the hopes that the file you're tasked with compressing just happens to have low enough entropy that it can be successfully compressed by more than the decompressor's size. Not a good bet to take. > my point is that this is not information-theoretically relevant. Exactly. This whole post is about the challenger trying to be clever with the rules and trying to sidestep the core information theory.