Live data from Hacker News

The $5000 Compression Challenge (2001)

patrickcraig.co.uk

121–130 of 192 posts

Re: The $5000 Compression Challenge (2001)

#121

Story time. In our Data Structures and Algorithms class during my undergrad, we had a similar challenge posed to us by an associate professor who was quite proud of the fact that it had never been beaten. The sophistication of my compression understanding at the time extended to lempel-ziv and huffman and well... that's about it. So I was like, “Okay, I’m not going to create the world’s best compression method on a w…

AND?! What was his response once you had to come clean?

Edit: I loved this (minus the missing ending). Really sucked me in with the level of detail.

Re: The $5000 Compression Challenge (2001)

#122
post #113

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…

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.

Re: The $5000 Compression Challenge (2001)

#124
Yeah, I'd strongly, strongly, in fact plead for people not to try this challenge. When it comes to 'compressing' random data: every single bit in random information is 'significant.' I am quite sure that the problem is logically meaningless, mathematically impossible, and a complete waste of effort. But more-so: if it weren't a waste of effort (it is) - I would still highly doubt any algorithm existed that was more efficient than brute force search. In this case -- the search for a function that solves the constraints is going to be like trying to brute force a cryptographic private key value. Simply because every 'bit' of entropy is valuable information.

Now lets look at how modern compression actually: works. Images, movies, text-documents, audio files... there is fundamental --structure-- in all this data. In text it might be using only a certain character range, a certain lexical word list, and so on. There may be geometric information in images and movies that could be turned into code to drastically cut down file size. With audio -- you can sample it and discard what you don't need. And so on and so fourth. Structure. But how do you apply any of these methods to random data? There is no structure, you can't sample it, reduce it, simplify it... Every bit has meaning.

So please, dear human thinking about compression of random data. It is an insane waste of intellectual effort. It's impossible. Don't do it. I made the same mistake (and setup vast amounts of HPC to work on algorithms.) COMPLETE. Waste of time.

Re: The $5000 Compression Challenge (2001)

#126

Earlier quoted context omitted.

That's not how seeds work. Seeds are tiny. Actually this would work perfectly if you knew it was generated in a single pass by a known random number generator and you had tons of time to brute force it. If the file were generated by a natural source of entropy then forget it. Or even if modified in a trivial way like adding 1 to every byte.

What is with the many downvotes but no comments? Everything I said is factual. Seeds are something like 32 bits, though it depends on the exact implementation. But not the length of files.

When implementing a PRNG, you can make its seed as big as you want. There is no mathematical law that dictates or limits the size of a seed.

Re: The $5000 Compression Challenge (2001)

#127

I didn’t quite get the method used to „compress“ the data from the article, maybe this rephrasing helps someone: You basically split the file every time you encounter a specific character, and your compressor just combines all files it finds with the character you split by. If you split at every „X“ Char which might occur 1000 times in the file, the compressor only needs a small script which joins all files and puts…

Almost.

The trick is the missing character is static, in the 'decompressor'. It's inserted between every segment which was trimmed to end where that character existed in the original.dat file. The numbers at the end of each segment file correspond to the segment number, as bourne shells increment numbers. It does not handle errors or validate the output.

It does fulfill the discussed terms of the challenge, which fail to include any reference to an external set of rules.

Re: The $5000 Compression Challenge (2001)

#128
post #61

This guy clearly failed because he didn't actually do any compression, he just ab-used the filesystem to store parts of the data and then tried to argue that metadata was not data... But FYI someone else actually managed to compress that exact same data: https://jasp.net/tjnn/2018/1.xhtml

I'm rather skeptical of this claim that the data was compressed in 2018 because there is no further information, apart from a hash value given. If it's a true claim they must have identified some "non-random" aspect of the original data, and then they could have given more info.

Not necessarily. Consider a big file of random uniformly distributed bytes. It's easy to show that in practice some bytes are more common than others (because random), and that necessarily therefore the expected spacing between those specific bytes is less than 256, which gives you a small fraction of a bit you can save in a recoding of those specific bytes (distance from last byte of a specific value).

With a big enough file those fractions of a bit add up to a non trivial number of bits. You can be cunning about how you encode your deltas too (next delta makes use of remaining unused bits from previous delta).

I haven't worked through all the details, so it might be in the end result everything rebalances to say no, but I'd like to withhold judgement for the moment.

Re: The $5000 Compression Challenge (2001)

#129

Earlier quoted context omitted.

He does use the filenames. If you change the filenames randomly (such that the files sort differently), it does not work.

> such that the files sort differently But if you change them without making them sort differently, everything is fine. He depends on the order, not the filenames. You could even remove the filenames entirely, as long as you patch the code to account for such a strange environment.

Not really a good point. If the order of bytes does not matter, then I can compress any file of your liking to O(log n) size :P

Re: The $5000 Compression Challenge (2001)

#130
post #82

Earlier quoted context omitted.

The issue with the invariance theorem you point out always bugged me. Let s be an algorithmically random string relative to UTM A. Is it the case that there exists some pathological UTM S, such that K(s|S) (the Kolmogorov complexity of s relative to S) is arbitrarily small? I.e. the blank print statement of S produces s. And there always exists such an S for any s? Is there some way of defining a meta-complexity meas…

> Is it the case that there exists some pathological UTM S, such that K(s|S) (the Kolmogorov complexity of s relative to S) is arbitrarily small Yes. It’s not even that hard to create. Just take a standard UTM and perform a branching “if” statement to check if the input is the string of interest before executing any other instructions. > Is there some way of defining a meta-complexity measure, the complexity of some…

Interesting. I guess then we would only be interested in the normalized complexity of infinite strings, e.g. lim n-> \infty K(X|n)/n where X is an infinite set of numbers (e.g. the decimal expansion of some real number), and K(X|n) is the complexity of the first n of them. This quantity should still be unique w/o reference to the choice of UTM, no?
Post reply on HN