3 ms·
The pigeonhole principle means that compression can never be effective on average. For every input that can be compressed, there must be others that are expande
by mikeash 10y ago
The pigeonhole principle means that compression can never be effective on average. For every input that can be compressed, there must be others that are expanded, such that the average compression ratio is at best 1.
Useful compression algorithms take advantage of the fact that inputs aren't evenly distributed. Real-world data tends to have repetition, self-similarity, or predictability, which real-world algorithms use to produce smaller output.
It's unlikely that πfs would provide useful compression for any real data, since it would have to line up entirely by random chance.