Data compression — AQA A-Level Computer Science
Data compression reduces the bit size of files to conserve storage space and decrease transmission times across networks. In AQA A-Level Computer Science, students must master both lossy and lossless techniques, notably Run Length Encoding (RLE) and dictionary-based methods like LZW.
Data compression explained
Lossless compression reduces the size of a file so that the original data can be rebuilt exactly, bit for bit, when it is decompressed.
Read the full explanation
Nothing is discarded. The principle that makes this possible is redundancy: many files contain repeated patterns, long runs of the same value or predictable sequences, and an encoder can replace these with shorter codes that record enough information to reverse the process. Explaining a technique therefore means stating what kind of redundancy it exploits, how the encoder represents that redundancy more compactly, and why the decoder can recover the original exactly. Students should be able to explain this for each technique named in the course, and to distinguish lossless methods, where the original is fully recoverable, from lossy methods, which deliberately discard data that is judged less important and so cannot be restored exactly.
Your focus
- Explain the principles behind the following techniques for lossless compression:
Data compression exam tips
Topic Overview
Data compression is the process of modifying, encoding, or converting the bit structure of data to reduce its overall bandwidth consumption and storage footprint. It plays a critical role in networking, database optimisation, and modern multimedia distribution where transmission channels have finite capacity.
Within the AQA A-Level specification, students examine the mechanical differences between lossy and lossless algorithms, analysing Run Length Encoding (RLE) and dictionary-based compression techniques. Understanding these methods connects fundamental data representation to practical computing systems, including web protocols, file formats, and network throughput limits.
Key Concepts
- →Lossless compression algorithms reduce file size by identifying and eliminating statistical redundancy without discarding any original information, allowing perfect bit-level reconstruction.
- →Lossy compression algorithms permanently discard perceptually redundant or less critical data (exploiting limits of human vision and hearing) to achieve far higher compression ratios.
- →Run Length Encoding (RLE) represents consecutive sequences of identical data values as a single frequency count and value pair.
- →Dictionary-based compression replaces repeated tokens, words, or character sequences with compact numerical pointers corresponding to an internal or external lookup table.
Marking Points
- Identifies redundancy in the data as the basis of lossless compression
- Explains that the encoder replaces repeated or predictable content with a shorter representation
- States that the decoder reverses the encoding so the original data is recovered exactly
- Distinguishes lossless compression, where no data is lost, from lossy compression, where some data is discarded
Examiner Tips
- 💡For each technique, name the redundancy first, then the encoding, then why decoding restores the original
- 💡Use the phrase 'bit for bit' or 'exactly the same' to show you understand lossless recovery
- 💡Compare with lossy methods only when the question asks, and keep the comparison to what is lost
- 💡Use exact terminology when answering scenario questions: describe data as 'statistically redundant' or 'perceptually redundant' rather than simply 'unimportant'.
- 💡When explaining dictionary-based compression, clearly distinguish between the initial static alphabet dictionary and dynamically generated phrases created during tokenisation.
Common Mistakes
- Describes lossless compression as removing unimportant data; correct it by stating that nothing is discarded and the original can be rebuilt exactly
- Explains a technique without naming the redundancy it exploits; state the pattern in the data that the method relies on
- Assumes any compressed file can be restored exactly; only lossless methods guarantee this
- By the pigeonhole principle and information theory (Shannon's source coding theorem), a lossless algorithm cannot compress all possible inputs; high-entropy or already compressed files will stay the same size or expand.
- Lossy compression is essential for high-bandwidth media (e.g., MP3 audio, JPEG images, H.264 video) where minor precision loss is imperceptible to humans, yielding bandwidth savings unattainable with lossless methods.
Revision Plan
- 1Review core definitions: differentiate clearly between lossless and lossy compression with real-world file format examples (PNG vs JPEG, FLAC vs MP3).
- 2Practise manual traces of Run Length Encoding on 1D character strings and 2D monochrome pixel grids, calculating compression ratios.
- 3Work through dictionary compression traces (LZW style) step-by-step to understand how new substrings are added to the dictionary index.
- 4Complete past AQA exam questions evaluating compression choices for specific network scenarios such as database backups versus live video streams.
Exam Question Types
- 📋Comparison questions: Contrasting lossy and lossless compression in given scenarios (e.g., medical imaging vs. streaming music).
- 📋Algorithm trace questions: Stepping through RLE or dictionary-based encoding on a given string or pixel sequence and showing the output tokens.
- 📋Evaluation questions: Assessing whether a specific compression method will reduce file size based on the frequency distribution and entropy of the source data.
Command Word Expectations (AQA)
Set out the mathematical or logical mechanisms clearly with reasons, such as how dictionary entries replace recurring substrings with shorter bit-length indices.
Explore multiple perspectives or trade-offs (e.g., processing overhead and fidelity loss versus transmission speed and bandwidth savings) before reaching a reasoned conclusion.
How Students Lose Marks (Examiner Pitfalls)
Step-by-Step Worked Solutions
Question: A monochrome bitmap image of dimensions 8x8 pixels is represented using binary, where 0 is white and 1 is black. Row 1 contains: 0 0 0 0 1 1 1 0. Explain how Run Length Encoding (RLE) encodes this row using frequency-value pairs, and calculate the compression ratio if the uncompressed row uses 8 bits and the RLE format uses 4 bits per run (2 bits for run length, 2 bits for pixel value).
- 1.Step 1: Identify consecutive runs in the binary row (0, 0, 0, 0, 1, 1, 1, 0). Run 1: four 0s. Run 2: three 1s. Run 3: one 0.
- 2.Step 2: Express runs as (count, value) pairs: (4, 0), (3, 1), (1, 0).
- 3.Step 3: Calculate RLE bit requirements. There are 3 runs, each requiring 4 bits (2 bits for length + 2 bits for value): 3 * 4 = 12 bits.
- 4.Step 4: Calculate original bit requirement: 8 pixels * 1 bit per pixel = 8 bits.
- 5.Step 5: Calculate the compression ratio (Original size / Compressed size): 8 / 12 = 0.67:1 (or show percentage change: file increased by 50%).
Question: A dictionary-based compression algorithm processes the string 'BANANA_BAND'. The initial dictionary maps standard ASCII characters to integer indices (e.g., A=1, B=2, D=3, N=4, _=5). Construct the dictionary additions and the compressed output sequence for the first 6 characters: 'BANANA'.
- 1.Step 1: Start with current string s = 'B'. Read next character c = 'A'. Check if 'BA' is in dictionary. It is not.
- 2.Step 2: Output code for 'B' (2). Add 'BA' to dictionary at index 6. Set s = 'A'.
- 3.Step 3: Read next character c = 'N'. Check if 'AN' is in dictionary. It is not. Output code for 'A' (1). Add 'AN' to dictionary at index 7. Set s = 'N'.
- 4.Step 4: Read next character c = 'A'. Check if 'NA' is in dictionary. It is not. Output code for 'N' (4). Add 'NA' to dictionary at index 8. Set s = 'A'.
- 5.Step 5: Read next character c = 'N'. Check if 'AN' is in dictionary. It is in dictionary (index 7). Set s = 'AN'. Read next character c = 'A'. Check if 'ANA' is in dictionary. It is not.
- 6.Step 6: Output code for 'AN' (7). Add 'ANA' to dictionary at index 9. Set s = 'A'.