Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The $5000 Compression Challenge

patrickcraig.co.uk

Post reply on HN
Print view View original

171–175 of 175 posts

Re: The $5000 Compression Challenge

#171

Post by path411 »

a_e_k wrote: post #45
im3w1l wrote: post #6

I don't think it is 100% foolproof, even if no filesystem trickery is used. The random number generator used is likely not perfect and so the data should be compressible. I mean it would probably be quite difficult, but maybe possible.

From random.org, used as a source for the data: > RANDOM.ORG offers true random numbers to anyone on the Internet. The randomness comes from atmospheric noise, which for many purposes is better than the pseudo-random number algorithms typically used in computer programs.

Give me a file the size of the universe, and my decompressor will re-sim the universe until the point of the file creation date and read the atmospheric noise from that point.

Re: The $5000 Compression Challenge

#172

Post by caf »

anamexis wrote: post #89
caf wrote: post #88

Earlier quoted context omitted.

In fact this solution doesn't use either the number of files or their filenames to encode additional information - it uses the sizes of those files to encode the additional information.

It does use the filenames, for ordering. If you renamed the files so they sort differently, they would not decompress correctly.

I don't think that's relevant - in a sense the ordering information is only required because using individual files has otherwise destroyed some information (by allowing reordering within the output data).

The same process would work with a single stream input to the decompressor, as long as the length of each block where an additional '5' must be output is available - the list of file sizes - so that's where the additional information is stashed.

Re: The $5000 Compression Challenge

#173

Post by DougBTX »

emn13 wrote: post #157
DougBTX wrote: post #137

Earlier quoted context omitted.

The "compressed" files includes a header file which records the original file name and the number of parts which make up the compressed file, so it doesn't depend on directory listing to re-combine the parts.

Yes, it does. It records the original file name, not the name of the parts, and it needs the names+metadata of those parts (specifically in this case their order) to reconstruct the original file.

Here's the script:

    #!/bin/sh
    i=0
    f=`head -1 $1`
    n=`tail -1 $1`
    rm -f $f
    while [ $i != $n ]; do
        cat $1.$i >> $f
        i=`expr $i + 1`
        if [ $i != $n ]; then printf "5" >> $f; fi
    done
The iteration is done with a while loop based on metatdata from the "compressed" file (the number of parts, $n) and the name of the archive ($1). The order of the parts is determined by incrementing $i up to $n, not from eg, the order of the files in the file system, which seems to be what was implied in the comment earlier.

Re: The $5000 Compression Challenge

#174

Post by kazinator »

eridius wrote: post #167
ghayes wrote: post #87

Earlier quoted context omitted.

> Mike agreed that Patrick could send multiple file, but Mike never agreed that these files would be accepted as a winning submission Then what is "agreeing"? These two sentences appear logically inconsistent.

Huh? Patrick asked if he could send multiple files. Mike said yes. Again, since the context of this is pedantic arguments, agreeing that Patrick could send multiple files is not the same as agreeing that Mike would consider the multiple files to be a winning submission.

I have to logically agree with you. Indeed, Mike never issued a statement like, "I am amending the contest rules so that multiple files decoded by a single program are admitted as a valid solution."

Only, this trickerly was not Mike's intent, otherwise, of course, he would have played this card immediately. For instance:

"I said you could send that to me because that is a true statement with which I therefore agree. It is undeniably true that you can send me anything you like. You can send me an e-greeting card for my birthday, and you can send me a Britney Spears MP3 as a MIME attachment. You can send me questions asking about what you can send me. Obviously, though, the only material which you can send me which also happens to conform to the contest rules is a single program and a single data file. Please re-read the contest statement; I will gladly explain any portion of it that is not clear."

Mike had no need to complain that the program isn't a decompressor. He should have played it as above.

Instead, he demonstrated acceptance of the the multi-file structure of the solution by complaining that the algorithm in the program file isn't a form of compression.

Re: The $5000 Compression Challenge

#175

Post by andrewaylett »

prettyrandom100 wrote: post #166
andrewaylett wrote: post #161

Earlier quoted context omitted.

It's not that there might be a collision, but that collisions are guaranteed . How many 3Mb files are there? 2^(3M 8) = 2^25165824. How many distinct hashes are there? 2^(256 1001) = 2^256256. By the pigeonhole principle, we can't fit 2^25165824 objects into 2^256256 holes; indeed each file will have on average 2^24909568 other files that share the same set of 1001 sha256 hashes. The reason that we are able to work w…

There is just one 3MB file and we divide that file into 1000 parts. I agree there will be collision per hash (for each part). But I'm skeptical that all 1000 hashes will produce such bits so that the final file will cause collision on the hash of the original file (remember we do have hash of the original file). If the final hash does not match the hash of original file we would have to recompute all the hashes again…

Not every collection of 1000 correctly hashed parts will make a correctly hashed whole, but there are an awful lot of different collections of parts that will hash correctly (2^24909824 permutations of them) and of those, one in 2^256 will also match the full-file hash.
Post reply on HN