# How does file compression work? **URL:** \ **Category:** Factual Questions\ **Created:** [July 31, 2002, 1:49am UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621 "2002-07-31T01:49:32Z")\ **Posts on this page:** 19\ **Page:** 2
**Author:** ![Pete\_The\_Sequel](https://avatars.discourse-cdn.com/v4/letter/p/8edcca/32.png) [@Pete\_The\_Sequel](https://boards.straightdope.com/u/Pete_The_Sequel)\ **Post date:** [July 31, 2002, 10:25pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/21 "2002-07-31T22:25:07Z")
> [@](#): > > \*Originally posted by AmbushBug \* > _i have the feeling i’ve just exported munitions using the SDMB. **shudder** _ \*\* Nah, you’re safe. You’d only be breaking laws, if you exported pre-compiled code. -Pete ---
**Author:** ![fallom](https://avatars.discourse-cdn.com/v4/letter/f/a88e57/32.png) [@fallom](https://boards.straightdope.com/u/fallom)\ **Post date:** [July 31, 2002, 10:33pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/22 "2002-07-31T22:33:08Z")
My favorite compression trick is to make a ridiculously huge (around 500 megs or 1 gig) image that consists of nothing but white space. Then compress it to a 2 meg jpg. When you view it on a website, it decompresses, and makes your computer grind to a halt. ---
**Author:** ![iamthewalrus\_3](https://avatars.discourse-cdn.com/v4/letter/i/258eb7/32.png) [@iamthewalrus\_3](https://boards.straightdope.com/u/iamthewalrus_3)\ **Post date:** [August 1, 2002, 12:16am UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/23 "2002-08-01T00:16:06Z")
Wait. Does that really work? I don’t know how display of compressed images works, but the image buffer shouldn’t hold any more than whatever the screen size is, right? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 1, 2002, 12:32am UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/24 "2002-08-01T00:32:21Z")
> [@](#): > > \*Originally posted by iamthewalrus(:3= \* > \*\*Wait. Does that really work? I don’t know how display of compressed images works, but the image buffer shouldn’t hold any more than whatever the screen size is, right? \*\* No, the image buffer is completely happy to try to hold an entire image. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [August 1, 2002, 7:49pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/25 "2002-08-01T19:49:36Z")
> [@](#): > > \*Originally posted by Achernar \* > I would like to point out that a completely random sequence of bits is, in general, uncompressable. (Is that right? I’m not an expert at all.) You’ve taken the classic definition and written it backwards. If it compresses, then it is _defined_ to be non-random. (In this field of study.) This is such a simple statement I cannot see how it can appear to be circular. (Despite the use of “If”, this is a definition, so non-compressible means random. But you have to resort to Kolmogorov-type definitions to state it right.) Regarding the _output_ of a compressor and randomness. (Cf. **AmbushBug**.) It is only a limited form of pseudo-randomness and not nearly of good enough quality to compare to one time pads. Keep in mind that the everyday compression schemes most people are familiar with trade in compressibility for time. Who wants to wait a couple years to compress an image to 95% less space? Hence, a zipped file could be compressed further (and therefore is not random), but it could take a method that might use substantially more time. Keep in mind that NSA, etc. have “time” (in the sense of computer cycles). ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 1, 2002, 9:54pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/26 "2002-08-01T21:54:05Z")
I can’t find any good online resources on Kolmogorov complexity, but when I get home I’ll post what little info I have, just in case anyone’s curious. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 2, 2002, 12:29am UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/27 "2002-08-02T00:29:21Z")
Let x be a string. Let |x| denote the length of x (i.e., the number of characters in x). The Kolmogorov complexity of x, denoted K(x), is the length of the shortest program/input combination that produces x as output. How does this relate to compressibility? Well, a string x is said to be c-compressible if K(x) \< |x| - c for some constant c. If x is not 1-compressible, then x is incompressible. That’s what we’re calling random here. ---
**Author:** ![pulykamell](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pulykamell/32/3166_2.png) [@pulykamell](https://boards.straightdope.com/u/pulykamell)\ **Post date:** [August 2, 2002, 8:24am UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/28 "2002-08-02T08:24:38Z")
> [@](#): > > \*Originally posted by CurtC \* > \*\* > Knowing that it was either a fraud or a joke, I kept my eye on them, checking their web site occasionally for updates. Recently when I looked, they’re no longer there! The company name was ZeoSync, and their web site was [www.zeosync.com](http://www.zeosync.com). Unfortunately, their web page was completely Flash, so Google’s cache feature won’t let you view it. You can still search for ZeoSync and find lots of articles, for example \*\* You can get to a version of their original web page at [http://web.archive.org/web/20010719111638/http://www.zeosync.com/](http://web.archive.org/web/20010719111638/http://www.zeosync.com/) ---
**Author:** ![sailor](https://avatars.discourse-cdn.com/v4/letter/s/a587f6/32.png) [@sailor](https://boards.straightdope.com/u/sailor)\ **Post date:** [August 2, 2002, 10:30am UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/29 "2002-08-02T10:30:00Z")
> [@](#): > > You can get to a version of their original web page at > [http://web.archive.org/web/20010719...ww.zeosync.com/](http://web.archive.org/web/20010719...ww.zeosync.com/) I had another look at it and laughed at the crap almost as hard as the first time I saw it. I remember news reports giving it credibility which just goes to show you what reporters know. ---
**Author:** ![pulykamell](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pulykamell/32/3166_2.png) [@pulykamell](https://boards.straightdope.com/u/pulykamell)\ **Post date:** [August 2, 2002, 11:42am UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/30 "2002-08-02T11:42:17Z")
Yeah, in particular the main claim can’t exactly be found guilty of understatement. > [@](#): > > Relational Differentiation Encoding is theoretically capable of; > “Encode the entire sum content of human knowledge > on a singular computer disk.” Hey, they didn’t say how big the disk would have to be, now did they? ---
**Author:** ![ForgottenLore](https://avatars.discourse-cdn.com/v4/letter/f/5e9695/32.png) [@ForgottenLore](https://boards.straightdope.com/u/ForgottenLore)\ **Post date:** [August 2, 2002, 1:12pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/31 "2002-08-02T13:12:15Z")
When I was a computer science student in college one of our assignments was to write a text file compressor. The method I used was pretty straightforward. Normally every letter and punctuation mark is represented by a byte of memory. I simply did frequency analysis on the file, then assigned the commonest characters smaller bit strings. The most common letter would be represented by two or three bits, the least common ones by maybe as many as ten. Do this conversion to all the characters in the file and append the conversion dictionary to the end. Abracadabra, the file is smaller. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 2, 2002, 3:35pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/32 "2002-08-02T15:35:01Z")
> [@](#): > > \*Originally posted by ForgottenLore \* > \*\*When I was a computer science student in college one of our assignments was to write a text file compressor. The method I used was pretty straightforward. Normally every letter and punctuation mark is represented by a byte of memory. I simply did frequency analysis on the file, then assigned the commonest characters smaller bit strings. The most common letter would be represented by two or three bits, the least common ones by maybe as many as ten. Do this conversion to all the characters in the file and append the conversion dictionary to the end. Abracadabra, the file is smaller. \*\* What you’re talking about is a Huffman encoding, and I think I could come up with a text file that would get larger under Huffman encoding. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [August 2, 2002, 6:51pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/33 "2002-08-02T18:51:43Z")
> [@](#): > > What you’re talking about is a Huffman encoding, and I think I could come up with a text file that would get larger under Huffman encoding. You certainly could, but that text file would probably not be well-formed English. For instance, the string “abcdefghijklmnopqrstuvwxyz” would not be compressed by Huffman, but the Gettysburg Address would be. Also, an optimally-compressed file is generally _not_ indistinguishable from random noise, depending on what you mean by “optimal”. A zip file, for instance, includes some extra redundancy for the purpose of error correction. This only adds a logarithmic number of bits to the file (i.e., the number of added bits is of the order of the log of the number of original bits), so it doesn’t hurt your compression much, but it makes the message instantly distinguishable from noise (noise doesn’t usually come with a bunch of convenient checksums at the end). ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 2, 2002, 7:05pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/34 "2002-08-02T19:05:09Z")
> [@](#): > > \*Originally posted by Chronos \* > **You certainly could, but that text file would probably not be well-formed English.** Yeah. So? I realize that **forgottenlore** wasn’t claiming that I couldn’t do that, but I wanted to make sure everyone realized it was possible. ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [August 2, 2002, 8:59pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/35 "2002-08-02T20:59:52Z")
I basically got romped in GQ for some of the absurd statements I made in the last thread I remember on compression, so let me say that ignorance was fought, even if it was a bitter fight. But, I still have some questions. For a compression routine, can it be known ahead of time exactly how many combinations will not compress (given a definite string length or less)? ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [August 3, 2002, 5:26pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/36 "2002-08-03T17:26:39Z")
> [@](#): > > \*Originally posted by erislover \* > For a compression routine, can it be known ahead of time exactly how many combinations will not compress (given a definite string length or less)? _Exactly_? No. It would take some time to explain, complete with a detour into the Busy Beaver Function and the Amazing Omega Constant. _Roughly_ could be figured out as long as you like approximate guesses. For typical compressors, the easiest answer is “only a tiny fraction” where “tiny” is an ever decreasing amount as the string length increases. E.g., 2[sup]n/c[/sup] out of 2[sup]n[/sup] for some constant c\>1. That may look like a lot but it’s an insignificant percentage for large n. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 3, 2002, 5:32pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/37 "2002-08-03T17:32:20Z")
[symbol]w[/symbol] is the probability that a randomly chosen program will halt upon a randomly chosen input, correct? ---
**Author:** ![Seraphim](https://avatars.discourse-cdn.com/v4/letter/s/ad7895/32.png) [@Seraphim](https://boards.straightdope.com/u/Seraphim)\ **Post date:** [August 3, 2002, 8:30pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/38 "2002-08-03T20:30:16Z")
A related question I’ve wondered about: Is it possible to replace JPEG, PKZIP, GIF, etc.–all of them–with some new theoretical lossless technique that achieves maximum possible compression on all sets of data, or will it always be that certain techniques work better with different sets? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 3, 2002, 8:42pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/39 "2002-08-03T20:42:57Z")
> [@](#): > > \*Originally posted by Seraphim \* > \*\*A related question I’ve wondered about: Is it possible to replace JPEG, PKZIP, GIF, etc.–all of them–with some new theoretical lossless technique that achieves maximum possible compression on all sets of data, or will it always be that certain techniques work better with different sets? \*\* No compression technique can achieve the maximum possible compression for each file. See [73] in the second part of the compression faq I referenced earlier for an explanation as to why not. [Previous page](https://boards.straightdope.com/t/how-does-file-compression-work/121621.md?page=1)