{"id":933,"date":"2010-08-03T11:48:17","date_gmt":"2010-08-03T15:48:17","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/?p=933"},"modified":"2010-08-03T11:48:17","modified_gmt":"2010-08-03T15:48:17","slug":"revenge-of-the-return-of-the-compression-idiot","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2010\/08\/03\/revenge-of-the-return-of-the-compression-idiot\/","title":{"rendered":"Revenge of the Return of the Compression Idiot"},"content":{"rendered":"

Do I really<\/em> need to go through this again? Argh!<\/p>\n

As long-time readers will remember, a while back, I had an encounter with
\na crackpot named Jules Gilbert who claimed to be able to cyclically compress
\nfiles. That is, he could take a particular input file, compress it, do
\nsomething to it, and then compress it again, making it smaller. He claimed to
\nbe able to do this for any<\/em> input. <\/p>\n

And to make it more annoying, his claim to be able to do this brilliant
\nmagical cyclical compression was attached to an obnoxious christian “I want to
\nsave you soul” rant, where he effectively offered to share the profits from
\nthis brilliant invention with me, if I’d only give him the chance to tell me
\nabout Jesus.<\/p>\n

I tried to get rid of the schmuck. I asked him to leave me alone politely.
\nThen I asked him to leave me alone not-so politely. Then I asked him to
\nleave me alone very, very rudely. Then I publicly mocked him on this blog.
\nAfter the last, he finally seemed to take the hint and go away.<\/p>\n

Unfortunately, good things often don’t last. And yesterday, I received
\nanother new message from him, bragging about the results of his uber-magical
\ncompression system. He has now perfected it to the point where he can take
\nany<\/em> input file, and compress it down to about 50K:<\/p>\n

\n

I am now compressing single bit as:<\/p>\n

I use C code to pack up one bit to a byte and call bzip2’s compress
\nbuffer.<\/p>\n

I print the result and compute the size.<\/p>\n

(I did this for both gzip and bzip2.) Gzip didn’t compress; it gave
\nme back about 6.25, but I needed at least 8.0.<\/p>\n

And bzip2 gave it to me. About 8.2 and higher. (This is with no
\nactual I\/O, just buffer to buffer.)<\/p>\n

This was with random data. At least that’s what people call it.
\nBzip2 data. (It looks pretty random to me.)<\/p>\n

I expect to show up at a friend’s house and show him the system on
\nMonday. THIS IS NOT A COMPLETE SYSTEM, but it’s not just research
\neither. The input was randomly chosen (not by me, by a C function,)
\nand the program has been arranged to simply open another file when a
\ncurrent file is exhausted.<\/p>\n

Every input file has been compressed once with bzip2. Each input file
\nis at least 5k bytes and was chosen with the intent to represent all
\npopular OS’s somewhat equally.<\/p>\n

This program is easily able to process MN’s 415k file. And since it
\nuses 256 byte blocks, I can bring it down to about 50k (number
\ndemonstrated in testing.) Another way to say this is that (with this
\nprogram,) all files greater than about 50k can be made that small.<\/p>\n

This is the simplist system I have ever made that uses my “modern”<\/p>\n

techniques (I mean, not my LSQ ideas of a decade ago.) i started
\ncoding it this morning, to see if a certain idea worked…<\/p>\n

I’m trying to drop bzip but it’s pretty good! I’m also trying to
\nmodulate my input to it, in order to obtain a gain from the pattern
\nrecognition (the BWT may not be an actual FFT but it’s a similar
\nidea.) If I can do this I will keep it.<\/p>\n

If all this is greek to you, here’s the thing: Just about every other
\ncomputer scientist in the whole wide world believes this is
\nimpossible. Why is this valuable? Because it means that all files
\nand messages can be compressed in while in transit to, say, 50k —
\nprobably much less. (Or while sitting on a CD-ROM or DVD.)<\/p>\n<\/blockquote>\n

I love that line in there: “Just about every other computer scientist in
\nthe whole wide world believes this is impossible”.<\/p>\n

Jules, baby, belief has nothing<\/em> to do with it.<\/p>\n

<\/p>\n

Let’s walk through this one more time. What is a compression system?
\nFundamentally, it’s a function with three properties:<\/p>\n

    \n
  1. It’s computably invertible. That is, if x is an input, and f(x) is the compressed output, there must be a computable function f^{-1} : (forall x) f^{-1}(f(x)) = x.<\/li>\n
  2. It’s one-to-one. It must<\/em> be one-to-one – because if it weren’t it wouldn’t be invertible. If there were two values, x and y where x neq y land f(x) = f(y), then f^{-1} wouldn’t be able to decompress – because it wouldn’t know which value to return for f^{-1}(f(x)).<\/li>\n
  3. For some set of interesting x-values, the size of f(x) is smaller than the size of x.<\/li>\n<\/ol>\n

    In an ideal<\/em> compression function, you’d have the property that f is total, and (forall x) len(f(x)) < len(x).<\/p>\n

    Ideal compression functions are impossible<\/em>. And it’s very easy to prove. Suppose you had a compression function which could remove one bit – just one bit – from any input file. Consider the set of file with N bits. You’d like to be able to compress those to N-1 bits. You can’t<\/em> do it. Why? Because there are 2^{N} possible values with N bits; and there are 2^{N-1} possible values with N-1 bits. You can’t have a total one-to-one function from a set with 2^N values to a set with 2^{N-1} values. Can’t do it. Impossible. Absolutely, totally, profoundly impossible. End of discussion. <\/p>\n

    You might respond: but I’ve got gzip and bzip2 on my computer, and they clearly work! Well, that’s true. They work. For some<\/em> inputs. But not for all. gzip and bzip are based on compression algorithms that exploit the structure of their typical inputs. Text files typically have a huge<\/em> amount of repetition in them – and the LZW family of algorithms that common compressors are built on do a very good job of exploiting that. But they don’t work on everything. Just for one example, I tried compressing an MP3 on my disk. Before compression, its length was 7937898 bytes, After compression by bzip, it’s length was 7972829. “Compressing” the file actually added<\/em> nearly 35,000 bytes. Our compression functions work pretty well on the types of data for which they’re designed, which contain lots of redundancy. But a true, general, ideal compression system? It’s impossible. <\/p>\n

    The usual crackpot response to this is something along the lines of “You just believe<\/em> it’s impossible. Scientists have been wrong before.”<\/p>\n

    The thing is, there are proofs, and then there are proofs. Every proof is dependent on its basic premises. If those premises turn out to be false, then the proof is also false. This has happened lot of times before. For example, back when I was in high school, there was an absolute proof, built using Shannon’s information theory, that you couldn’t transmit data with more than 600 modulations per second over a telephone line. That meant that a modem couldn’t transmit data any faster than 600 bits per second. Not just the kind of modem they built back then, but any<\/em> modem – because it was a fundamental property of the bandwidth of the telephone line.<\/p>\n

    It turned out to be wrong. The proof itself didn’t have any problems – but the model it used for the bandwidth capacity of a telephone line was incorrect. So by the time I started college, 1200bps modems were common; by the time I got to grad school, 28,800bps modems were common; before broadband started hitting the scene, 56,600bps modems were common. That original proof of the bandwidth capacity of a phone line was off by a factor of 100. <\/p>\n

    But computing the bandwidth capacity of a telephone line is remarkably tricky. There are a ton of places where incorrect assumptions about the line can enter the proof – and so, while the proof itself is fine, it’s not a proof about real telephone lines.<\/p>\n

    That’s the kind of problem that you encounter in mathematical proofs about the real world. If the proof is actually valid, its validity in inescapable. But truth and validity are two different things. Truth is, in a vague sense, whether or not the validity of the proof implies anything about some real-world phenomenon that the proof is applied to. Validity is just internal consistency of the proof in its logical system. So a proof can be valid, without a particular application of that proof being true. To determine whether or not a proof is true, you need to check whether or not its axioms actually map correctly onto a real-world application.<\/p>\n

    In the case of this kind of compression nonsense, the mapping between the proof and the real world is incredibly direct. The compressor, in order to work, must<\/em> be a one-to-one function. There is no way that it can decompress if it isn’t. <\/p>\n

    Mr. Gilbert claims that he can take any<\/em> input file, and compress it down to 50K. That is, quite simply impossible.<\/p>\n

    There are 2400,000<\/sup> possible 50K long files. That seems like an astonishingly large number. It’s larger than the number of atoms in the observable universe. It’s a number that’s really beyond the ability of our imagination to comprehend. But… I’ve got a rather large collection of music on my hard-drive. A bit over 30GB worth. The average file there is around 5 megabytes. That’s around 5,000,000 bytes, or\t40,000,000 bits. There are 240,000,000<\/sup> possible files that long.\tAnd Jules is claiming that he can take any<\/em> of those files, and compress them to 50K. It’s an unavoidable fact that even if we restrict all files to be exactly<\/em> 5,000,000 bytes long, then his system must<\/em> be mapping an average of 2^{100} files onto each possible 50K output file. Therefore, his system isn’t one to one – therefore, it isn’t a compression system – i.e., it doesn’t work<\/em>. <\/p>\n

    The number don’t lie. The proof has no holes. There’s no way to do what he claims to be doing. And I’ve explained this before – both in email to him, and in posts on this blog. But some people are so convinced of their own perfect brilliance that they think reality doesn’t apply to them. Sorry Jules, but even with the help of Jesus himself, your stuff can’t<\/em> work. <\/p>\n","protected":false},"excerpt":{"rendered":"

    Do I really need to go through this again? Argh! As long-time readers will remember, a while back, I had an encounter with a crackpot named Jules Gilbert who claimed to be able to cyclically compress files. That is, he could take a particular input file, compress it, do something to it, and then compress […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[7],"tags":[],"class_list":["post-933","post","type-post","status-publish","format-standard","hentry","category-bad-software"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-f3","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/933","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=933"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/933\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=933"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=933"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=933"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}