Lossless compression

Lossless compression makes data smaller in a way that can be reversed exactly: decoding gives back every original bit. It is used for archiving, for editing intermediates, for general file compression, and as the final stage inside every lossy media codec.

Redundancy and entropy

Redundancy is the part of the data that is repetitive or predictable, and therefore carries no new information. Entropy measures how unpredictable the data is. Low entropy means high redundancy and good compressibility; random noise has high entropy and barely compresses at all. Lossless compression removes redundancy so that the encoded size approaches the entropy of the data.

That is also why lossless video and audio files stay large: real camera and microphone signals contain a lot of noise, which is unpredictable by nature.

Run-length encoding

Run-length encoding (RLE) stores a run of identical values as one value and a count, so AAAAABBBCC becomes 5A3B2C. It works well on long runs, such as flat-color graphics or digital silence, and does nothing for varied data.

Huffman coding

Huffman coding gives frequent symbols short codes and rare symbols long ones. It builds a binary tree from the symbol probabilities; each symbol’s code is the path from the root to its leaf, and no code is a prefix of another, so a decoder can read them back without separators.

Suppose you log the state of a traffic light: green 50% of the time, red 40%, yellow 9%, and off for maintenance 1%. Four states fit in two bits each (00, 01, 10, 11), an average of 2 bits per symbol. Huffman coding does better:

State	Probability	Code
Green	50%	0
Red	40%	11
Yellow	9%	100
Off	1%	101

The average code length is (0.5 × 1) + (0.4 × 2) + (0.09 × 3) + (0.01 × 3) = 1.6 bits per symbol. (NIST: Huffman coding)

Arithmetic coding

Huffman codes must be a whole number of bits per symbol. Arithmetic coding removes that limit by representing a whole sequence as one number inside an interval that narrows with each symbol, in proportion to the symbol’s probability. Real implementations work with finite-precision integers and emit bits as they go, but the idea is easiest to see with fractions. (NIST: arithmetic coding)

Give each state a slice of [0, 1) matching its probability: green [0, 0.5), red [0.5, 0.9), yellow [0.9, 0.99), off [0.99, 1). For each symbol, with width = high − low of the current interval:

new_low  = low + width × symbol_low
new_high = low + width × symbol_high

Encoding green, red, yellow, green:

Symbol	Interval before	New interval
Green	[0, 1)	[0, 0.5)
Red	[0, 0.5)	[0.25, 0.45)
Yellow	[0.25, 0.45)	[0.43, 0.448)
Green	[0.43, 0.448)	[0.43, 0.439)

Any number in the final interval identifies the sequence; 7/16 = 0.4375 (binary 0.0111) is a short one. To decode, the decoder repeatedly finds which slice the number falls in and rescales: 0.4375 is green, rescaled to 0.875 is red, then 0.9375 is yellow, then about 0.4167 is green. It also needs to know when to stop, from a stored length or an end-of-message symbol.

Over long sequences, arithmetic coding approaches the entropy of the source. For these probabilities that is −Σ p·log₂(p) ≈ 1.408 bits per symbol, compared with Huffman’s 1.6. Modern video codecs use adaptive arithmetic coders as their entropy-coding stage: CABAC in H.264 and HEVC, and a multi-symbol arithmetic coder in AV1.

Prediction and residual coding

Media samples are usually close to their neighbors, so a codec can predict each sample from previous ones and store only the difference (the residual). Residuals are small numbers clustered around zero, which entropy-code far better than the raw samples.

• FLAC predicts each audio sample with a linear predictor (LPC) from previous samples and Rice-codes the residual.
• PNG applies a per-row prediction filter (for example, “subtract the pixel to the left”) and then compresses the result with DEFLATE.
• FFV1 predicts each pixel from its neighbors and codes the residual with a context-modelled range coder (or Golomb–Rice coding).

General-purpose compressors such as ZIP and zstd add dictionary coding (LZ77 and relatives): repeated byte sequences are replaced with references to an earlier occurrence.

Lossless in practice

Media	Common lossless formats
Audio	FLAC, WavPack, ALAC
Video	FFV1 for archiving, UT Video for editing, x264/x265 lossless modes for small files
Images	PNG, lossless WebP, lossless JPEG XL

A lossless encode is only lossless if nothing changes before it. Converting 10-bit to 8-bit, 4:2:2 to 4:2:0, or RGB to YUV throws information away before the lossless encoder ever sees it. Keep the source’s pixel format and sample format, and compare decoded output against the source (for example with FFmpeg’s framemd5 muxer) when it matters.