Skip to topic
    ← Back to course topics

    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

    1. 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
    1. 1Review core definitions: differentiate clearly between lossless and lossy compression with real-world file format examples (PNG vs JPEG, FLAC vs MP3).
    2. 2Practise manual traces of Run Length Encoding on 1D character strings and 2D monochrome pixel grids, calculating compression ratios.
    3. 3Work through dictionary compression traces (LZW style) step-by-step to understand how new substrings are added to the dictionary index.
    4. 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)
    Explain

    Set out the mathematical or logical mechanisms clearly with reasons, such as how dictionary entries replace recurring substrings with shorter bit-length indices.

    Discuss

    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)
    Pitfall: Confusing the suitability of lossy versus lossless compression for text, code, or executable files.
    ❌ Weak Answer (Loses Marks):Lossy compression can be used on text files to make them much smaller because humans cannot notice missing letters.
    Example improved answer:Lossless compression must be used for text files and program executables because discarding any data would result in syntax errors, corrupted meaning, or unexecutable code. Lossy compression permanently removes data and is only acceptable for media such as audio or video where minor data loss is imperceptible to human sensory systems.
    Examiner Tip: Always specify that lossless compression enables exact reconstruction of the original file, whereas lossy permanently discards redundant or imperceptible data.
    Pitfall: Assuming Run Length Encoding (RLE) always decreases the file size regardless of data characteristics.
    ❌ Weak Answer (Loses Marks):RLE compresses any image or text file by counting repeated characters and making the file smaller.
    Example improved answer:RLE only decreases file size if the data exhibits long contiguous runs of identical values. If applied to data with high entropy or alternating values (such as 'ABABAB'), storing both the frequency count and the value increases the total byte size compared to the original uncompressed data.
    Examiner Tip: When asked to evaluate RLE, explicitly mention that data without significant consecutive repeated patterns will actually expand in size.
    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. 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. 2.Step 2: Express runs as (count, value) pairs: (4, 0), (3, 1), (1, 0).
    3. 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. 4.Step 4: Calculate original bit requirement: 8 pixels * 1 bit per pixel = 8 bits.
    5. 5.Step 5: Calculate the compression ratio (Original size / Compressed size): 8 / 12 = 0.67:1 (or show percentage change: file increased by 50%).
    Final Answer: Encoded as (4, 0), (3, 1), (1, 0). Total compressed size is 12 bits versus 8 bits uncompressed, giving a compression ratio of 8:12 (or 0.67:1), showing that RLE has expanded this specific row.

    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. 1.Step 1: Start with current string s = 'B'. Read next character c = 'A'. Check if 'BA' is in dictionary. It is not.
    2. 2.Step 2: Output code for 'B' (2). Add 'BA' to dictionary at index 6. Set s = 'A'.
    3. 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. 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. 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. 6.Step 6: Output code for 'AN' (7). Add 'ANA' to dictionary at index 9. Set s = 'A'.
    Final Answer: Output token sequence: 2, 1, 4, 7. New dictionary entries: 6: 'BA', 7: 'AN', 8: 'NA', 9: 'ANA'.
    Active Recall Memory Test
    Why can executable machine code never be compressed using lossy techniques?
    Key Fact: Executables require absolute syntactic accuracy; losing even a single bit corrupts machine instructions or memory addresses, causing program failure.
    What data condition is required for Run Length Encoding (RLE) to achieve a positive compression ratio?
    Key Fact: The data must contain long runs of contiguous, identical values that exceed the bit overhead required to store the run count and value.
    In dictionary-based compression, what replaces recurring sequences of characters in the output file?
    Key Fact: Fixed-length or variable-length numerical codes (pointers/indices) that reference matching entries in the dictionary.
    Frequently Asked Questions
    What is the main difference between lossy and lossless compression for AQA A-Level?
    Lossless compression reduces file size without losing any data, allowing the exact original file to be reconstructed when decompressed. Lossy compression permanently removes data that is deemed imperceptible or redundant to the human senses. Lossless is mandatory for text, code, and critical data, whereas lossy is used for audio, video, and photography to achieve much smaller file sizes.
    Can Run Length Encoding make a file larger?
    Yes. If data contains few or no consecutive identical values, storing the run length alongside each individual value adds extra bytes. For example, compressing alternating characters like 'ABABAB' would result in pairs like (1,'A'), (1,'B'), doubling the required storage compared to the original raw characters.
    How does dictionary-based compression work on text files?
    Dictionary-based algorithms build a table of character strings that recur frequently in the text. When a recognised string appears again, the algorithm replaces it with a short numerical index pointing to its position in the dictionary. Because the numerical pointer uses fewer bits than the sequence of characters it replaces, the overall file size decreases.
    Why does compressing an already compressed zip file rarely make it smaller?
    Compressed files already have their statistical redundancy removed, resulting in high entropy where symbols appear largely random. Since lossless algorithms rely on patterns and recurring sequences to reduce bit length, running compression on high-entropy data cannot identify further redundancies and often causes the file to expand due to added header metadata.