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

61–70 of 192 posts

Re: The $5000 Compression Challenge (2001)

#61

Post by elahieh »

fxtentacle wrote: post #5

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.

Re: The $5000 Compression Challenge (2001)

#62

Post by Jerrrry »

_hark wrote: post #58
dooglius wrote: post #49

Earlier quoted context omitted.

This seems to assume that there is a tractable way to encode H efficiently, but this seems very difficult given a model that is focused on understanding the content. Ex: I can easily write a program that can do basic arithmetic, but given say a bitmap scan of elementary school math materials, such a program gives me no easy way to compress that; rather something generic like PNG (that does not know or understand the…

Great point. This points to the related issue: what do we want to compress? Do we want to compress "the answer", here the arithmetic expression's solution, or do we want to compress the image? You can formalize this with rate--distortion theory, by defining a distortion function that says what your objective is. That implies a well-defined complexity relative to that distortion function. Okay to be clear, I've writte…

  >Okay to be clear, I've written a paper on exactly this topic which will be announced in a week or so. So you won't find anything on the subject yet, haha. But I use almost exactly this example.
I would use Floating Point arithmetic as the example/analogy: one trades off accuracy/precision for exactness/correct-ness when in the extremities. Answers near the more granular representations will be only be able to represented by their nearest value. If this is forsee-able, the floating point implementation can be adjusted to change where the floating point's "extremities'" are.

I used the above analogy and the following when articulating the magnitude of near-lossless-ness that large LLM's have managed to attain, especially when all of the humanities corpus is compressed into a USB flash drive; the Kolmogorov complexity re-mitted/captured is similar to a master-piece like the Mona Lisa having to be described in X many brush-strokes to achieve Y amount of fidelity.

Re: The $5000 Compression Challenge (2001)

#63

Post by [deleted] »

Dylan16807 wrote: post #53
spencerflem wrote: post #35

Earlier quoted context omitted.

That's how all compressors work, in that likely files (eg. ASCII, obvious patterns, etc) become smaller and unlikely files become bigger.

> likely files (eg. ASCII, obvious patterns, etc) become smaller Likely files for a real human workload are like that, but if "most inputs" is talking about the set of all possible files, then that's a whole different ball game and "most inputs" will compress very badly. > unlikely files become bigger Yes, but when compressors can't find useful patterns they generally only increase size by a small fraction of a perce…

[deleted]

Re: The $5000 Compression Challenge (2001)

#64

Post by teo_zero »

Mike supports $SPORT team the Compressors. He's so sure they are unbeatable that he accepts 50:1 bets against them. Patrick bets 100$ that they won't win this year's championship; Mike accepts. Later, the Compressors announce financial troubles and can't pay the fee to enter the championship, which is then won by another team. Patrick reclaims his 5000$. Mike refuses to pay saying that the Compressors have not been beaten, and the championship result does not disprove his claim that the Compressors are unbeatable, which was the spirit of the bet since the beginning. Mike offers to refund the 100$. Patrick holds that the terms of the bet were met and he deserves the 5000$.

Re: The $5000 Compression Challenge (2001)

#65

Post by kevinventullo »

l33t7332273 wrote: post #57
lambdaone wrote: post #28

Earlier quoted context omitted.

This is actually an extremely interesting question. 'Weak' files that are more easily compressable than others certainly exist, but with low probability. For example, the all-zeros file is a member of the set of all random 3 megabyte files, and it would certainly be possible to compress that, if by great good fortune you were lucky enough to receive it - albeit something that is unlikely to ever happen in the possibl…

One thing you can do, as the other commenter pointed out, is consider entropy of the file. However, this restriction is too much for the purposes of this challenge. We don’t actually need a file with low entropy, in fact I claim that a weak file exists for files with entropy 8 (the maximum entropy value) - epsilon for each epsilon > 0. What we actually need is a sufficiently large chunk in a file to have low entropy.…

Note that if this large chunk occurs in the middle of the file, then you will need extra space to encode that position. For example, a random bit string of length 2^n is decently likely to have a run of n zeroes. But this doesn’t help you because you need n bits just to encode where that run happens.

Re: The $5000 Compression Challenge (2001)

#66

Post by stavros »

l33t7332273 wrote: post #51
stavros wrote: post #29

Sorry, if you're trying to hustle people by xstging $100 per try, don't catch the sleight of hand in the "multiple files" question, and accept, you were beaten at your own game, fair and square.

I feel like if the FAQ requires not using filename shenanigans then the slight of hand was illegal the whole way.

He didn't use filenames, he used files, and if that were illegal, Mike shouldn't have accepted it.

Re: The $5000 Compression Challenge (2001)

#67

Post by PaulKeeble »

echoangle wrote: post #40
PaulKeeble wrote: post #36

I would not have accepted multiple files nor scripting. Scripts offers up the entire contents of the linux operating system and this could allow you to use operating system files as partial data. To really test compression/decompression the rules need to be a lot tighter. The challenge was met and beat because the criteria was bad. It leaves open a number of dishonest approaches. The decompression program needs to be…

> Scripts offers up the entire contents of the linux operating system and this could allow you to use operating system files as partial data. I also thought about this, but when thinking more about the argument by the challenge creator, I understood that the data in the OS doesn’t help you. If you’re given a file with 100 bits, there are 2^100 possibilities. If you want to compress to 99 bits, there are only 2^99 pos…

One possibility I considered is that your script could use an "apt install" to provide out of band data, you could put the information you need into the operating system from the universe repositories/your own package server.

Re: The $5000 Compression Challenge (2001)

#68

Post by echoangle »

PaulKeeble wrote: post #67
echoangle wrote: post #40

Earlier quoted context omitted.

> Scripts offers up the entire contents of the linux operating system and this could allow you to use operating system files as partial data. I also thought about this, but when thinking more about the argument by the challenge creator, I understood that the data in the OS doesn’t help you. If you’re given a file with 100 bits, there are 2^100 possibilities. If you want to compress to 99 bits, there are only 2^99 pos…

One possibility I considered is that your script could use an "apt install" to provide out of band data, you could put the information you need into the operating system from the universe repositories/your own package server.

The computer used for the test probably doesn’t have network connectivity, otherwise you could just download the data with curl.

Re: The $5000 Compression Challenge (2001)

#69

Post by nojvek »

I’d take this bet.

> With this offer, you can tune your algorithm to my data.

One can generate a 1GB file or 10GB file. It is highly likely that there is some form of a repeatable pattern in there to shave off 50-100 bytes by sliding window search.

Then the decompressor is essentially - at this index, expand this pattern. The compressed file excludes the range of pattern.

One may not always get such a pattern, but on multiple tries it’s very feasible. Payout just needs one win in 50 tries.

You could generate a 100GB file. The bigger the file the higher the chance of repeating pattern.

The challenge is won if compressed_file + decompressor is less one byte than original file.

One could have a self executing decompressor to save some file overhead bytes.

Re: The $5000 Compression Challenge (2001)

#70

Post by Jerrrry »

nojvek wrote: post #69

I’d take this bet. > With this offer, you can tune your algorithm to my data. One can generate a 1GB file or 10GB file. It is highly likely that there is some form of a repeatable pattern in there to shave off 50-100 bytes by sliding window search. Then the decompressor is essentially - at this index, expand this pattern. The compressed file excludes the range of pattern. One may not always get such a pattern, but on…

good compression = pattern eventually

maximum compression = indelineable from random data

Post reply on HN