Computer ScienceFoundation18 min read

Data Storage and Compression

Making files smaller, and deciding what you can afford to lose

This topic appears in:

O Level Computer Science (2210) · ch.1A Level Computer Science (9618) · ch.1
01

Why compress at all

Compression reduces the number of bits a file occupies. That matters for three reasons the syllabus asks about: less storage space is used, files transmit faster over a network, and less bandwidth is consumed — which costs money on a metered connection.

There are two kinds, and the difference between them is the whole topic. Lossless compression allows the original to be reconstructed exactly. Lossy compression discards some data permanently in exchange for a much smaller file.

LosslessLossy
Original recoverable?exactlynever
Size reductionmodestlarge
Used fortext, spreadsheets, program codephotographs, music, video
Example formatsZIP, PNG, FLACJPEG, MP3, MP4
Repeated compressionsafequality degrades each time

Never use lossy compression on a program or a spreadsheet

Lossy compression works because the eye and the ear do not notice small changes. A program file has no such tolerance — altering a single bit can stop it running, and a changed digit in a spreadsheet is simply a wrong number. Any file where every bit matters must be compressed losslessly or not at all.

02

How lossless compression works

Lossless methods find repetition and describe it more briefly, without discarding anything.

Run-length encoding replaces a sequence of identical values with the value and a count: WWWWWWBBB becomes 6W3B. It works extremely well on images with large flat areas and badly on photographs, where adjacent pixels rarely match exactly.

Dictionary methods build a table of repeated sequences and replace each occurrence with a short reference to the table. Since the table is stored with the file, the original can always be rebuilt exactly.

Worked example

Apply run-length encoding to AAAABBBCCCCCCD and calculate the saving, assuming one byte per character and one byte per count.

  1. Group the runs: four A, three B, six C, one D.Each run becomes one value and one count.
  2. Encoded as 4A 3B 6C 1D.Eight items — four counts and four characters.
  3. Original = 14 bytes; encoded = 8 bytes.
  4. Saving = 6 bytes, about 43%.Note that a single D still costs two bytes to encode — run-length encoding can make a file with no repetition LARGER.

4A3B6C1D — 8 bytes instead of 14, a saving of about 43%

03

How lossy compression works

Lossy methods discard information that human perception is least likely to notice, then store what remains.

For images, a JPEG reduces the precision of colour information — the eye is far more sensitive to brightness than to fine colour detail — and merges similar nearby colours. For sound, an MP3 removes frequencies outside human hearing and quieter sounds masked by louder ones occurring at the same moment.

The reduction is dramatic: a JPEG is routinely a tenth of the size of the equivalent bitmap. What is discarded is gone permanently, and compressing an already-compressed file again degrades it further.

Generation loss

Open a JPEG, edit it, save it, and repeat. Each save discards a little more, and after enough cycles the image visibly deteriorates. This is why photographers keep an uncompressed or losslessly compressed master and export lossy copies from it, rather than editing the JPEG itself.

04

Storage devices and units

Compression is one answer to limited storage; the other is choosing the right medium. Each has different characteristics and the syllabus expects the comparison.

Magnetic storage — hard disks — uses magnetised regions on spinning platters. Large and cheap per gigabyte, but the moving parts make it slower and vulnerable to shock. Optical storage — CD, DVD, Blu-ray — uses pits burned into a surface and read by laser. Cheap, portable and durable, but slow and small by modern standards. Solid state storage — SSDs and flash drives — has no moving parts, so it is fast, silent and shock-resistant, but costs more per gigabyte and each cell tolerates only a limited number of writes.

8 bits = 1 byte1 kibibyte (KiB) = 1024 bytes1 mebibyte (MiB) = 1024 KiB1 gibibyte (GiB) = 1024 MiB1 tebibyte (TiB) = 1024 GiBmanufacturers often use powers of 1000 instead, which is why a "1 TB" disk shows as about 931 GB

Before you leave this chapter

  1. Compression saves storage, transmission time and bandwidth.
  2. Lossless recovers the original exactly; lossy discards data permanently.
  3. Text, spreadsheets and program code must be lossless. Photos, music and video can be lossy.
  4. Run-length encoding replaces runs with a value and a count — and can enlarge a file with no repetition.
  5. Magnetic is cheap and large, optical is portable, solid state is fast with no moving parts.
05

Reducing a file without a compression algorithm

Compression is not the only way to make a media file smaller. The settings that determine its size in the first place can simply be reduced, and the syllabus expects both routes.

For an image: fewer pixels, or fewer bits per pixel. For a sound: a lower sample rate, a lower resolution, or mono instead of stereo. Each reduces the file in direct proportion, and each loses something specific — detail, colour accuracy, high frequencies or stereo separation.

