3 ms·
No, there is no way this could be done, because there is no way to know which of multiple colliding inputs was the right one. Imagine a one-bit hash function. Y
by stouset 8y ago
No, there is no way this could be done, because there is no way to know which of multiple colliding inputs was the right one. Imagine a one-bit hash function. You start your “decompression” process and read in a 0. What input produced that bit? Literally fifty percent of all possible strings would produce that same output. Without more information, you cannot choose between them. And the information needed to choose correctly is exactly the same amount of information in the original input.
https://en.m.wikipedia.org/wiki/Pigeonhole_principle https://en.m.wikipedia.org/wiki/Pigeonhole_principle
- greiskul 8y agoYup, the pigeonhole principle really defines a hard limit on compression, in that it is impossible to compress (make smaller) ALL files. The way compression algorithms get around that, is by abusing the fact that we rarely want to send around arbitrary data, real world data has lots of redundancy in it, so we can make algorithms where real world data gets mapped into compressed files smaller then they are (by finding the redundancies in the data), and purely random data gets mapped into files that are actually slightly longer than the data.
- caf 8y agoOften rendered as the pithy phrase "A compression algorithm is actually an expansion algorithm with some interesting failure cases."