IB COMPUTER SCIENCE | A1.1.8 Compression

Lesson objective

Describe compression, distinguish lossless and lossy methods, and explain run-length encoding and the transform–quantisation approach to image coding.

Learn

A1.1.8 | COMPRESSION

01 | THE SAME PURPOSE, FEWER BITS

A photograph, sound recording or program file is represented by bits. Compression represents data using fewer bits where possible, reducing the amount that must be stored or transmitted. The receiver or application uses a corresponding decoding process to recover usable data.

A smaller attachment can take less time to send over the same connection, and a compressed collection can use less storage space. There is still work to do: compression and decompression require processing, and some methods trade exact recovery for a smaller representation.

The important distinction is between lossless compression, which allows exact recovery of the original data, and lossy compression, which discards some information. This IB objective also includes run-length encoding and transform coding.

Do not confuse compression with encryption. Encryption protects information by changing its representation according to a cryptographic method and key. Compression aims to reduce size; it does not by itself make a file confidential.

02 | WHY DATA CAN SOMETIMES BE REPRESENTED MORE COMPACTLY

Some data contains repeated patterns or predictable relationships. Writing out every repeated item separately can be less efficient than describing the pattern and how many times it occurs.

For example, twelve identical pixels in a row could be described as twelve copies of one value rather than twelve separately stored values, if the chosen encoding format makes that description shorter. The decoder must know the rule and have enough information to reconstruct the row.

Not every input has useful repetition for a particular method. A compressed file already tends to have less exploitable redundancy. Applying another compression stage may save little or even increase the size because of added headers or a poor match to the data.

No lossless method can make every possible input shorter. If all distinct inputs were mapped to too few shorter representations, the decoder could not uniquely recover every original. Practical methods exploit patterns that occur in the data they are designed for.

03 | LOSSLESS: EXACT RECOVERY MATTERS

Lossless compression represents data in a way that allows the original information to be reconstructed exactly. The compressed representation looks different, but decoding restores the original sequence.

This matters for source code, executable programs, database records and other information where a changed symbol or value could alter meaning or behaviour. A program that comes back “almost the same” may not run correctly.

A lossless image format can also preserve the exact pixel values presented to its encoder, which can be useful for diagrams or further editing. It does not restore detail that had already been removed before encoding.

Run-length encoding is one lossless method. ZIP-style archives and PNG images use other lossless techniques or combinations; do not assume every lossless file uses run-length encoding.

04 | RUN-LENGTH ENCODING: COUNT CONSECUTIVE REPEATS

Run-length encoding (RLE) replaces a consecutive run of identical values with a description containing the value and its repetition count. A run ends when the next value changes.

Consider AAAAAABBBBCC. The sequence has six A symbols, then four B symbols, then two C symbols. We can describe it with the pairs (6, A), (4, B), (2, C), where each pair means count followed by symbol.

The decoder repeats A six times, B four times and C twice, in the same order. Nothing has been approximated or discarded: the original twelve symbols are recovered exactly.

Consecutive runCountSymbolDecoded output
AAAAAA6AAAAAAA
BBBB4BBBBB
CC2CCC

Consecutive is essential. ABABAB has six runs of length one, not a run of three A symbols followed by three B symbols. Combining those separated values would change the order and corrupt the original sequence.

05 | DOES THIS RLE FORMAT ACTUALLY SAVE SPACE?

An example is only useful if its storage assumptions are clear. Suppose each original A–D symbol uses one byte, and every RLE pair uses one byte for the count plus one byte for the symbol. Header and metadata costs are ignored in this small model.

AAAAAABBBBCC uses twelve bytes originally. Its three pairs use six bytes. That is half the original size. In contrast, the twelve-symbol sequence ABABABABABAB has twelve one-symbol runs, so its pairs use twenty-four bytes in this encoding.

The same lossless algorithm therefore compresses one input and expands the other. Real formats may switch strategies or add special rules, but those rules and their overhead must also be defined.

The written notation (6, A) is for people to read. Our model stores two one-byte fields, not the literal brackets, comma and space. Counting printed characters in the notation would use a different representation.

06 | TRY ENCODING AND DECODING A SEQUENCE

Enter up to 64 symbols using A, B, C and D. These represent four possible data values. The activity groups consecutive runs, displays the pairs and decodes them back to check exact recovery.

Try the long-runs and alternating examples. Compare their byte counts before claiming that RLE always reduces file size. A run of up to 64 fits in the one-byte count field used by this model.

Byte model: one byte per original symbol, two bytes per count–symbol pair; no file header or metadata included.

07 | LOSSY: KEEP AN APPROXIMATION

Lossy compression removes some information so the decoded result is an approximation of the original. The original discarded detail cannot be uniquely reconstructed from that compressed file alone.

For a photograph displayed at a modest size, a small change in fine detail may be acceptable if it makes the file much smaller. For audio or video distribution, a suitable lossy method can reduce the amount of data sent while preserving acceptable perceived quality.

