Lossless and Lossy Compression

Distinguish exact reconstruction from controlled approximation, examine how coding algorithms exploit structure, and compare rate only after stating an appropriate distortion measure.

Compression uses regularity or permitted approximation to represent data with fewer bits. A lossless system must reconstruct the original exactly. A lossy system may reconstruct a different value, so its bit rate must be considered together with a stated measure of distortion. Neither kind of compression can be judged from file size alone.

Measure the Encoded Size

Let $B_{\text{original}}$ and $B_{\text{compressed}}$ be the numbers of bits in the original and compressed representations. We will use the compression ratio

R=\frac{B_{\text{original}}}{B_{\text{compressed}}}.

“The compression ratio is the original number of bits divided by the compressed number of bits.” A value above one means that the compressed representation is smaller under this convention.

If a $1{,}200$ -byte file becomes $400$ bytes, then $R=1200/400=3$ . The compressed file is one third of the original size. Its space saving is

1-\frac{B_{\text{compressed}}}{B_{\text{original}}} =1-\frac{400}{1200} =\frac23\approx66.7\%.

Some sources reverse the ratio or report only the percentage reduction. A numerical claim should therefore state its convention rather than saying “three-to-one compression” without defining the direction.

Exercise: Calculate compression ratio and saving

A representation shrinks from $900$ bytes to $300$ bytes. Using $R=B_{\text{original}}/B_{\text{compressed}}$ , what is its compression ratio?

Check the ratio

Compute it first, then check your number.

HintDivide original size by compressed size

Calculate $900/300$ . The corresponding space saving is a different number.

SolutionThe ratio is three

The compression ratio is $R=900/300=3$ . The compressed representation uses one third of the original bytes, which corresponds to a space saving of $1-1/3=2/3\approx66.7\%$ .

Run-Length Encoding Uses Repetition

Run-length encoding replaces each consecutive run with its symbol and run length. Consider the binary message

000000001111

Its runs are eight zeros followed by four ones. Suppose a toy format stores each run as one symbol bit followed by a four-bit count. The uncompressed message uses $12$ bits. The two encoded runs use

2(1+4)=10\text{ bits},

so the compression ratio is $12/10=1.2$ .

The same format performs badly on 010101010101. It contains twelve runs of length one, so the encoded representation uses $12(1+4)=60$ bits. Its ratio is $12/60=0.2$ : the “compressed” result is five times as large as the original. An actual file format needs a rule for storing raw data when an encoding would expand it.

Encode and decode consecutive runs

Change the binary message. The example verifies exact recovery and compares raw bits with a toy one-bit-symbol, four-bit-count format.

Ready to run.

Exercise: Calculate run-length encoded size

A binary message contains three runs. A toy run-length format uses one symbol bit and four count bits for each run. How many encoded bits are required?

Check the encoded size

Compute it first, then check your number.

HintEach run has the same record size

Each run needs $1+4=5$ bits.

SolutionThree run records use fifteen bits

Each run uses $5$ bits, so three runs use $3\times5=15$ bits. Whether this is smaller than the original depends on the original message length.

Lossless Compression Must Reverse Exactly

For a lossless encoder $C$ and decoder $D$ , every valid input $x$ must satisfy

D(C(x))=x.

Program source, database records, cryptographic keys, and numerical model parameters normally require exact recovery. A single altered bit may change their meaning.

Different lossless methods exploit different structure:

run-length encoding exploits consecutive repetition;
dictionary methods replace repeated strings with references to earlier or stored phrases;
Huffman coding gives short prefix-free codewords to frequent symbols;
arithmetic coding represents a sequence through nested probability intervals and can approach ideal average lengths over long messages.

General compressors often combine several ideas. For example, one stage may predict or locate repeated phrases, while a later entropy-coding stage assigns short representations to frequent outputs from the first stage.

Exercise: Recognize a lossless requirement

Which item normally requires lossless rather than lossy compression?

Choose one

A Python source file

A preview photograph

A low-bandwidth voice recording

Select one choice, then check.

HintAsk whether a small change is acceptable

A changed punctuation mark can change the meaning of executable code.

SolutionProgram text needs exact recovery

A Python source file normally requires lossless compression because the decoder must recover every character exactly. A photograph or voice signal may permit controlled perceptual differences when the application allows it.

Huffman Coding Uses Unequal Probabilities

Suppose a memoryless source has probabilities:

Symbol	Probability
$A$	$0.4$
$B$	$0.3$
$C$	$0.2$
$D$	$0.1$

Huffman coding repeatedly joins the two least probable remaining groups:

join $D$ and $C$ to form a group of probability $0.3$ ;
join that group with $B$ , also of probability $0.3$ , to form $0.6$ ;
join the $0.6$ group with $A$ to form the root of probability $1$ .

One resulting prefix-free code is:

Symbol	Codeword	Length
$A$	`0`	$1$
$B$	`10`	$2$
$C$	`110`	$3$
$D$	`111`	$3$

Its expected length is

L=0.4(1)+0.3(2)+0.2(3)+0.1(3)=1.9

bits per source symbol. A fixed-length binary code for four symbols uses two bits per symbol. Huffman coding saves $0.1$ bit per symbol on average under this distribution. Ties in the construction may produce different codewords, but the expected optimal length is unchanged.

Huffman codeword lengths are whole numbers. Arithmetic coding can represent a long sequence with an average closer to fractional information values. The next lessons will make that comparison precise through self-information and entropy.

