Why compress data?
Data take space to store and time to send. A photograph, a song and a video are all long sequences of bits (Topic 2.1). If we can represent the same data with fewer bits, files take less space, load faster and use less bandwidth. Data compression is the process of reducing the number of bits needed to store or transmit data.
Two points are easy to miss.
- Fewer bits does not necessarily mean less information. A good method removes redundancy (repetition) while keeping everything that matters. The text “ten dashes: –––––” can be described in a few bits without losing any information.
- How much is saved depends on two things: the amount of redundancy in the original data, and the algorithm used. A picture of a plain blue sky has a lot of repetition and compresses a great deal; a picture full of random-looking noise does not.
Lossless compression
A lossless algorithm reduces the number of bits while guaranteeing complete reconstruction of the original data. Decompress it and you get back exactly what you started with, bit for bit. This matters whenever a single changed bit would be damaging: a spreadsheet, program code, a legal document, a medical record.
A simple lossless idea: run-length encoding. Where the same value repeats, store the value once together with how many times it repeats. The string AAAAABBBCCCCCCCCDD (18 characters) becomes 5A3B8C2D (8 characters). Reading it back, 5 A’s, 3 B’s, 8 C’s and 2 D’s, rebuilds the original exactly.
Run-length encoding does not always help. If there are few repeats, the “count” can make things longer. ABCDEF becomes 1A1B1C1D1E1F, twice as long. That is why the saving depends on the redundancy in the data.
Lossy compression
A lossy algorithm can reduce the number of bits significantly, but it allows reconstruction of only an approximation of the original. Some detail is thrown away for good. Examples include reducing the number of colours in a picture, storing a sound with fewer detailed frequencies, or storing a video with less precise motion. Humans often cannot notice the difference, so the approximation is good enough.
Because it is willing to discard information, lossy compression can usually reduce size more than lossless compression. The cost is that you cannot get the exact original back, and repeatedly compressing and decompressing can lower the quality further.
Choosing between them
| Situation | Matters most | Typical choice |
|---|---|---|
| Medical scan kept for diagnosis; legal text; program code | Quality and exact reconstruction | Lossless |
| Video call on a slow connection; photo thumbnails on a web page | Small size and fast transmission | Lossy |
| A file that will be edited and saved many times | Keeping all detail | Lossless |
| Music streamed to a phone with a limited data plan | Small size, acceptable quality | Lossy |
State the priority first (quality or size), then match the type, and mention the trade-off.
Worked example 1: run-length encoding and the saving
Task. A fictional pixel row, written with R for red, G for green and B for blue, is RRRRRRGGGGBBBBBBBBRR. (a) Encode it by run-length. (b) Assume each character takes 8 bits (one byte). Work out the size before and after and the percentage saved. (c) Show that the encoding is lossless.
(a) Encode. Group the runs: RRRRRR (6 R), GGGG (4 G), BBBBBBBB (8 B), RR (2 R). Total: 6 + 4 + 8 + 2 = 20 characters. Encoded: 6R4G8B2R.
(b) Sizes. Before: 20 characters × 8 bits = 160 bits. After: 6R4G8B2R has 8 characters × 8 bits = 64 bits. Bits saved: 160 - 64 = 96. Percentage saved: 96 ÷ 160 = 0.6, so 60%. (The compressed version is 64 ÷ 160 = 40% of the original size.)
(c) Lossless check. Decode: 6 R, 4 G, 8 B, 2 R gives RRRRRR GGGG BBBBBBBB RR, which is exactly the original 20 characters. Nothing was lost.
Check. The two numbers 160 and 64 are consistent with 20 characters and 8 characters at 8 bits each. A tidy final sentence: “the encoding is smaller because the data contain long runs.”
Worked example 2: choosing a method and reading file sizes
Scenario. A fictional hospital stores a 12 MB X-ray image. It tests two methods. Method 1 produces a 7 MB file and the original can be rebuilt exactly. Method 2 produces a 1.5 MB file and the rebuilt image differs slightly from the original.
Task. (a) Classify each method. (b) Calculate the percentage saved by each. (c) Choose a method for (i) keeping the X-ray for diagnosis and (ii) sending a preview to a doctor’s phone over a weak signal.
(a) Classify. Method 1 allows complete reconstruction: lossless. Method 2 gives only an approximation: lossy.
(b) Savings. Method 1: (12 - 7) ÷ 12 = 5 ÷ 12 = 0.4167, so about 41.7%. Method 2: (12 - 1.5) ÷ 12 = 10.5 ÷ 12 = 0.875, so 87.5%. The lossy method saves much more, as expected.
(c) Choose. (i) Method 1 (lossless). For diagnosis the quality and the ability to reconstruct the exact original matter most; a small change could hide a detail. (ii) Method 2 (lossy). A preview over a weak signal needs to be small and fast, and a slightly degraded picture is acceptable for a preview; the full lossless image remains stored for diagnosis.
Check. Each choice names the priority (quality or speed), the matching method and the trade-off. It is not a mistake to use both methods in one system, for different purposes.
Why redundancy makes compression possible
Compression works because real data are rarely random. Text uses some letters far more than others; a photograph has large areas where neighbouring pixels are nearly identical; a song repeats its chorus. This predictable repetition is redundancy, and an algorithm can store the repeated pattern more cheaply than the full data. Data with no pattern at all cannot be compressed much, and an algorithm that suits one kind of data may do poorly on another.
Another lossless idea: shorter codes for common values
Suppose a message of 20 symbols uses only four symbols, A, B, C and D, with counts A 10, B 5, C 3 and D 2. A fixed-length code gives every symbol 2 bits, so the message needs 20 × 2 = 40 bits. A variable-length code gives the most common symbol the shortest code: A = 0, B = 10, C = 110 and D = 111. The total is 10 × 1 + 5 × 2 + 3 × 3 + 2 × 3 = 10 + 10 + 9 + 6 = 35 bits, a saving of 5 bits, which is 12.5% of 40. No code is the start of another, so the message can be decoded exactly: this is lossless. (This is Marlbridge’s illustration; the course does not require any named algorithm.)
How lossy methods save bits
A lossy method decides which detail matters least and discards it. A picture stored with 256 shades of grey needs 8 bits per pixel (2 to the power 8 is 256). If the shades are reduced to 16, each pixel needs only 4 bits (2 to the power 4 is 16), so the picture is half the size, at the cost of smooth shading becoming visibly stepped. Once the extra shades are discarded they cannot be recovered from the compressed file, which is why only an approximation of the original can be rebuilt.
Because the savings depend on the data, a question that gives you two compression results for the same file is really asking which method suits that data, and a question that gives you the same method on two files is asking about redundancy. Reading it that way saves time.
Common misconceptions
- “Compression deletes information, so the data are always damaged.” Lossless compression loses nothing; it removes redundancy only.
- “Fewer bits means less information.” Not necessarily: lossless methods keep all the information in fewer bits.
- “Lossy is always worse.” It depends on the purpose; when small size matters more than perfect quality it can be the better choice.
- “All compression works equally on all data.” Savings depend on the redundancy in the data and the algorithm; data with little repetition may not compress or may grow.
- “After lossy compression I can restore the original.” Only an approximation can be reconstructed.
- “Lossless is always the best.” It may produce files that are too large for the situation.
- “Compression changes what the data mean.” Lossless methods do not; lossy methods may change detail but aim to keep the meaning.
Where this leads
Compression is one way of handling the size of data; next, Extracting Information from Data asks what we can learn from data once they are stored. Compression also matters for networks in Unit 4, where sending fewer bits saves time. Practise with the practice questions, recap with the revision notes, and review your skills on the checklist.
Quick questions
Does compressing a file always make it smaller?
No. A method that works well on data with a lot of repetition may do nothing, or even make the file larger, on data with little repetition. The saving depends on both the data and the algorithm.
Can I get the original back after lossy compression?
Not exactly. Lossy compression lets you reconstruct only an approximation of the original, because some detail has been discarded for good.
Is lossy compression always bad?
No. It is the right choice when small size or fast transmission matters more than perfect quality, such as streaming video on a slow connection, as long as the loss is acceptable for the purpose.
Do I need to know the name of a compression algorithm?
No specific algorithm is required. You need to reason about lossless and lossy methods, the effect of redundancy, and which is suitable for a situation.