The trade-off depends on the content, settings and intended use. A strong setting can introduce visible blocks, ringing around edges or other artefacts; audio methods can introduce audible changes. Lossy does not mean the result must always look or sound obviously poor.

It also does not mean every operation called compression throws away pixels or lowers the image dimensions. Lossy methods can change the information represented at the same dimensions.

08 | TRANSFORM CODING: DESCRIBE PATTERNS INSTEAD OF PIXELS

An image can be described by the brightness at each pixel. Transform coding changes the representation into a set of coefficients that describe contributions from different patterns. A coefficient is a numerical weight indicating how much of a pattern is present.

One example is the discrete cosine transform, or DCT, used in common JPEG-style image compression. A block of pixel values is represented by weights for cosine patterns ranging from slowly varying brightness to rapidly changing detail.

Low spatial frequencies represent broad, smooth changes across the image. High spatial frequencies represent rapid changes such as fine texture and sharp transitions. Spatial frequency here describes variation across image positions, not sound pitch or processor clock speed.

A mathematical transform by itself does not necessarily reduce the number of coefficients or discard information. With adequate precision and an invertible transform, an inverse transform can recover the input. The important compression decisions come next.

09 | QUANTISATION: WHERE THE APPROXIMATION IS INTRODUCED

In a lossy transform-based method, coefficients can be quantised: represented using coarser allowed values. A simple teaching rule divides a coefficient by a step size and rounds it, then reconstructs it by multiplying by that step.

For example, with step 10, coefficients 23 and 24 both round to 2 after division. Reconstruction produces 20. The decoder cannot know whether the original value was 23 or 24, so exact recovery is lost.

Small coefficients can become zero. A sequence containing many zeros and small values may then be represented efficiently by later coding stages. Those later stages can themselves be lossless; they preserve the already-quantised coefficients, not the original pixels.

Real image encoders commonly use different quantisation strengths for different coefficients and may include other stages. The key chain is transform, quantise, encode; decoding reverses the coding and applies an inverse transform to the available approximate coefficients.

A SIMPLIFIED TRANSFORM-CODING PATH
  1. Transform: represent a block as weighted patterns.
  2. Quantise: round coefficients more coarsely, losing precision.
  3. Encode: represent the resulting values efficiently.
  4. Decode and reconstruct: recover the quantised representation and apply the inverse transform.

Quantisation is the information-losing step in this simplified path. The inverse transform does not restore the discarded precision.

10 | SEE A TRANSFORM AND QUANTISATION EXAMPLE

This activity calculates a two-dimensional DCT for one 8 × 8 grayscale block, then reconstructs it with an inverse DCT. Choose no quantisation first: the reconstructed integer pixel values match the original in this example.

Then choose a quantisation step. The activity rounds each coefficient after dividing by that same step, reconstructs the approximate coefficients and applies the inverse transform. Compare the image and the average absolute pixel difference.

This is a real mathematical transform on a small artificial block, but not a complete JPEG encoder. It uses uniform quantisation, no colour subsampling and no final compressed bitstream. The zero count illustrates a pattern that later coding might exploit; it is not a measured file size or compression ratio.

ORIGINAL 8 × 8 BLOCK

RECONSTRUCTED BLOCK

Inspect the coefficient representation

Rows and columns identify transform-pattern frequencies, not pixel positions. With quantisation selected, entries are rounded coefficient indices; without it, approximate original coefficients are shown. The top-left coefficient represents the constant component after the model’s brightness offset.

Transform coefficients

11 | LOSSLESS AND LOSSY SIDE BY SIDE

QuestionLossless compressionLossy compression
Can original encoder input be recovered exactly?Yes, with correct decoding and intact data.Not in general: information has been discarded.
What supports size reduction?A more efficient reversible representation of patterns or other redundancy.An approximation that removes information, often followed by efficient lossless coding.
Suitable examplesSource files, database exports and images requiring exact pixel preservation.Photographs, audio or video where the chosen quality is acceptable.
Does every file become smaller?No; the method and data determine the result.Size and quality depend on the method, settings and content.
What must be checked?Format support, encoded size and exact recovery.Perceived quality, acceptable information loss and encoded size.

A filename alone can be misleading. Some formats support more than one mode, and a lossless container cannot restore information removed earlier. Describe the actual encoding process and the requirement, rather than relying only on a file extension.

12 | DESCRIBE SIZE REDUCTION WITHOUT MIXING THE NUMBERS

Always compare sizes in the same units. One common convention defines compression ratio as original size divided by compressed size. Under that convention, reducing twelve bytes to six gives a 2:1 ratio.

Percentage size reduction is (original − compressed) ÷ original × 100. Twelve to six is a 50% reduction. The compressed size as a percentage of the original is also 50% in this example, but those two percentages are different calculations in general.

If a file changes from 100 MB to 25 MB, the ratio is 4:1, the size reduction is 75%, and the remaining size is 25% of the original. State the convention because some resources use different ratio directions.

Smaller transmitted data can reduce transfer time if the effective link rate stays the same, but compression and decompression take time too. Headers, metadata and protocol overhead also matter in a real system.

13 | MATCH THE METHOD TO THE REQUIREMENT

