Compression is the art of removing redundant or duplicate information from a file or a set of bytes in such a way that the original content can be reconstituted (decompressed) at a later stage.

The compression algorithm we are perhaps most familiar with is zip compression – although it's more formally known as 'Deflate'. This is a good example of a 'lossless' compression algorithm: when you compress something with Deflate and then decompress it, you get exactly the same file back, using the same set of bytes.

For a data file (say a word-processing document or a spreadsheet), this is exactly what you want. You certainly don't want to lose information through the compression/decompression process.

There is, however, a class of files where it doesn't matter too much if you don't get exactly the same file after going through a compression/decompression cycle. The data in these files is represented in such a way that our human senses can't really tell the difference between the original file and the processed one.

We're talking about data that we perceive through our eyes and ears: text, video, photos, music and the spoken word. Each of these kinds of files has its own set of compression algorithms that are fine-tuned to how we see or how we hear. For example, a WAV file is an uncompressed audio file, but we use MP3s as the file of choice when we store songs in our music player.

Files in MP3 format take up much less space but sound more or less as good as WAV files do. For video, things are much the same, although in practice uncompressed video files aren't used much because of their large size. There are several varieties of video compression formats – among them the familiar MPEG-4 – and each involves a different algorithm.

One of the main reasons for this variety of formats is legal: it's often easier to implement your own compression format than battle through the patent issues involved in using someone else's. There is a plethora of different formats for still pictures, too: BMP, GIF, JPEG, TIFF, PNG and so on. Some of these formats are similarly bedevilled with thorny patent issues (although thankfully, most of these patents have now expired).

The format maze

BMP – or 'bitmap' – is a simple uncompressed format where, in essence, each pixel in a 24-bit image is represented by three bytes, usually encoded as RGB (red, green and blue values).

GIF (Graphics Interchange Format) is a fine example of a lossless compression algorithm for images. It compresses well, especially for non-photographic images. However, images can only contain 256 colours because the GIF format prepends a palette of colours for the byte values 0 to 255 and then uses these values when rendering. A GIF-encoding program must analyse the image being compressed and allocate a palette for the colours in the image.

This means that for images using more than 256 colour values, such as photos, the encoder must throw away some information. As a result, GIF is generally only used for relatively simple images that contain contiguous blocks of colour.