# 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:** 20\ **Page:** 1
**Author:** ![cykrider](https://avatars.discourse-cdn.com/v4/letter/c/f19dbf/32.png) [@cykrider](https://boards.straightdope.com/u/cykrider)\ **Post date:** [July 31, 2002, 1:49am UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/1 "2002-07-31T01:49:32Z")
How does a program like PK Zip compress a file to a smaller size? I don’t really see how this can be done other than cutting part of the code out of the original program. Just wondering. Thanks. ---
**Author:** ![Thylacine](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thylacine/32/1143_2.png) [@Thylacine](https://boards.straightdope.com/u/Thylacine)\ **Post date:** [July 31, 2002, 2:04am UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/2 "2002-07-31T02:04:42Z")
> **[How File Compression Works](https://computer.howstuffworks.com/file-compression.htm)** > > Compression programs can eliminate 50 to 95 percent of file size in seconds, but when you open up the file the data is still there! Learn how compression algorithms cut down on bytes without killing data. google is your friend ---
**Author:** ![Sam\_Stone](https://avatars.discourse-cdn.com/v4/letter/s/ecccb3/32.png) [@Sam\_Stone](https://boards.straightdope.com/u/Sam_Stone)\ **Post date:** [July 31, 2002, 2:31am UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/3 "2002-07-31T02:31:04Z")
All compression algorithms rely on the fact that meaningful information is not random. Given that data is redundant or repetitive, there are ways to compress it, either while losing some information, or retaining all of it. If you need to recover the exact data stream, there are a number of ways. A simple one is called “Run Length Encoding”. Consider this string of digits: 1100001010100011100000000010111100000000000001100 Now, I could represent that string like this: 1-2,4,1,1,1,1,1,3,3,9,1,1,4,13,2,2 The ‘1’ at the beginning means the first digit is 1. Every number after that tells me how many times to print that number before switching to the other. Each comma represents a transition from 1 to 0. Now consider this number: 10000000000000000000000000001 Now we can compress it to: 1-1,27,1 This type of technique works well when there are large blocks of unchanging data. For example, a GIF image. If a GIF was 255 pixels wide, and the the top 200 rows were all solid black, it could be represented like this: black(51000), or its digital equivalent. That’s a hell of a lot better than storing 51,000 individual numbers, all of which are the same. Another method is to spot patterns and ‘tokenize’ them. For instance, consider this paragraph: George had a father named George. George’s father’s father was also named George. When George and his father and grandfather get together, you have three Georges in the same room. His father thinks that’s crazy, but George understands. I’ll bet his grandfather does too. Here’s a simple compression of that: First, I’m going to do a pass through it looking for certain patterns that repeat. In this case, the obvious ones are the word ‘George’, and the word ‘father’. So I will build a table of tokens like this: father - 1 george - 2 Now I can re-write the sentence like this: 2 had a 1 named 2. 2’s 1’s 1 was also named 2. When 2 and his 1 and grand1 get together, you have three 2s in the same room. His 1 thinks that’s crazy, but 2 understands. I’ll bet his grand1 does too. That’s roughly the way algorithms like the Lempel-Zev compression in PKZIP work. The executable of a program or an image have TONS of repeating patterns. Replace each pattern with a smaller token, and you can compress the file. Then there is ‘lossy’ compression, which relies on the fact that much information is redundant and unnecessary. For instance, I’ll bet you can understand this sentence: If u strt walkng nrth, u wll reach the nrth ple in tme. You might have to work a little bit at deciphering it, but once you do, you can extract all the information that was in it. Images contain redundant information, and also information that cannot be perceived (very subtle changes in colors, for example). That can be exploited, and by stripping information that is imperceptibe you can compress an image, although it is no longer the same as the original. Some algorithms combine methods. For instance, consider a movie. Not only does each frame have a lot of repeating patterns, but because the background in a movie stays relatively unchanged from frame to frame, by just storing the parts that change in each frame you can compress the image dramatically. In the extreme case of those old Spider-man cartoons where the background doesn’t even move, you could just store each background once, then all you’d have to store frame-by frame was the one person’s arm or whatever’s moving. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [July 31, 2002, 3:36am UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/4 "2002-07-31T03:36:44Z")
[http://www.faqs.org/faqs/compression-faq/part1/](http://www.faqs.org/faqs/compression-faq/part1/) The first part of the comp.compression FAQ. Good reading, if you like this kinda stuff. FWIW, for any given algorithm, there is a strength of length n that it can’t compress, simply because there aren’t enough possible outputs. Simple counting argument–more later if it’s necessary. ---
**Author:** ![CnoteChris](https://avatars.discourse-cdn.com/v4/letter/c/278dde/32.png) [@CnoteChris](https://boards.straightdope.com/u/CnoteChris)\ **Post date:** [July 31, 2002, 4:08am UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/5 "2002-07-31T04:08:00Z")
Fascinating way to explain it **Sam**. Every time I hear ‘algorithms’ and whatnot, my eye begin to gloss over. But the George example and that other actually make sense to me. Thanks. ---
**Author:** ![Ms2001](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ms2001/32/18463_2.png) [@Ms2001](https://boards.straightdope.com/u/Ms2001)\ **Post date:** [July 31, 2002, 5:33am UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/6 "2002-07-31T05:33:52Z")
Going along with what **ultrafilter** said, no lossless algorithm (e.g. PKZip, RAR, GIF) can make all inputs of any given size smaller; if it makes some smaller, it must make some larger. Basic example: you can’t compress all two-bit patterns into one bit, because there are 4 possible two-bit patterns and only 2 possible one-bit patterns. No matter how tricky your decompression algorithm is, if you have one “compressed” bit, it can only have one of two possible values, so you can only produce one of two possible “decompressed” output patterns. The same argument can be extended to any number of bits. But there are lossy formats like JPEG and MP3, which can work all the time because they don’t promise to restore the exact same pattern after compressing and decompressing. Of course, a lossy algorithm is only useful when you don’t need the exact same pattern - if you compressed a program and it was different when you decompressed it later, that would be catastrophic. MP3 basically works by removing details that your ear and brain are physically incapable of hearing… e.g., when you hear frequency X, it masks out frequencies Y and Z, so you don’t need to store those parts of the signal. As you lower the bit rate to get better compression, the encoder is more willing to throw out parts of the signal, so it throws out something that you otherwise would have heard (this is why low-bitrate MP3s sound bad). JPEG works by breaking the image into small blocks, then applying an algorithm called the discrete cosine transform (DCT). Just like you can make any number by combining different powers of 2 in a binary number system (35 = 32 + 2 + 1), you can make any possible block of the image by combining a fixed set of “building blocks” in different amounts; each building block is generated by a specific cosine wave, so it looks like a smooth gradient. Without getting into a full explanation, the JPEG encoder basically eliminates fine variations in the amounts it uses to combine the building blocks. Instead of “3 parts of block C + 18 parts of block F”, you might end up with “4 parts of block C + 16 parts of block F”. Since it’s still a smooth gradient and your eye isn’t very sensitive to small changes in color, you don’t notice the loss of information when you look at a JPEG image… unless you try compressing an image with sharp changes in color (like a cartoon), because then you’ll see smooth gradients where there were none before. ---
**Author:** ![Urban\_Ranger](https://avatars.discourse-cdn.com/v4/letter/u/e9c0ed/32.png) [@Urban\_Ranger](https://boards.straightdope.com/u/Urban_Ranger)\ **Post date:** [July 31, 2002, 5:36am UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/7 "2002-07-31T05:36:55Z")
> [@](#): > > \*Originally posted by Sam Stone \* > All compression algorithms rely on the fact that meaningful information is not random. Not all. Some algorithms such as Huffman code relies on the fact that some letters of an alphabet appear more frequently than others. Adaptive Huffman code builds a binary tree dynamically. I am sure there are other ways. > [@](#): > > \*Originally posted by Sam Stone \* > If you need to recover the exact data stream, there are a number of ways. A simple one is called “Run Length Encoding”. Consider this string of digits: > > 1100001010100011100000000010111100000000000001100 > > Now, I could represent that string like this: > 1-2,4,1,1,1,1,1,3,3,9,1,1,4,13,2,2 > > The ‘1’ at the beginning means the first digit is 1. Every number after that tells me how many times to print that number before switching to the other. Each comma represents a transition from 1 to 0. Eh, your compression algorithm end up with a longer “compressed file” then the original. If I didn’t count it wrong, the original is 32-bit long, while the compressed file is at least 33 bytes long, more than 8 times the size. > [@](#): > > \*Originally posted by Sam Stone \* > Then there is ‘lossy’ compression, which relies on the fact that much information is redundant and unnecessary. That’s only under a certain scale, sampling rate, etc. When you take a JPEG image and increase the size, it’s going to look bad. ---
**Author:** ![Sam\_Stone](https://avatars.discourse-cdn.com/v4/letter/s/ecccb3/32.png) [@Sam\_Stone](https://boards.straightdope.com/u/Sam_Stone)\ **Post date:** [July 31, 2002, 5:41am UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/8 "2002-07-31T05:41:09Z")
Thanks, Dad. I was trying to explain a concept, not design an efficient algorithm. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [July 31, 2002, 5:53am UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/9 "2002-07-31T05:53:24Z")
> [@](#): > > \*Originally posted by Urban Ranger \* > **Some algorithms such as Huffman code relies on the fact that some letters of an alphabet appear more frequently than others.** If the letters appear with different frequencies, then it’s not random. ---
**Author:** ![Crusoe](https://avatars.discourse-cdn.com/v4/letter/c/49beb7/32.png) [@Crusoe](https://boards.straightdope.com/u/Crusoe)\ **Post date:** [July 31, 2002, 7:19am UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/10 "2002-07-31T07:19:48Z")
Thanks for an excellent explanation, **Sam**. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [July 31, 2002, 2:21pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/11 "2002-07-31T14:21:17Z")
> [@](#): > > \*Originally posted by Mr2001 \* > \*\*Going along with what **ultrafilter** said, no lossless algorithm (e.g. PKZip, RAR, GIF) can make all inputs of any given size smaller; if it makes some smaller, it must make some larger. > > Basic example: you can’t compress all two-bit patterns into one bit, because there are 4 possible two-bit patterns and only 2 possible one-bit patterns. No matter how tricky your decompression algorithm is, if you have one “compressed” bit, it can only have one of two possible values, so you can only produce one of two possible “decompressed” output patterns. The same argument can be extended to any number of bits.\*\* Note that one of those two-bit strings could also be compressed to the empty string. Still, that’s not enough target strings. ---
**Author:** ![John\_Kentzel-Griffin](https://avatars.discourse-cdn.com/v4/letter/j/ccd318/32.png) [@John\_Kentzel-Griffin](https://boards.straightdope.com/u/John_Kentzel-Griffin)\ **Post date:** [July 31, 2002, 2:28pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/12 "2002-07-31T14:28:05Z")
> [@](#): > > \*Originally posted by \*\*\*Achernar \*\* > If the letters appear with different frequencies, then it’s not random. Random does not mean equally probable. And in the context of computer science, random just means that the system cannot anticipate the next item; as opposed to sequential. If the system does not anticipate the next item, it does not matter if every item is the same, it’s still random. ---
**Author:** ![Urban\_Ranger](https://avatars.discourse-cdn.com/v4/letter/u/e9c0ed/32.png) [@Urban\_Ranger](https://boards.straightdope.com/u/Urban_Ranger)\ **Post date:** [July 31, 2002, 2:29pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/13 "2002-07-31T14:29:21Z")
> [@](#): > > \*Originally posted by Achernar \* > If the letters appear with different frequencies, then it’s not random. This is a bit off-topic, but here goes. What you say is true for samples of infinite size, but not true for any practical files we might encounter. There is absolutely nothing in probably that stops the letter “z” from generated 25% more often than the letter “e,” for example. ---
**Author:** ![Urban\_Ranger](https://avatars.discourse-cdn.com/v4/letter/u/e9c0ed/32.png) [@Urban\_Ranger](https://boards.straightdope.com/u/Urban_Ranger)\ **Post date:** [July 31, 2002, 2:30pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/14 "2002-07-31T14:30:35Z")
d’oh. probably = probability ---
**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:** [July 31, 2002, 5:14pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/15 "2002-07-31T17:14:27Z")
Preface: I have published research papers on compression and information theory. Pardon me for being blunt. It bothers me when I see people who state something correctly are criticized by people who obviously are not at all expert on the matter. Huffman coding, when it does work, works because the distribution of character counts is _not random_. **Urban Ranger** et al.'s criticism is not warranted. In fact, in the context of compression and information theory, “random” is defined to mean “not compressible”. So any (lossless) method of any form that can compress a large set of data means that the data is not random _by definition_. This stuff all dates back to Church (who first proposed the idea) and Turing (who gave the first practical formalism). ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [July 31, 2002, 6:32pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/16 "2002-07-31T18:32:52Z")
I was using a definition of “random” that is mathematically equivalent to **ftg** ’s (though less circular-sounding). I assume **Sam Stone** was too. 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.) ---
**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:** [July 31, 2002, 6:45pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/17 "2002-07-31T18:45:54Z")
More on Huffman coding: If you’re not using a standard frequency distribution (such as the letter frequencies in English words), then you have to include your mapping as part of your compressed message. By the time that your message is large enough that this header size is insignificant, you’re to the size where a truly random message will have a frequency distribution close enough to random that Huffman coding will be useless. Some messages will be shrunk, but some will be expanded, and on average, you won’t help the size at all. The key to practical compression is that you hardly ever _want_ to compress a random message. If, for instance, you want to compress your five thousand page novel, a Huffman code will do the job, since your novel is in English, and English has uneven letter frequencies. You can probably do even better by going to the word or fragment level, instead of the letter level (the word “the” is more common than the letter “q”, for instance). If you want to compress an image, then you’ve probably got either smooth gradients, in which case JPEG will work well, or large uniform blocks, in which case GIF will work well. About the only time you’ll see files on your computer sufficiently “random” to be uncompressible will be the output of your compression programs: Running a zip file through WinZip again won’t really make much difference. ---
**Author:** ![AmbushBug](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ambushbug/32/4600_2.png) [@AmbushBug](https://boards.straightdope.com/u/AmbushBug)\ **Post date:** [July 31, 2002, 9:24pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/18 "2002-07-31T21:24:31Z")
> [@](#): > > _Originally posted by Achernar \* > \*\* I would like to point out that a completely random sequence of bits is, in general, uncompressable._\* One of my favorite corollaries to compression and randomness is the converse of your statement: if you have data that is compressed with an efficient algorithm, it has the outward appearance of being completely random. As long as you work to skip any ‘headers’ your compression program might add within your file I should think that .ZIP files would make an effective one-time pad for secret messages. As in: “Here’s a big data file of seemingly random numbers. To decrypt it, WINZIP disk 3 of Microsoft Excel for Windows, 1.03 from 1988 and XOR the bytes against the zip file.” AmbushBug _i have the feeling i’ve just exported munitions using the SDMB. **shudder** _ ---
**Author:** ![CurtC](https://avatars.discourse-cdn.com/v4/letter/c/ce73a5/32.png) [@CurtC](https://boards.straightdope.com/u/CurtC)\ **Post date:** [July 31, 2002, 10:10pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/19 "2002-07-31T22:10:53Z")
A few months ago, a company claimed to be able to compress “near-random,” practical data by a 100:1 factor, and that you could repeat the process to get even more compression. They made a big press splash around the first of this year, and their press release was picked up by several credulous news agencies, including Reuters (!). 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 [http://www.pcworld.com/news/article/0,aid,86986,00.asp](http://www.pcworld.com/news/article/0,aid,86986,00.asp) . They even went so far as to say that their work specifically refuted the work of Claude Shannon. I’d really like to know the rest of the story. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [July 31, 2002, 10:24pm UTC](https://boards.straightdope.com/t/how-does-file-compression-work/121621/20 "2002-07-31T22:24:41Z")
ZeoSync was discussed here in GQ. The consensus of those in the know was that it was a bunch of crap. [Next page](https://boards.straightdope.com/t/how-does-file-compression-work/121621.md?page=2)