SituationSuitable approach to considerReason or caution
Download an executable programLosslessThe original instruction bytes must be recovered exactly.
Keep an exact database exportLosslessValues and structure must not be approximated.
Encode a simple row with long identical runsRLE may be usefulConsecutive repetition can be described with fewer count–value pairs.
Encode a rapidly alternating sequenceCheck RLE size carefullyMany short runs can make the representation larger.
Distribute photographs for a websiteA suitable lossy transform-based method may be acceptableFine precision can be traded for size if the quality is sufficient.
Retain exact image data for later analysisLossless or an explicitly validated workflowDiscarded detail may matter to the analysis; do not assume acceptable visual appearance is enough.

No method wins for all data. A good answer names the requirement, describes how the method represents information and states whether exact recovery is possible.

14 | AVOID THESE COMMON CONFUSIONS

ConfusionCorrection
Lossless means no encoding happened.The representation changes but permits exact recovery.
RLE counts all occurrences anywhere in the file.It counts consecutive runs and preserves their order.
Compression always shrinks a file.A poor match or overhead can cause expansion.
The transform alone must be the lossy step.A reversible transform changes representation; coefficient quantisation introduces loss in this example.
More zero coefficients means a known exact file size.Final size depends on the coding format and overhead; the demo does not generate that bitstream.
A lossless save restores earlier lost detail.It preserves the input it receives, not information discarded before that input existed.
Every smaller image has fewer pixels.Compression can change representation or precision without changing dimensions.

For describe compression, explain fewer-bit representations, distinguish exact from approximate recovery, and use a concrete method. For RLE, show the consecutive counts. For transform coding, connect coefficients, quantisation and reconstruction.

Further reading: PNG’s lossless format specification · JPEG encoder settings and transform implementation context

MATCH THE COMPRESSION TERM TO ITS MEANING

Terminology

Terminology

Compression

Representing data using fewer bits where possible.

Decompression

Decoding a compressed representation into usable data.

Lossless compression

Compression permitting exact recovery of the original encoder input.

Lossy compression

Compression that discards information, giving an approximate reconstruction.

Redundancy

Patterns or repetition that may allow a more compact representation.

RLE

Run-length encoding: describing consecutive repeats using their value and count.

Run

A consecutive sequence of identical values.

Count–value pair

A representation recording how many times a value repeats consecutively.

Encoding format

The defined rules used to represent and interpret data.

Overhead

Additional information such as headers and metadata needed by a format.

Transform coding

Representing data using transform coefficients, which can then be quantised and encoded.

Coefficient

A numerical weight describing the contribution of a pattern in a transformed representation.

DCT

Discrete cosine transform: a transformation representing data using weighted cosine patterns.

Spatial frequency

The rate of variation of an image pattern across spatial positions.

Quantisation

Mapping values to a coarser set of allowed representations.

Inverse transform

A process reconstructing data from its transform coefficients.

Artefact

An introduced visual or audible feature associated with processing or approximation.

Grayscale

An image representation using brightness values without colour components.

Compression ratio

A size comparison; this page uses original size divided by compressed size.

Size reduction

The decrease relative to original size, often expressed as a percentage.

Bitstream

A sequence of encoded bits representing the file or data.

Exact recovery

Reconstructing the original input values without approximation.

Reconstruction

The data produced by decoding and any required inverse processing.

Metadata

Information describing the data or how it should be interpreted.

Encryption

A cryptographic process for protecting information, distinct from compression.

Precision

The fineness with which numerical values are represented.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which statements distinguish the two compression categories?
2. How should AAAAAABBBBCC be represented using count then symbol?
3. Why can RLE expand ABABABABABAB in the page’s byte model?
4. Which claim about a transform is correct?
5. Which are correct for the quantisation example with step 10?
6. Why can small quantised coefficients becoming zero help compression?
7. Which files normally require exact recovery?
8. A file shrinks from 100 MB to 25 MB. Which are correct under this page’s convention?
9. What does the transform activity measure?
10. Which statements are accurate?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Describe compression and one practical benefit.

2. Describe the difference between lossless and lossy compression.

3. Describe RLE using AAAAAABBBBCC.

4. Explain why RLE can increase size.

5. Describe transform coding.

6. Explain why quantisation prevents exact recovery in the example.

7. Describe what the DCT activity shows and what it does not.

8. Describe an appropriate choice for an executable program and a website photograph.

9. Calculate a ratio and reduction for 80 MB becoming 20 MB.

10. Explain why saving an already-lossy image in a lossless format does not restore it.

APPLY IT | CODE, DIAGRAMS AND PHOTOGRAPHS

A team distributes an executable program, an exact database export and photographs for a project website. Describe an appropriate compression approach for each and justify whether loss is acceptable. Then RLE-encode AAAABBBCCD using count–symbol pairs and compare byte counts under the page’s stated format.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

    Selections are kept while this page is open.

    Workbook

    Workbook

    COMING SOON

    The workbook for A1.1.8 Compression is coming soon. Complete the matching task and written questions in your exercise book.