3 ms·
>When I read the challenge, and saw that arbitrary Unix programs were allowed, my first idea for a compressor was to scan the OS software for snippets of data t
by im3w1l 14y ago
>When I read the challenge, and saw that arbitrary Unix programs were allowed, my first idea for a compressor was to scan the OS software for snippets of data that match the source data.
No this would not work. It is very simple to see this. There are more files with size n, than with there are with lower sizes. A decompressor should therefor be a surjective function from a smaller set to a larger which is impossible. This applies no matter how you construct you (de)compressor. You can have it access word lists, files on harddrive, etc. There will be at least one file it wont be able to compress and then decompress.
- lurker14 14y agoI was slightly vague in my oroginal post. I didn't mean "match completely the soruce data", I meant "match a part of the source data", as a standard rsync/Exchange-style block-deduplicator would do. Per the challenge, it need not work on every file, only the one the challenger chose to provide. If the challenger is not suspecting this attack, he won't know to make sure to pick one of the many source files that are resistant to the attack. Of course the compression is impossible in general, if the task is sufficiently rigorously described, which it wasn't in this case.
- im3w1l 14y agoA randomly generated file will in a crushing majority of cases not be compressible in this way.