Compression

Compression makes files smaller. A compression algorithm is a sequence of steps that is followed to reduce the size of a file. Every digital file is just a long series of binary digits, and a compression algorithm reduces the number of bits, so the compressed file has fewer bits (often far fewer).

A compressed file can be saved and moved around in this form, but it has to be decompressed before it can be used in a meaningful way (for example viewed or listened to).

The decompressed file above is not labelled "original file". Whether it is exactly the same as the original depends on whether the compression was lossy or lossless.

Compression may change the data inside a file, but it does not change the basic properties of the file. For example, a compressed bitmap image still has the same resolution as before, and a 10-minute piece of music still lasts 10 minutes.

Compressing and decompressing usually happen automatically. Most users do not choose to compress a file: they just save it in a format that happens to be compressed. For example, a phone camera usually saves photos in JPEG format, which is compressed, so the phone applies the compression algorithm to every photo automatically. When you open the photo, the software uses the file format to decompress the data and show it as an image.

Some files are very large. Local storage is often cheap and plentiful, so sometimes file size does not matter. But large files are a problem when they must be stored on a device with limited capacity (such as a memory card) or sent over a cable or wireless link. A smaller file means more files fit in the same storage, and files are quicker to transfer, upload and download.

The need to compress images. Image files can be very large. A typical mid-range camera is rated at 24 megapixels, which means it uses about 24 000 000 pixels for each image. A photo typically uses 12 bits for each colour channel, red (R), green (G) and blue (B), so 36 bits per pixel.

Storage space is often limited: for example, the number of photos a camera can hold depends on the size of its memory card. Photos may also need to be uploaded to cloud storage, a web server or a social media account, which can take a long time. To cut the storage and transfer time, photos are usually stored in JPEG format, which is highly compressed: JPEG reduces a file to around 10% of its uncompressed size.

The need to compress sound files. Sound files can also be very large. The most popular sound format for everyday users is MP3, which is compressed. Most listeners do not notice any difference in quality after compression, and they benefit from the smaller files when streaming or downloading. Music professionals usually work with uncompressed data to keep the highest sound quality: WAV is an uncompressed sound format.

Lossy compression always loses data: some data is permanently removed from the file. When the file is decompressed, the removed data is recreated from the data that remains, but it is never an exact copy of the original. It is an approximation. For example, a lossy algorithm could compress the number 3.1415926, and decompressing it would give back only 3.14.

It may seem strange that the data is not exactly the same after compression. But for many types of file, an approximation of the original data is good enough. Lossy compression is often used for image and sound files, because some data can be lost without a noticeable effect on quality: the human eye and ear cannot usually detect the small changes the algorithm makes. It also makes files much smaller than lossless compression can.

The risks of lossy compression. Lossy compression is destructive: the original data is lost for ever. Compressing a file with a lossy method again and again can lose so much data that the file becomes unrecognisable.

Lossless compression loses no data. When the file is decompressed, its contents are identical to the original file before it was compressed. For example, a lossless algorithm could compress the text AABBBA into a shorter string of bits, and decompressing those bits gives back exactly AABBBA.

Files that are unsuitable for lossy compression. Some data must not go through lossy compression. A file of words or numbers must be exactly the same when it is decompressed: it cannot be approximated. Imagine trying to rebuild a word when you are given only every other letter. From the letters "fos", the word could be "floss", "frogs", "fools" or many other words. Data like this needs lossless compression.

Lossless compression is the right choice wherever data cannot be approximated, such as documents of text and numbers, where every character must be kept. For example, if you email an assignment to your teacher, it must be exactly the same as the original when it is opened to be marked.

Most users do not choose a compression method. Compression is applied automatically when a file is saved, and the data is recreated when the file is opened. You rely on the software to store the data in the most suitable form.

There are many compression techniques, and the best one depends on the kind of data. Each technique is either lossy or lossless.

Run-length encoding (RLE) is a lossless compression technique. It finds runs of the same value repeated one after another, and replaces each run with one copy of the value and a number that says how many times it is repeated.

This bitmap image is 28 pixels by 28 pixels. Each pixel is stored as a binary colour code. A black and white image would need just one bit per pixel (0 for black, 1 for white), but this image uses five colours, so more codes are needed. To give five colours their own codes, 3 bits are needed (2³ = 8), so the colour depth is 3 bits.

RLE is lossless: the exact original data can be recreated from the compressed data by reversing the process.

Text files must be compressed with a lossless method, because every character must be exactly the same when the file is decompressed.

Run-length encoding of text. Groups of the same character repeated one after another are replaced by one copy of the character and the number of times it is repeated.

Dictionary-based methods. Words and groups of characters that appear many times are stored once in a dictionary, and every time they appear in the text they are replaced by a short reference to their place in the dictionary.

Huffman encoding is a lossless compression technique most often used for text documents. It works especially well when characters appear many times in the file.

Without compression, every character in a text file uses the same number of bits. With 8 bits per character, each character takes 1 byte, so a text of 180 characters needs 180 bytes, or 180 × 8 = 1440 bits.

Huffman encoding reduces the number of bits by giving characters bit patterns of different lengths. Characters that appear most often get short bit patterns, and characters that appear less often get longer ones.

A digital photo is stored as a bitmap, with a colour code for each pixel. JPEG compression is a lossy technique that uses the fact that real-life images are not made of a grid of separate pixels, but of smooth changes in colour.

A photo has millions of pixels, and the difference in colour between one pixel and the next can be too small to see. JPEG takes advantage of this by storing fewer colour codes. The algorithm throws away colour information that the human eye cannot detect, and finds patterns in the colours that remain. Blocks of similar colours are stored as a single colour, worked out from a sample of the pixels in the block. This reduces the amount of data stored, so the file is smaller. On standard settings, one colour is stored for every block of nine pixels, which reduces the file size by around 90%.

JPEG compression is lossy, so some data is lost for ever. When the image is opened, the missing pixels are recreated from the colours that remain, using the colours on either side of each missing pixel. This can cause compression artefacts: visible faults that are most noticeable where there is a sharp change of colour.

Compression ratio. JPEG compression typically has a compression ratio of 10:1, with little noticeable loss of quality. So an image of 36 MB would be reduced to 3.6 MB. With JPEG, the amount of compression can be adjusted, so the user can choose between a smaller file and a better-quality image.

A vector graphic is stored as a drawing list: a list of drawing objects and their properties, usually saved as text (for example in SVG). So it can be compressed with lossless methods used for text, for example by replacing sequences that are repeated many times, such as the same property values, with short codes.

A vector file is already small, because it stores instructions for drawing each shape, not the colour of every pixel. It has little repeated data, so it does not usually compress as much as a bitmap image does.

Sampling already loses some data, because the sound between two samples is never captured. Compression can then make the file smaller still.

MP3 is a common lossy compression technique for sound files. It works on the fact that the human ear cannot hear some sounds, and hears some sounds much better than others. For example, a quiet sound can be hidden by a louder sound at the same time, so the quiet sound can be removed completely. Sounds outside the range of human hearing can be removed too. When the file is played, the MP3 player recreates the missing sound using what is known about how sounds change in the real world.

MP3 compresses about as much as JPEG: compressed files are typically 10% of the original size, so a 15 MB file becomes about 1.5 MB. The sound will not be exactly the same as the original, but most people will not notice, because sound quality also depends on the equipment and the room the music is played in.