3 ms·
They just mean that there is no general way to compress an arbitrary M-bit string to an N-bit string for M > N, and yet compression algorithms exist. The point
by kevinventullo 7y ago
They just mean that there is no general way to compress an arbitrary M-bit string to an N-bit string for M > N, and yet compression algorithms exist.
The point is that the input to your compression is not an arbitrary M-bit string, but some very structured thing which could have a smaller representation. Similarly, when encountering what appears to be an NP-hard problem in the wild, you might still be able to find an efficient solution by exploiting the structure of your input (NP-hardness only applies when considering all inputs).
- areyousure 7y agoOne major issue is that the quote seems entirely backwards. In fact, Claude Shannon described how to optimally compress a string from a known source. https://en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem https://en.wikipedia.org/wiki/Shannon%27s_source_coding_theo... As such, Shannon's results would suggest the existence of many compression algorithms. (And conversely, I see no reason to believe that "Claude Shannon proved that generalized compression algorithms can't exist". I assume that result predates Shannon.)
- hinkley 7y agoThe pigeonhole principle establishes that you cannot fit n distinct messages into m spaces, where n>m The Shannon coding limit defines the bounds on what subset of n can fit into a channel of capacity m, without excluding any of the others. By drawing a fence around the possible, he fences out the impossible. comp.compression has several longstanding bets that one particular high entropy input can not be represented by any decoder smaller than the difference in the input and output size, but I lack their confidence in the infallibility of their entropy source. It is possible someone will win that particular bet, but there will come a time where another similar bet will never be collected.