Compression

Uncompressed images, sound and video are huge: three minutes of CD-quality audio is about 32 MB, and a single uncompressed 4K video frame is about 25 MB. Compression reduces file sizes so that data takes less storage and transfers faster. This note covers why compression is needed, the difference between lossy and lossless compression, how each type of file (text, bitmap, vector, sound) can be compressed, and run-length encoding (RLE), which Paper 1 asks you to apply by hand.

Why compress?

Compression reduces the number of bits needed to represent the same data (or acceptably similar data). The benefits all follow from smaller files:

• less storage space is needed, on devices and on servers;
• files transfer faster over networks and use less bandwidth, which matters for downloads, email attachments and web pages;
• streaming audio and video becomes possible at the bit rates real connections provide (see bit streaming);
• costs fall, for example for cloud storage or mobile data.

The costs are processing time (to compress and decompress) and, for lossy methods, some loss of quality.

Lossless and lossy compression

Lossless methods work by finding redundancy: patterns and repetition that can be described more briefly. Lossy methods go further and throw away detail judged to be unimportant, so they achieve much greater reductions.

Justifying a method

The choice always comes down to one question: does the file have to be exactly the same after decompression?

• A text document, a program, a spreadsheet of accounts: yes. Losing a single character could change the meaning or stop the program working, so lossless.
• A photograph for a website or a song to stream: no. Small losses are not noticed, and a much smaller file loads or streams faster, so lossy.
• A photograph a designer will keep editing, or a medical X-ray: yes. Repeated lossy saves degrade the image, and lost detail could matter, so lossless.

Run-length encoding (RLE)

Run-length encoding is a lossless method. A run is a sequence of identical consecutive data items. RLE replaces each run with two values: the number of items in the run and the item itself.

AAAABBBCCD becomes 4A3B2C1D: four A, three B, two C, one D. Ten characters become eight.

RLE works well when data has long runs, such as images with large areas of a single colour (icons, diagrams, cartoons, scanned text documents). It works badly when consecutive items are usually different: ABCDEF becomes 1A1B1C1D1E1F, which is twice the size. Photographs rarely have long runs of identical pixels, so RLE is a poor choice for them.

In a bitmap, RLE is applied to pixel colour values, usually row by row, and each run is stored as a pair of bytes: one byte for the count and one for the colour. A single count byte can hold at most 255, so a longer run is split into two.

FUNCTION Encode(Data : STRING) RETURNS STRING
   DECLARE Result : STRING
   DECLARE Count : INTEGER
   DECLARE Index : INTEGER

   Result ← ""
   Count ← 1
   FOR Index ← 2 TO LENGTH(Data)
      IF MID(Data, Index, 1) = MID(Data, Index - 1, 1) THEN
         Count ← Count + 1
      ELSE
         Result ← Result & NUM_TO_STR(Count) & MID(Data, Index - 1, 1)
         Count ← 1
      ENDIF
   NEXT Index
   // the final run has not been output yet
   Result ← Result & NUM_TO_STR(Count) & RIGHT(Data, 1)
   RETURN Result
ENDFUNCTION

How each type of file is compressed

Text files

Text must be compressed losslessly, because every character matters.

• Dictionary-based compression: repeated words or sequences are stored once in a dictionary, and each occurrence in the text is replaced by a short index into the dictionary. Long documents with many repeated words compress very well.
• Variable-length codes (for example Huffman coding): frequently used characters such as e and the space get short binary codes; rare characters get longer codes. The average number of bits per character falls below 8.
• RLE only helps if the text contains long runs of the same character, such as rows of spaces or dashes.

Bitmap images

• Lossless: RLE for images with large areas of identical colour; PNG and GIF use lossless methods that also exploit repeated patterns. Used for diagrams, screenshots and images to be edited.
• Lossy: JPEG removes detail the eye is unlikely to notice. It stores colour information at lower resolution than brightness (the eye is less sensitive to colour detail) and discards fine high-frequency detail. Reducing the colour depth (fewer bits per pixel) or reducing the resolution (fewer pixels) also reduces size and is lossy, because the removed data cannot be recovered.

Vector graphics

A vector graphic is a drawing list of objects and properties, essentially structured text, so it is compressed losslessly: with general-purpose lossless methods (for example a ZIP-style compression of an SVG file), and by removing redundant data such as unnecessary decimal places in coordinates, hidden objects, or comments. Lossy compression would change shapes and positions, which defeats the point of a precise drawing.

Sound files

• Lossy (perceptual) compression, as in MP3 and AAC, removes sounds people cannot hear or will not notice: frequencies outside the range of human hearing, and quieter sounds that are masked by louder sounds at the same time (perceptual masking). It can reduce file size to about a tenth with little audible difference.
• Reducing the sampling rate or sampling resolution, or converting stereo to mono, also reduces size and is lossy.
• Lossless formats such as FLAC exploit patterns in the samples and give back the original exactly, for archiving and professional editing.

Practice