Lossless compression and an evaluated end-to-end design

By UK GCSE Computer Science · independent study · myAudience

Original built-in imagegen teaching raster; author inspected original and three served sizes2026-10-04. Independent derivative review pending. · Generated project artwork; no copied exam or publisher illustration. Independent rights/publication review pending.

Lossless compression and an evaluated end-to-end design

Compression encodes the same message in fewer bits when its structure allows it. Lossless compression permits exact recovery; lossy compression discards some detail according to a chosen model. RLE and Huffman coding in this lesson are lossless. Entry skills are strings, loops, binary units and explicit contracts. A compressed representation can be larger for an unsuitable input, so “compression always saves space” is false. The generated Huffman tree shows the four symbol frequencies, the 0/1 branch paths and the resulting prefix-free codes. The example distinguishes its 14-bit payload from the larger total that may result once the tree and header are stored.

Run-length encoding stores consecutive repetitions as count/value pairs. For a row 00011110, runs are (3,0),(4,1),(1,0). For this toy format we store an eight-bit count followed by an eight-bit ASCII character value, making each pair 16 bits. A run longer than 255 must split into several pairs. Eight one-character alternating runs cost 128 bits for an eight-character input whose seven-bit ASCII payload is 56 bits. Thirty repeated zero characters need one pair or 16 bits versus 210 seven-bit ASCII bits. State the count width, character encoding and any header before claiming savings.

Huffman coding gives shorter bit strings to frequent symbols using a binary tree. Join the two lowest-frequency nodes repeatedly until a root remains; assign 0 and 1 to branches. Leaf paths form prefix-free codes, so no complete code is the prefix of another. For frequencies A:4, B:2, C:1, D:1, join C and D to weight 2, join B with that node to weight 4, then join A with it. One valid assignment is A=0, B=10, C=110, D=111. Ties can yield different valid trees and codes, so identical codes are not required; optimal weighted length and decodability are the meaningful properties.

For AAAABBCD, the encoded bits are 00001010110111: four A bits, four B bits, three C bits and three D bits, totaling 14. Seven-bit ASCII uses 8×7=56 bits. The ideal payload saving is 42 bits or 75%, but the recipient needs the tree or equivalent codebook and message framing. With a 48-bit header the compressed total becomes 62 bits, larger than 56. Prefix freedom does not solve every container problem: an incomplete final code must be rejected, and the number of symbols or padding length must be known.

The runnable program uses original RLE mechanics and round-trip checks. It rejects zero counts and non-single-character values on decoding. Python's random module supplies a seeded, reproducible source of synthetic test strings; the algorithm for generating pseudorandom numbers is not required by an awarding body. random is not suitable for real password generation or security tokens. Random tests complement targeted empty, alternating and long-run cases, but cannot replace a proof that each run is preserved. The independent test suite exhaustively enumerates short binary strings and checks exact recovery.

An end-to-end fictional sensor-label tool should validate its declared input alphabet, choose an encoding based on total stored bits, and decode for a verified round trip before reporting a saving. Record the rule and test outcomes without retaining personal identifiers. Security asks whether malformed counts can exhaust resources; ethics asks whether the data was necessary to collect and whether a smaller file still exposes private content. Compression is not encryption. Broader systems, networks, SQL and societal assessment remain substantial whole-subject gaps; this capstone integrates only the selected foundation slice.

Runnable original Python 3 example (also saved verbatim in examples for CLI execution):
```python
from random import Random

def rle_encode(text):
"""Return count/character pairs with counts in 1..255; text input."""
runs = []
for character in text:
if runs and runs[-1][1] == character and runs[-1][0] < 255:
count, value = runs[-1]
runs[-1] = count + 1, value
else:
runs.append((1, character))
return runs

def rle_decode(runs, maximum=10000):
"""Decode within output character budget; reject malformed runs."""
total = 0
parts = []
for count, character in runs:
if type(count) is not int or not 1 <= count <= 255:
raise ValueError("invalid count")
if not isinstance(character, str) or len(character) != 1:
raise ValueError("invalid character")
total += count
if total > maximum:
raise ValueError("output budget exceeded")
parts.append(character * count)
return "".join(parts)

assert rle_encode("00011110") == [(3, "0"), (4, "1"), (1, "0")]
assert rle_decode(rle_encode("0" * 256)) == "0" * 256
rng = Random()
for _ in range(20):
text = "".join(rng.choice("01") for _ in range(40))
assert rle_decode(rle_encode(text)) == text
```

Worked example: Use codes A=0,B=10,C=110,D=111 to encode AAAABBCD and calculate ideal payload saving against seven-bit ASCII.

Concatenate four 0 codes, two 10 codes, then 110 and 111: 00001010110111.

Bit count is 4×1+2×2+1×3+1×3=14; ASCII is 8×7=56.

Saving is 56-14=42 bits; 42/56=75%, before tree and header.

Answer: 14-bit payload; ideal 75% saving, not a guaranteed container saving.

Check your understanding: Transfer: for a 300-character zero row, the RLE toy format splits at 255 and has a 32-bit header. Calculate full bits versus seven-bit ASCII. Then explain how a malicious huge count and a mistaken “compressed means private” claim should affect the design.

Answer: Runs are (255,0),(45,0): 32 pair bits plus 32 header bits = 64, versus 2100 ASCII bits. Reject out-of-range counts and impose a total decode budget. Compression reveals recoverable content; it provides no confidentiality. Apply access controls and data minimisation separately.

Why: The arithmetic must include run splitting and framing. A valid per-run maximum alone does not prevent many runs exhausting memory, hence the total budget. Ethical evaluation links data purpose, retention and access rather than assuming a small file is harmless.