91–100 of 192 posts
Likewise this challenge would have been stronger if the requirement was to compress two provided arbitrary files :P
The original email thread was from 2001, and it gets posted to HN periodically: https://news.ycombinator.com/from?site=patrickcraig.co.uk For another compression challenge that is still ongoing, try "500000€ Prize for Compressing Human Knowledge" (also known as "Hutter Prize"): http://prize.hutter1.net/ https://news.ycombinator.com/item?id=37502329 - Hutter Prize for compressing human knowledge (2023-09-13, 215 comme…
Earlier quoted context omitted.
I have a fundamental problem with the Hutter prize stating that intelligence is related to compression & then sponsoring a prize for lossless compression. Intelligence is related to lossy compression. Lossless is mainly a mechanistic act.
Marcus Hutter is free to sponsor a prize according to his definition of intelligence. You are free to sponsor a prize according to your intelligence definition involving a lossy compression.
Are you trying to imply that people need to put up big sums of money when they want to critique someone else's definitions be taken seriously? If yes, I think that's ridiculous. If no, I can't figure out the point of your comment.
Earlier quoted context omitted.
He didn't use filenames, he used files, and if that were illegal, Mike shouldn't have accepted it.
He does use the filenames. If you change the filenames randomly (such that the files sort differently), it does not work.
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.
Earlier quoted context omitted.
He didn't use filenames, he used files, and if that were illegal, Mike shouldn't have accepted it.
He does use the filenames. If you change the filenames randomly (such that the files sort differently), it does not work.
What you're saying is like saying that you encoded info in filenames because decompress.sh expects a file "compressed.dat" to exist. It's not describing any meaningful part of the scheme.
I would have expected it to be possible to compress a single arbitrary random file with a small program. I would have thought an RNG could generate a file with some weakness that allows you to compress it, although said compressor would be worse at other inputs. Likewise this challenge would have been stronger if the requirement was to compress two provided arbitrary files :P
Which is basically what he’s done here. He’s cheating by marking the location of the repeating sequence using unique files, rather than some other actually more efficient location system.
This is a fun discussion! I think it helps to make compression feel more approachable for armchair enthusiasts.
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…
My take was that the information is stored in the ordering of the files. The decompressor doesn't care about the file size of each file, right?
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.
Not in any significant way. The decompressor could be changed to require you to feed the files into it in the correct order or expect some other sorting. What you're saying is like saying that you encoded info in filenames because decompress.sh expects a file "compressed.dat" to exist. It's not describing any meaningful part of the scheme.
You are combining different parts and inserting a missing byte every time you combine the files. You need to combine the parts in the correct order, and the order is part of the information that makes this work.
If the ordering isn't coming from filenames, it needs to come from somewhere else.
There's another interesting loophole to these general compression challenges. A universal Turing machine will necessarily compress some number of strings (despite the fact that almost all strings are incompressible). The set of compressible strings varies depending on the choice of UTM, and if your UTM if fixed, you're out of luck for random data. But if the UTM is unspecified, then there exist an infinite number of…
UTM provides no gain.
The original email thread was from 2001, and it gets posted to HN periodically: https://news.ycombinator.com/from?site=patrickcraig.co.uk For another compression challenge that is still ongoing, try "500000€ Prize for Compressing Human Knowledge" (also known as "Hutter Prize"): http://prize.hutter1.net/ https://news.ycombinator.com/item?id=37502329 - Hutter Prize for compressing human knowledge (2023-09-13, 215 comme…
I have a fundamental problem with the Hutter prize stating that intelligence is related to compression & then sponsoring a prize for lossless compression. Intelligence is related to lossy compression. Lossless is mainly a mechanistic act.
I think the other way to read it is that you're fundamentally going to have to choose (by your freedom to control your algorithm's design) which of the maps from (2^|x|) -> (2^|compress(x)|) are the ones that actually end up getting no compression (ie |compress(x)| actually > |x| - bc of pigeonhole principle) and which ones are the ones that do get to be called compressed. So you do have an implied kind of lossiness w.r.t. to what parts of the input domain are actually compressed.