3 ms·
The problem in general with this approach is that the amount of bits it takes to identify the correct decoded value exceeds the amount of bits it takes to simpl
by jerf 6y ago
The problem in general with this approach is that the amount of bits it takes to identify the correct decoded value exceeds the amount of bits it takes to simply write down the correct encoded value.
People have been proposing similar algorithms for the last few decades. It's really become the "Free energy is being suppressed by the man!" of compression algorithms. One of the more popular is "just identify where your value is in pi!", which fails for that reason.
One problem is that in order to analyze such algorithms you really need to count your bits carefully. For instance in the pi case people sometimes think "well, I just need two numbers, the distance into pi and the length", but those "two numbers" may need arbitrarily unbounded numbers of bits to represent.
GoL has its own problem which is that if you construct a "random" state that didn't start "naturally" the odds of it being a Garden of Eden state are essentially 1. Can you even call it an "image compression" tool when it can't represent an image of any pure color at all, let alone in a compressed format?
- alpaca128 6y agoExactly, I know first hand that it's easy to believe in such admittedly creative ideas. But thinking it through was fun and cleared up my misunderstanding; in the end the information itself cannot be compressed, one can only reduce redundancies. And an arbitrarily chosen algorithm tends to do a really bad job with that on average.
- dcanelhas 6y agoHaha that's really creative though. Makes me wonder if there is anything useful "stored" in pi that could be represented with, say, 2 64-bit integers.
- klyrs 6y agoFurther "compression" -- you only want the index of the first occurrence of a given string. Thus, you create a table of offsets for each string length, where index 0 is the first unique string of length n, index 1 is the second, etc. This allows you to elide the issue that indices can be arbitrarily large. Of course, the table is hard to compute for large n, and the resulting "compression" has indices at worst the size of the original data... so it's gonna be super efficient at compressing the bits of pi, and no worse than unity on average.