So, I realised today I take file compression for granted. The ability to bundle a few files together into one, and have it come out smaller than any of them, is something I just accept as a fact, but how does it actually work?

I have a limited knowledge of it that includes something to do with replacing all the duplicate entries with pointers, to shrink that way, but beyond that I'm fairly clueless!

As I'm always open to new knowledge, as I imagine most of us here are, I thought I'd ask. So, SuperUser, how does compression actually work?

  • 1
    The Wikipedia article is a good start, but it would be nice to have more specific explanations. Good question (though I was sure we had such question already, but seems that not). – Gnoupi Apr 18 '10 at 14:34
  • 2
    @Gnoupi: Indeed, first thing I did was search, as I was sure there was one here. Apparently not, so I tried to rectify that :P – Phoshi Apr 18 '10 at 14:47
  • 2
    we've got a "what-is" tag for when you post pictures and go "wot izzit??"; i've been noticing a need for a "how-does-it-work" tag, but that's too long and "how-work" sounds dumb. "explain" might do it tho. – quack quixote Apr 18 '10 at 15:01
  • @quack quixote: Ah, thanks. I was looking in the autocomplete for a "plz-send-the-explanation" type tag, but couldn't find one. – Phoshi Apr 18 '10 at 15:04
  • 2
    i've come close to just creating a "how" tag a couple of times... but "explain" is probably better. "tutorial" and "howto" and "beginner" are all semi-applicable but don't quite fit. – quack quixote Apr 18 '10 at 15:23

Lossless Compression

Lossless compression is where no data is lost. Everything that is entered can be retrieved perfectly. This works well for text or binary files where the smallest error will be noticed.

File compression works by taking the file and scanning for patterns, and translating those patterns into something else which takes up less space.

For example "AAAAAAAA" could be turned into "8A".

Granted that's not how it works exactly because then you have the problem what if "8A" was in the plaintext. You would uncompress the file and it would be wrong. A good place to start is either Wikipedia or the LZW Data Compression Algorithm.

There is some simply psuedo-code for this copied below:

STRING = get input character
WHILE there are still input characters DO
    CHARACTER = get input character
    IF STRING+CHARACTER is in the string table then
        STRING = STRING+character
        output the code for STRING
        add STRING+CHARACTER to the string table
    END of IF
output the code for STRING

All compression uses a lookup dictionary which is used to compress and decompress the file. The bigger the dictionary, the more you can compress it, although you do run into the Law of Diminishing Returns.

It's also worth noting that compression doesn't always yield a smaller file. There are situations (with small files, or when compressing random data) that you will not get a smaller file after compression. There have been some fun challenges pertaining to the ability to compress random data.

"Lossy" Compression

The above mostly pertains to lossless compression. Other types of compression used in video / audio applications such as MP3, JPG, and h.264 are examples lossy compression.

Lossy compression works by discarding data that is least likely to be noticed. In audio this is sounds about 30,000 Hrz and below 100 Hrz, along with other various things. In picture (static) it removes various things and merges pixles together, along with discarding data.

Lossy compression is a form of transform coding. It averages out data to reduce the overall size. For example a block of 10 pixels in an image, all of slightly different colors may be merged together to one color and thus compressed.

In video compression often instructions will be placed to only redraw pixels that have changed since the last frame, or keyframe.

  • Note that this is explanation for lossless compression only, the kind for which you can recover the exact initial data (most likely used by archiving programs). There are other kinds of compression in which you lose quality for smaller size, used for example in JPG, MP3, etc. – Gnoupi Apr 18 '10 at 15:11
  • Josh's first example is a form of a real compression method called Run-Length Encoding, and "8A" would be compressed to "181A". Obviously his last paragraph applies here; RLE works best on data with many duplicates. – Dour High Arch Apr 18 '10 at 15:24
  • 3
    I added the lossless / lossy titles and rounded it out a bit more. It's good to note that the best way to further understand this is to simply read the wikipedia article. – Josh K Apr 18 '10 at 15:35

Compression works by finding patterns in the data, then replacing these patterns with a special smaller patterns. Decompression is the inverse: find the special patterns, and replace them with the larger patterns they represent. Knowing what patterns are probable is important; for example, patterns found in text may be quite different than those found in images. Some compression techniques are lossy; they do not guarantee the expansion will recover the input exactly. This is usually fine for analog data, such as music and images, if the loss is small enough. But data such as text must be compressed with lossless techniques.

It is important to realize that it is impossible to compress, without loss, random data by even a single bit. Consider a file with N bits of binary data. There are 2^N possible files. If you compress any of these files by a single bit, so the compressed file is N-1 bits in size, there are only 2^(N-1) possible compressed representations. In other words, each possible compressed file must represent more than one possible uncompressed file. Without a unique compressed representation, the decompression algorithm cannot guarantee lossless decompression.

  • 3
    a file may be uncompressed (adjective) but cannot be uncompressed (verb). instead it is decompressed. – quack quixote Apr 18 '10 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.