4.5.6.9 - Lossless and lossy compression

Compression preserves or discards information

Compression changes a file's representation to reduce the amount of data needed to store or transmit it.

An uncompressed image may store millions of pixel values, and sampled sound stores many amplitude values each second. Smaller files use less storage and, at a fixed transfer rate, take less time to transmit. Text and other data can also be compressed: compression is not restricted to images and sound. Compressing a file is different from encrypting it; the aim here is a shorter representation, rather than secrecy.

A lossless method represents patterns more efficiently without discarding their information. The decoder reverses the representation using the agreed format. Repeated text, a program or a spreadsheet requires exact recovery: changing one character can change meaning, behaviour or a value. Lossless methods also suit images or recordings when preserving the original data matters. They cannot guarantee that every possible input becomes smaller; an input without useful patterns may stay the same size or grow because of extra format information.

A lossy method can reduce image or audio data by discarding detail judged less important for its intended use. For example, an audio encoder may discard sound detail that listeners are unlikely to notice in the presence of louder sounds. Decompression constructs usable output, but cannot retrieve the discarded information. A suitably chosen setting can make the difference hard to perceive; stronger compression may create visible image artefacts or audible distortion. A smaller file is therefore not automatically a suitable file.

Lossy compression can achieve a much greater reduction for suitable media, but exact text, executable code and numerical records cannot generally tolerate changed data. It is incorrect to say lossless means no compression, or that lossy merely reduces playback volume: the distinction is whether the original data is recoverable exactly.

Run-length encoding replaces repeated runs

Run-length encoding stores the length and value of each consecutive run rather than storing every repeated value separately.

In this worked format, each pair is count then symbol. The sequence AAAAAABBBBBBCC contains six As, six Bs and two Cs, so its pairs are (6,A), (6,B), (2,C). A decoder reads each pair and repeats its symbol the stated number of times, reconstructing all fourteen symbols in order. The two As in ABA are not one run: a different symbol separates them, so the pairs are (1,A), (1,B), (1,A).

For this format, each original ASCII symbol occupies one byte, and every count and symbol in a pair also occupies one byte. Counts range from 1 to 255; a longer run would need splitting into several pairs. Ignore headers in the following comparison.

The first input benefits from long runs. The second grows because each single symbol gains a count. A bitmap with large uniform-colour areas can contain long repeated pixel runs, while a photograph with rapidly changing pixel values may have many short runs. The order in which pixels are read matters: repeated colours separated elsewhere in the picture are not necessarily consecutive in the stored sequence.

RLE remains lossless in both rows because its pairs retain all values and their repetition counts. Compression ratio and losslessness are separate questions. Do not calculate size by counting the printed digits in a notation such as 6A: a displayed pair is a human-readable description of the stored count and value, and the task must state their actual storage sizes.

Dictionary compression replaces repeated patterns

A dictionary method stores recurring sequences once in a dictionary and represents their occurrences by shorter references.

Unlike RLE, a dictionary can exploit a pattern that reappears after other data. The phrase or byte sequence need not consist of one repeated character. In this deliberately simple format, the original data is divided into two-character chunks. A dictionary contains exactly two entries, each stored as two ASCII bytes, at implicit indices 0 and 1. Each reference token occupies one byte; the agreed format tells the decoder the dictionary length and entry size. Ignore any other header information.

The input ABABABCDCDABAB is fourteen one-byte characters. Its seven chunks are AB, AB, AB, CD, CD, AB, AB, giving tokens 0, 0, 0, 1, 1, 0, 0. Decoding looks up each token and concatenates its entry, restoring the exact original sequence.

The token stream occupies 7 bytes. The dictionary occupies 2 × 2 = 4 bytes, so the total is 11 bytes, not 7. The three-byte saving already includes this dictionary overhead. A one-chunk input AB would need 5 bytes under the same two-entry format: 4 dictionary bytes plus one token. It would grow from 2 bytes. A longer input with many repetitions can spread the dictionary cost over more occurrences.

Real dictionary formats differ. Some send an explicit dictionary; others let encoder and decoder build matching dictionaries using the same rules as data is processed. Both must know how references and any literal values are distinguished and how entries are recovered. The principle is replacing repeated patterns by references, not requiring this lesson's fixed two-entry format for every method. A missing or mismatched dictionary can make the tokens undecodable; the reference stream alone does not explain its own symbols.

Choosing a method for the intended use

A compression choice must balance the kind of repetition available, the need for exact recovery and the acceptable storage, processing and quality costs.

For a simple image with long same-colour runs, lossless RLE may be effective. For repeated words or byte patterns in text, a dictionary method may be more suitable even if adjacent characters rarely repeat. Both require compatible decompression software and format information; encoding and decoding take processing time. A poorly matched lossless method can increase file size, so compare the complete encoded representation, including dictionaries or headers, with the original.

For a music preview streamed over a slow connection, lossy compression may provide a useful reduction when a small fidelity loss is acceptable. For the master recording that will be edited later, retaining exact sample data may justify lossless storage. Repeatedly decoding and recompressing with a lossy encoder can discard further detail, so retaining a suitable original/master avoids making every later version depend on an already degraded copy. Merely copying an existing compressed file does not itself cause another lossy encoding step.