Cambridge A-Level Computer Science (9618) · lesson 5 of 15 · 30 min
Run-Length Encoding (RLE) — In Depth
RLE replaces consecutive repeated values with a (count, value) pair. At A-Level you must be able to apply RLE to binary data and calculate compression ratios.
Apply RLE to binary image row: 00000011111100000000
Original: 20 bits
Runs: 6×0, 6×1, 8×0
Encoded: (6,0)(6,1)(8,0) = 3 pairs
If each pair uses 8 bits: 3 × 8 = 24 bits — actually larger!
RLE is only effective when runs are long enough to justify the overhead.
Huffman Coding — In Depth
Huffman coding assigns variable-length binary codes to symbols based on frequency — more frequent symbols get shorter codes. The result is always optimal (shortest possible average code length).
Building a Huffman tree:
- Count the frequency of each symbol.
- Create a leaf node for each symbol.
- Repeatedly merge the two nodes with the lowest frequency into a new parent node (frequency = sum of children).
- Assign 0 to left branches and 1 to right branches.
- Read each symbol’s code by tracing from root to leaf.
Huffman codes for: A(5), B(3), C(2), D(1)
Frequencies: A=5, B=3, C=2, D=1
Merge D(1)+C(2) → DC(3)
Merge DC(3)+B(3) → DCB(6)
Merge DCB(6)+A(5) → root(11)
Codes: A=1 (1 bit), B=01 (2 bits), C=001 (3 bits), D=000 (3 bits)
Average bits per symbol = (5×1 + 3×2 + 2×3 + 1×3) / 11 = 20/11 ≈ 1.82 bits
Fixed 2-bit encoding would use 2 bits per symbol — Huffman saves ~9%.
In Huffman coding, the most frequent symbol receives:
- The longest code
- The shortest code
- A fixed-length code
- No code
- Answer: 1
Huffman assigns shorter codes to more frequent symbols to minimise average code length.
RLE is most effective when:
- Data has many different values
- Data has long runs of the same value
- Data is already compressed
- Data is random
- Answer: 1
RLE replaces runs of identical values — it only saves space when runs are long.
Huffman coding is an example of which type of compression?
- Lossy
- Lossless
- Perceptual
- Transform
Answer: Lossless
Huffman coding is lossless — the original data can be perfectly reconstructed.
Previous lesson: Error detection: parity, checksums, and CRC
Back to Cambridge A-Level Computer Science (9618)
Next lesson: Transmission media and bandwidth