3 ms·
> I was surprised they didnt advocate multiple runs; eventually all knowledge could be represented in one unquantifiable byte. I've seen many proofs that this
by tzs 6y ago
> I was surprised they didnt advocate multiple runs; eventually all knowledge could be represented in one unquantifiable byte.
I've seen many proofs that this is impossible. Usually they use a counting argument such as the pigeonhole principle, and show that you cannot have a compression function C and matching decompression function U with all the following properties:
1. U(C(f)) == f for any file f of at least one byte. I.e., compression is always reversible.
2. C(f) is never larger than f.
3. C(f) is sometimes smaller than f.
4. For any file f larger that one byte, iterating C a sufficient number of times will result in a file of exactly one byte. Iterating U a sufficient number of times on that one byte will produce f.
Many of the proofs are a little sloppy in how they define or specify things, making it easy to give a counterexample. Here is such a counterexample:
1. Order all possible files of at least one byte as follows:
1a. All n-byte files come before any m-byte file for all m > n.
1b. Order all n-byte files by treating them as 8n-bit unsigned binary numbers and ordering them by ascending numerical value.
2. Let I(f) be the index of file f in that ordered list of all >= 1 byte files. Let F(i) be the file whose index is i. Let Z = the one-byte file whose bits are all 0s. Let E be an empty file.
3. The compression function C(f) is as follows:
C(Z) = E
C(f) = F(I(f)-1) if f != Z
4. The uncompression function U(f) is as follows:
U(E) = Z
U(f) = F(I(f)+1) if f != E
So what's the catch?
Here is the catch. Suppose f1, f2, f3, ... are a bunch of n-byte files. It is true that iterating U enough times on any of them will result in a one-byte file. In fact you can iterate to get each down to a file consisting of a single null byte.
So now you have a bunch of files f1', f2', f3', ... each consisting of a single byte. Imagine you need to get f1 back. OK, you iterate U on f1'.
But how many times do you have to iterate? It will be around 2^(8n) iterations. Get the number of iterations wrong and you'll end up with a different n-byte file.
To make sure that uncompressed f1' gives you f1, not f2, f3, ... or some other n-byte file, you have to remember exactly how many times you iterated C when you compressed f1.
That essentially requires storing an n-byte random integer somewhere. So yeah, you compressed your n-byte f1 down to a 1-byte f1', but a byproduct of that was n bytes of metadata you have to store somewhere. Oops.
- h2odragon 6y agoI was looking at commercial encryption and compression libraries (when that wasn't even black magic yet but more kooks and woo, obviously), for a "fax on computers" text messaging over modems thing. DOS TSR days. We eventually wound up using LZ-like dictionary / codebook data for the various peers which provided compression, and "encoding" obfuscation that was "even better" than encryption; tho we had that too (with fixed/predictable keys). Real key exchange was a user impossibility. Keeping a dictionary wound up being an incredible win because our target market's data was enormously redundant. I was using random usenet text as test data and the real users saw 80% better performance than my tests led me to expect.