Drag sample rate down and the samples no longer follow the wave. Drag resolution down and each sample lands further from the true height. Both shrink the file, and both are visible as a worse reconstruction.

Reducing settings is lossy too

Halving the sample rate is a permanent loss just as much as MP3 compression is — the discarded measurements cannot be recovered. The difference is that a compression algorithm chooses which information to discard using knowledge of human perception, whereas reducing the settings discards indiscriminately. That is why an MP3 at a given size sounds better than a raw recording reduced to the same size.

Practice questions

6 questions · 20 marks · full working on every one

Try each one on paper first, then open the working. The marks are shown where they are actually awarded, because that is where they are actually lost.

Short questions

3 · 6 marks

Two marks each, in the style of the short-question section of the paper. Answer in two or three lines.

SQ1[2 marks]
State two reasons for compressing a file.
Model answer

It uses less storage space, and it transmits faster over a network while using less bandwidth — which reduces cost on a metered connection.

Examiner tip. Storage and transmission are the two the mark scheme wants. They are separate benefits and both should be named.

SQ2[2 marks]
Explain the difference between lossy and lossless compression.
Model answer

Lossless reduces the file size in a way that allows the original to be reconstructed exactly. Lossy discards some data permanently, giving a much smaller file that can never be restored to the original.

Examiner tip. The word "exactly" is the mark. Saying lossy "loses quality" is vaguer than saying the original cannot be recovered.

SQ3[2 marks]
Why must a program file not be compressed using a lossy method?
Model answer

Lossy compression alters the data, and in a program every bit matters — changing even one instruction could stop the program running or make it behave incorrectly. Lossy methods rely on human perception tolerating small changes, and a computer executing code has no such tolerance.

Examiner tip. The reason is that there is no perceptual slack to exploit. The same argument applies to spreadsheets and databases.

Solved numericals

2 · 8 marks

Full working, one step per line, with the marks shown where they are awarded.

N1[4 marks]
Apply run-length encoding to RRRRRGGGBBBBBBBB and comment on when this method works poorly.
Full working
  1. Runs identified: five R, three G, eight B[1]
  2. Encoded as 5R 3G 8B — six items instead of sixteen characters[1]
  3. It works poorly when adjacent values rarely repeat, such as in a photograph where neighbouring pixels differ slightly[1]
  4. In that case each run has length 1 and the encoding stores a count as well as the value, making the file larger than the originalthe enlargement is the key insight[1]

5R3G8B; it fails on data with little repetition, where it can increase the file size.

Examiner tip. That RLE can make a file bigger is the point examiners look for. It explains why photographs use a different method entirely.

N2[4 marks]
Compare magnetic, optical and solid-state storage, giving one advantage and one disadvantage of solid-state.
Full working
  1. Magnetic uses magnetised regions on spinning platters — large capacity and cheap per gigabyte[1]
  2. Optical uses pits read by laser — portable and cheap, but small capacity and slow[1]
  3. Solid-state advantage: no moving parts, so it is much faster, silent and resistant to being dropped[1]
  4. Disadvantage: higher cost per gigabyte, and each memory cell tolerates only a limited number of writesthe write-endurance point is the stronger one[1]

Magnetic cheap and large, optical portable, solid-state fast but dearer with limited write endurance.

Examiner tip. Write endurance is the disadvantage most students miss, and it is the reason an SSD should never be defragmented.

Long questions

1 · 6 marks

Theory and numerical together, as they appear in the long-question section.

LQ1[6 marks]
A school is setting up a system to store student photographs, exam scripts as scanned documents, and the school database.
  1. Recommend a compression approach for the photographs, with a reason.
  2. Recommend one for the database, with a reason.
  3. Explain why the total storage needed cannot be reduced indefinitely by compressing repeatedly.
Mark scheme
  1. Photographs: lossy compression such as JPEG[1]
  2. The reduction is large and the discarded detail is not noticeable in a photograph viewed normally, so the loss costs nothing in practice[1]
  3. Database: lossless compression, or none at all[1]
  4. Every value must be recoverable exactly — a changed digit in a mark or a date is simply wrong data, with no perceptual tolerance to exploit[1]
  5. Lossless compression works by removing repetition, and once the repetition is gone there is nothing further to remove[1]
  6. Compressing an already-compressed file usually achieves nothing and can make it slightly larger, since the compression data itself must be storedaccept that repeated lossy compression degrades quality instead[1]

(a) lossy — the loss is imperceptible (b) lossless — every value must be exact (c) once repetition is removed there is nothing left to compress

Examiner tip. Part (c) is the understanding mark. Compression exploits redundancy, and a file with no redundancy left cannot be made smaller without discarding real information.