Not Every Input Can Become Shorter

There are $2^n$ binary strings of length $n$ . The total number of binary strings shorter than $n$ is

1+2+4+\cdots+2^{n-1}=2^n-1.

There are not enough shorter strings to assign a different one to every length- $n$ input. For $n=3$ , eight possible input strings compete for only seven shorter strings, including the empty string. A lossless compressor may shorten inputs with the structure it expects, but some other inputs must remain the same length or become longer.

This counting argument does not make compression useless. Real datasets are not uniformly distributed over all possible bit strings. Compression succeeds by assigning short descriptions to the inputs that occur often and allowing unusual inputs to cost more.

Lossy Compression Allows Controlled Error

A lossy decoder returns an approximation $\hat{x}$ rather than requiring $\hat{x}=x$ . A distortion measure $d(x,\hat{x})$ assigns a numerical cost to the difference. For a vector of $n$ scalar measurements, mean squared error is

D=\frac1n\sum_{i=1}^{n}(x_i-\hat{x}_i)^2.

“D is one over n times the sum of squared differences between each original value x sub i and its reconstruction x hat sub i.” The average depends on the chosen numerical representation of the signal.

Consider the measurements

x=(0.2,0.9,1.4,1.8).

Rounding each value to the nearest integer produces

\hat{x}=(0,1,1,2).

The squared errors are $0.04$ , $0.01$ , $0.16$ , and $0.04$ , so

D=\frac{0.04+0.01+0.16+0.04}{4}=0.0625.

Only three reconstruction levels occur: $0$ , $1$ , and $2$ . If the decoder already knows this codebook, two-bit indices can identify the levels. This does not mean that an arbitrary real number has been compressed losslessly into two bits; many original values are deliberately mapped to the same reconstruction.

Quantize measurements and calculate distortion

Change the measurements or quantization step. A larger step usually reduces the number of reconstruction levels while increasing error.

Ready to run.

Exercise: Calculate average quantization distortion

The values $(1.2,2.7)$ are reconstructed as $(1,3)$ . Using mean squared error, what is the average distortion?

Check the mean squared error

Compute it first, then check your number.

HintSquare both errors before averaging

The errors are $0.2$ and $-0.3$ ; their squares are $0.04$ and $0.09$ .

SolutionThe mean squared distortion is 0.065

The mean squared error is $D=[(1.2-1)^2+(2.7-3)^2]/2=(0.04+0.09)/2=0.065$ .

Distortion Must Match the Purpose

Mean squared error is easy to calculate, but it is not automatically the right measure. A small pixel shift can create a large pixel-wise error even when two images look almost identical. A subtle change in speech may matter greatly for recognizing a word even when its average waveform error is small. In scientific data, a visually minor change might remove a rare but important event.

A lossy system therefore needs a distortion criterion that reflects what must be preserved. Possible criteria include absolute error, squared error, perceptual measures, classification error, or a collection of domain-specific constraints. Saying that a reconstruction “looks good” does not state a reproducible criterion.

Exercise: State the missing comparison criterion

A report says that encoder A creates smaller image files than encoder B. Is that fact alone enough to conclude that A is better?

Choose one

Yes

Select one choice, then check.

HintFile size measures only rate

Ask what each reconstruction changed and whether those changes matter for the intended use.

SolutionRate alone is insufficient

No. Encoder A has a lower rate, but the comparison also needs a relevant distortion or quality criterion. A smaller representation is not better if it removes information required by the application.

Rate and Distortion Form a Trade-off

The rate is the average number of encoded bits per source symbol, sample, pixel, or other declared unit. Requiring zero distortion returns us to lossless coding. Allowing greater distortion can reduce the required rate because more original values may share one reconstruction.

Shannon's rate–distortion theory asks for the lowest achievable rate subject to a bound on expected distortion. Its formal expression uses mutual information, which appears later in the chapter. The practical comparison is already clear: compare rate at a fixed distortion, or compare distortion at a fixed rate.

Encoder	Rate (bits per pixel)	Mean distortion
A	$1.2$	$0.020$
B	$1.8$	$0.020$
C	$1.2$	$0.035$

At equal distortion, A uses fewer bits than B. At equal rate, A has lower distortion than C. The table does not establish that mean squared error is the right perceptual measure; it only shows how a rate–distortion comparison is organized after a measure has been chosen.

Exercise: Compare encoders at equal distortion

At the same mean distortion, encoder A uses $1.2$ bits per pixel and encoder B uses $1.8$ bits per pixel. How many fewer bits per pixel does A use?

Check the rate difference

Compute it first, then check your number.

HintSubtract the two rates

Compare $1.8$ bits per pixel with $1.2$ bits per pixel.

SolutionEncoder A saves 0.6 bit per pixel

At the same stated distortion, the rate difference is $1.8-1.2=0.6$ bit per pixel. This makes A more rate-efficient under the selected distortion measure.

Compression Depends on Structure and Purpose

Lossless compression exploits regularity while preserving every source symbol. Run-length encoding helps when long runs are common, Huffman coding uses unequal symbol probabilities, and other methods use repeated phrases or predictive context. None can shorten every possible input because exact decoding requires distinct representations.

Lossy compression also uses regularity, but it gains additional savings by mapping several original values to one reconstruction. Its result is meaningful only when rate is paired with a distortion measure suited to the task. The next lesson returns to one observed outcome and asks how its probability determines an ideal code length. That quantity, self-information, will connect coding to surprise.