Computer Science › Section B · Data storage › Topic B.9

Data compression

Raw images, sound and video take far more bits than storage and networks can comfortably carry. Compression shrinks them by exploiting patterns in the data, or by discarding detail that people will not notice.

Lossless and lossy

Data compression means representing information in fewer bits. Every method falls into one of two families. Lossless compression lets the original be rebuilt exactly, bit for bit; it is essential for text, program files and spreadsheets, where a single changed bit could be a disaster. Lossy compression rebuilds only an approximation, but usually shrinks data much further, so it suits photographs, music and video, where small errors go unnoticed. ZIP files and PNG images are lossless; JPEG photos and MP3 or AAC audio are lossy. The compression ratio compares the sizes: a 10 MB file squeezed to 2 MB has a ratio of 5 to 1.

Run-length encoding

The simplest lossless method replaces a run of identical items with one copy and a count. A row of pixels that reads WWWWWWWWBBBWWWWW, with W for white and B for black, becomes 8W3B5W: six symbols instead of sixteen. Run-length encoding works well when long runs are common, as on a scanned page of text, which is mostly white, or in simple graphics with large flat areas. On varied data it backfires. ABCD has no runs at all, so it becomes 1A1B1C1D and doubles in size.

Frequency-dependent codes

Codes such as ASCII give every character the same number of bits, yet in English text e and t are far more common than q and z. A frequency-dependent code gives short patterns to common items and longer ones to rare items, so a typical message needs fewer bits in total. The catch is decoding: with patterns of different lengths, the reader must know where each one ends. The fix is a prefix-free code, in which no pattern is the start of another, so a decoder reading left to right always knows when a pattern is complete. The standard way to build such a code was published by David Huffman in 1952.

Worked example: a Huffman code

A 16-symbol message contains A 8 times, B 4 times, C twice, and D and E once each. 1. List the counts. 2. Merge the two smallest, D and E, into a group of count 2. 3. Merge the two smallest again, C and the DE group, into a group of 4. 4. Merge B with that group to make 8. 5. Merge A with the rest to make 16. 6. Label each merge 0 for the first branch and 1 for the second, reading from the last merge back: A = 0, B = 10, C = 110, D = 1110, E = 1111. 7. Total size: \(8 \times 1 + 4 \times 2 + 2 \times 3 + 4 + 4 = 30\) bits, against 48 bits with a fixed 3 bits per symbol. 8. Decoding 0101100 gives 0, 10, 110, 0, which is ABCA.

Relative encoding

Some data changes only a little from one item to the next, such as a temperature logged every second or consecutive frames of a film. Relative encoding, also called differential encoding, stores the first item in full and then only the differences. Readings of 1000, 1002, 1001 and 1005 become 1000, +2, −1 and +4. The small differences fit in far fewer bits than full readings. If the differences are stored exactly, the method is lossless; if they are rounded to save even more space, it becomes lossy.

Dictionary encoding

Dictionary encoding replaces pieces of a message with references to entries in a dictionary that the encoder and decoder share. Suppose a dictionary holds \(2^{15} = 32{,}768\) common words. Any of them can be named by a 15-bit index, while spelling out a seven-letter word in ASCII stored one byte per letter takes 56 bits. In an adaptive dictionary scheme, the dictionary grows during encoding, so patterns found in this particular message become entries too. The best-known adaptive method is LZW, named after Abraham Lempel, Jacob Ziv and Terry Welch. Its neat trick is that the decoder rebuilds the growing dictionary itself, so the dictionary never has to be sent.

Worked example: LZW

Encode ABCABCABC, starting with the dictionary A = 1, B = 2, C = 3. The rule: read the longest string already in the dictionary, output its code, then add that string plus the next character as a new entry. 1. A is known but AB is not: output 1, add AB = 4. 2. B; BC is new: output 2, add BC = 5. 3. C; CA is new: output 3, add CA = 6. 4. AB is now known but ABC is not: output 4, add ABC = 7. 5. CA is known, CAB is not: output 6, add CAB = 8. 6. BC is known and the message ends: output 5. 7. Nine characters became six codes, 1 2 3 4 6 5, and the savings grow as entries get longer.

Compressing images

GIF limits an image to a palette of at most 256 colours, so each pixel needs only a one-byte index, and then applies LZW to the indices. For logos and cartoons with few colours this loses nothing, but a photograph forced into 256 colours loses detail. PNG is fully lossless and also suits graphics. JPEG, designed for photographs, is lossy and exploits the eye. Because we notice changes in brightness more than changes in colour, it commonly averages the colour information over 2 × 2 pixel squares. It then splits the image into 8 × 8 blocks, transforms each with the discrete cosine transform, discards fine detail the eye would miss, and packs the rest losslessly.

Compressing sound and video

Uncompressed CD-quality stereo audio needs 44,100 samples per second × 16 bits × 2 channels = 1,411,200 bits per second. An MP3 at 128 kilobits per second is about 11 times smaller. MP3 and AAC rely on how hearing works: a quiet sound close in pitch or time to a loud one is masked and goes unheard, so it can be discarded. Video standards, many from the Moving Picture Experts Group (MPEG), use relative encoding between frames. A full key frame is stored now and then, and the frames in between are stored mostly as changes from their neighbours, which suits scenes where little moves.

Common mistakes to avoid

No lossless method can shrink every possible file: if it did, applying it again and again would reduce any file to nothing. That is why zipping a JPEG barely changes its size; the redundancy is already gone. Run-length encoding can make varied data larger. A variable-length code that is not prefix-free cannot be decoded reliably: if A = 0 and B = 01, the pattern 01 could start either. Re-saving an edited JPEG many times can lose a little more quality at each save. And GIF is a poor choice for photographs because of its 256-colour limit.

Key takeaways

Lossless compression rebuilds data exactly; lossy compression rebuilds an approximation in exchange for smaller files. Run-length encoding replaces runs with counts. Huffman codes give common items short, prefix-free patterns. Relative encoding stores differences between neighbours. Dictionary encoding replaces pieces with references, and LZW grows its dictionary as it goes, with the decoder rebuilding it. GIF uses a 256-colour palette plus LZW, PNG is lossless, and JPEG discards detail the eye misses. MP3 removes masked sounds, and video stores key frames plus changes.

Flashcards

Flashcard

Lossless

The original can be rebuilt exactly

ZIP, PNG; essential for text and programs.

Test your understanding

Question 1 of 5

Which run-length encoding matches the row GGGGGRRRRRRRRGG?

Question 2 of 5

With the Huffman code A = 0, B = 10, C = 110, D = 1110, E = 1111, how is BAD encoded?

Question 3 of 5

Which of these uses lossy compression?

Question 4 of 5

LZW starts with the dictionary A = 1, B = 2 and encodes AABAABAAB. What is the output?

Question 5 of 5

Which feature of human vision does JPEG compression rely on?

← Previous topicNext topic →