4 ms·

> There is a limit beyond which you can't compress data any further, called the Shannon limit. I think you are confusing things a bit here. The Shannon limit h

by ot 13y ago

> There is a limit beyond which you can't compress data any further, called the Shannon limit. I think you are confusing things a bit here. The Shannon limit has nothing to do with lossless compression, it refer to communication in noisy channels. What you are referring to is the Shannon entropy, but even that is not actually a lower bound to compression of actual data, because it is defined for stochastic sources. When you have an actual string and you want to compress it, the only meaningful lower bound is the Kolmogorov complexity of the string, that is the size of the smallest program that generates that string. It is of course incomputable, but it is what you would get if you had infinite computing power.

sillysaurus2 13y ago
I appreciate you correcting my terminology, but beyond that you haven't actually disagreed with anything I've said. Humans call it either the Shannon limit, or Shannon entropy, or Kolmogorov complexity of a string, or whatever other name humans have come up with for human names. The central point is there is some limit which you can't circumvent through trickery like "find it embedded within pi," regardless of what species you are, or what your species chooses to name fundamental limitations of nature. A program to generate digits of pi is small, and pi embeds every possible string. But generating up to that offset of pi is impossible in practice. And it probably won't net you any savings anyway, since you'll still need to communicate the offset. The offset's length in digits is probably close to the length of the original string (after perfect compression), so it's unlikely you'd be able to circumvent Shannon entropy. But, if you do manage to create a practical way to bypass Shannon entropy, I'd imagine it'll be headline news, along with netting you quite a lot of money.
- iliis 13y ago
  If you're talking about Kolmogorov Complexity here, you can't really "circumvent" it. Kolmogorov Complexitiy of a string is basically defined as the size of the shortest possible representation of said string. If you manage to"bypass" the Kolmogorov Limit you actually just "lowered" it (well, it alwayws was by definition this low). Your main point is totally valid however. You cannot compress infinitely. A simple proof: For any given N bits you can encode [at most] 2^N different strings. As there exist more than N strings there must be one which cannot be represented by N bits. As N can be arbitrarily large you'll always find strings which cannot be compressed lower than some chosen size. QED.
kevgnulldev 13y ago
Of related interest: http://mitpress.mit.edu/books/minimum-description-length-principle http://mitpress.mit.edu/books/minimum-description-length-pri... http://arxiv.org/abs/math/0406077 http://arxiv.org/abs/math/0406077

by ot 13y ago

sillysaurus2 13y ago

I appreciate you correcting my terminology, but beyond that you haven't actually disagreed with anything I've said. Humans call it either the Shannon limit, or Shannon entropy, or Kolmogorov complexity of a string, or whatever other name humans have come up with for human names. The central point is there is some limit which you can't circumvent through trickery like "find it embedded within pi," regardless of what species you are, or what your species chooses to name fundamental limitations of nature. A program to generate digits of pi is small, and pi embeds every possible string. But generating up to that offset of pi is impossible in practice. And it probably won't net you any savings anyway, since you'll still need to communicate the offset. The offset's length in digits is probably close to the length of the original string (after perfect compression), so it's unlikely you'd be able to circumvent Shannon entropy. But, if you do manage to create a practical way to bypass Shannon entropy, I'd imagine it'll be headline news, along with netting you quite a lot of money.

iliis 13y ago
If you're talking about Kolmogorov Complexity here, you can't really "circumvent" it. Kolmogorov Complexitiy of a string is basically defined as the size of the shortest possible representation of said string. If you manage to"bypass" the Kolmogorov Limit you actually just "lowered" it (well, it alwayws was by definition this low). Your main point is totally valid however. You cannot compress infinitely. A simple proof: For any given N bits you can encode [at most] 2^N different strings. As there exist more than N strings there must be one which cannot be represented by N bits. As N can be arbitrarily large you'll always find strings which cannot be compressed lower than some chosen size. QED.

kevgnulldev 13y ago

Of related interest: http://mitpress.mit.edu/books/minimum-description-length-principle http://mitpress.mit.edu/books/minimum-description-length-pri... http://arxiv.org/abs/math/0406077 http://arxiv.org/abs/math/0406077