Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Yep. Consider the minimum case: assume we've described a process for finding any bitstream we want in pi while necessarily saving at least one bit. Attempt to do so for the bitstreams 00, 01, 10, and 11. If we compress 2 bits to 1 bit, by the pigeonhole principle, at least one of 0 and 1 has to represent at least 2 distinct bitstreams, which means we have lost data.

A similar argument works for all compression algorithms and all sizes. It is flatly impossible to compress all data all of the time.



"It is flatly impossible to compress all data all of the time." Might I add "...such that the uncompressed data is recoverable."

Pedantically speaking, any data passing through a cryptographic hash algorithm is being compressed.


Pedantically, that's not compression.





Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: