1.3.1 - Lossy and lossless compression

What can be removed from a file?

Compression represents data using fewer bits, but different methods preserve different things.

Lossless methods exploit redundancy, such as a repeated symbol or repeated word, rather than deleting meaningful content. The compressed bytes need not resemble the original bytes. Program source, account records and an examination answer need exact reconstruction. Losing a character could change a command, amount or meaning.

With a lossy method, saving the decompressed result cannot recover the discarded information. For example, an image method may reduce fine colour differences which are difficult to notice; an audio method may remove detail which is less perceptible to a listener. This can give a much smaller file for photographs, music and streaming video, at a chosen acceptable quality. Increasing compression can introduce visible blocking or audible distortion. It is unsuitable when exact values matter, such as an original medical measurement.

Suppose a sender has 8 megabits of image data and a connection carries 2 megabits per second. Ignoring protocol overhead, sending it takes 4 seconds. A 2-megabit representation takes 1 second. Compression/decompression also take processing time, so the total saving depends on both the size reduction and the processor. A compressed file is not necessarily secret, and a file that already has little exploitable redundancy may barely shrink or may grow because the format adds metadata.

Encoding and decoding consecutive runs

Run-length encoding (RLE) replaces each consecutive run of equal symbols with the symbol and its count.

Define the representation before using it. Here each pair is (symbol, count), and pairs are read from left to right. The sequence AAAAABBBAA becomes (A,5), (B,3), (A,2). The last two As form a new run because the Bs separate them from the first five. Counting all seven As together would lose their positions. To decompress, write each symbol as many times as its associated count; the counts sum to the original length, 10.

A monochrome image row WWWWBBBBWW can similarly be represented as (W,4), (B,4), (W,2). A row convention which stores only lengths must also give its starting colour and an explicit alternating-colour rule. Counts alone cannot tell the decoder whether the first run is white or black. Do not assume different RLE conventions use the same order or metadata.

For a size calculation, assume the original has one byte per symbol and the compressed format uses one byte for a symbol plus one byte for its count, with no header. Ten original bytes above become six compressed bytes: three pairs times two bytes. This particular one-byte count can represent at most 255 repeats if zero is unused, so a longer run would have to be split. A practical format must specify this boundary and how empty input is represented.

The alternating sequence ABABAB has six runs of length one. Under the same format it grows from six bytes to twelve. RLE is useful for long repeated runs, such as large areas of a simple image, but is a poor choice for many rapidly changing symbols. It does not merge similar but unequal colours.

Replacing repeated sequences with dictionary codes

Dictionary coding replaces repeated sequences with shorter codes whose meanings are recorded in a dictionary.

The repeated sequence does not have to be a consecutive run. To see the mechanism without a complicated file format, suppose a text is tokenised into words using exactly one space between words, with no punctuation. Assign these one-byte codes:

The text red blue red green blue red becomes the code stream 1, 2, 1, 3, 2, 1. The decoder looks up each code in order, then inserts the agreed spaces. It recovers red blue red green blue red exactly. Without the dictionary, 1 does not tell the receiver which word to use. Lossless reconstruction also requires the agreed treatment of spaces, punctuation and case; a dictionary that ignores those details would not preserve arbitrary text exactly. Real methods may use repeated character sequences instead of whole words and may build the dictionary as processing proceeds.

Account for dictionary storage when deciding whether this saves space. In this explicitly simplified format, an entry uses one byte for its code, one for its word length and one per character. The three entries therefore use 5 + 6 + 7 = 18 bytes. The six codes use 6 bytes, giving 24 bytes total. The original six words and five spaces use 27 bytes. The saving is only 3 bytes, even though the code stream alone looks much smaller. The receiver already knows the one-space rule; no additional header is counted here.

If the text instead contains only red blue green, its 14 original bytes become 18 dictionary bytes plus 3 codes, or 21 bytes. Repeated reuse pays for the dictionary overhead. RLE exploits adjacent equal symbols; dictionary coding can exploit a phrase reappearing far away. Both can be lossless when decoding rules preserve all information.

Choosing a method from the data

A compression choice needs both a reconstruction requirement and evidence about the data's redundancy.

For a website photograph intended for a small preview, a lossy method may be justified: some detail can be sacrificed to reduce download time while the image remains recognisable. Keep the original separately if later editing needs it. Repeated lossy editing can compound information loss. For a text log, exact characters may be needed to diagnose a fault, so choose lossless compression. Within lossless methods, a log with recurring phrases may favour dictionary coding; a small monochrome icon with long uniform runs may favour RLE. Those are data-dependent reasons, not guarantees that every photograph or log will compress well.

You can express the outcome using explicit units. If an original file is 1,000 bytes and the complete compressed file is 700 bytes, the saving is 300 bytes, or 30% of the original. A ratio defined as original size divided by compressed size is about 1.43:1. Other contexts define ratios differently, so state the convention. Include the dictionary, headers and other stored information in the compressed size. Compare the quality requirement, actual complete size and time cost instead of assuming one method is always best.