Course 1.3Lesson 3 of 3
Compression makes a file smaller, so it needs less storage and less time to send. You learn why we compress, the difference between lossy and lossless compression, and how run-length encoding squeezes repeated data without losing any of it.
Try the code and the simulations beside the lesson.
You send a holiday photo to a friend, and it arrives in a moment. The phone has made the file smaller first. Compression reduces the size of a file. That brings three benefits.
There are two kinds of compression.
Lossy compression reduces the file size by permanently removing data. The removed data can never be brought back. It is chosen so that a person hardly notices the loss.
The picture shows an image of 16 by 16 pixels, and the same image after its resolution is cut to 4 by 4. The second file is one sixteenth of the size, but the fine detail has gone for good.
Lossy compression can make files very small. It suits photos, music and video, where a small loss is acceptable. It does not suit a text document or a program, where every bit must come back exactly.
Lossless compression reduces the file size without permanently losing any data. When the file is decompressed, it is exactly the same as the original. It saves less space than lossy compression, but nothing is lost.
The method in this syllabus is run-length encoding (RLE).
Data often has runs: the same value many times in a row. A row of sky in a picture may be the same blue for many pixels. RLE stores each run once, as a pair: how many times the value repeats, and the value.
Look at this line of text, 12 characters long.
AAAAABBBCCCCThere are three runs: 5 A, 3 B and 4 C. RLE stores it as the pairs (5, A), (3, B), (4, C). If the count and the character take one byte each, that is 6 bytes instead of 12.
The picture shows one row of an image with 20 pixels: 9 white, 4 black and 7 white. Stored one byte a pixel, the row takes 20 bytes. With RLE it is three pairs, which is 6 bytes. Decoding writes each value out the number of times its count says, so the row comes back exactly. That is why RLE is lossless.
When RLE does not help. If the data has no runs, every pair has a count of 1. The text ABCD becomes (1, A), (1, B), (1, C), (1, D), which is 8 bytes instead of 4. RLE works best when the data has long runs.
This algorithm reads a string and outputs each run as its count followed by its character. SUBSTRING(Text, Position, 1) gives one character, and LENGTH(Text) gives the number of characters. The site cannot run pseudocode, so it is shown in a plain box.
// Run-length encoding of a string
DECLARE Text : STRING
DECLARE Count : INTEGER
DECLARE Position : INTEGER
INPUT Text
Count ← 1
FOR Position ← 2 TO LENGTH(Text)
IF SUBSTRING(Text, Position, 1) = SUBSTRING(Text, Position - 1, 1)
THEN
Count ← Count + 1
ELSE
OUTPUT Count, SUBSTRING(Text, Position - 1, 1)
Count ← 1
ENDIF
NEXT Position
OUTPUT Count, SUBSTRING(Text, LENGTH(Text), 1)The Python program below follows the same steps, so you can run it.
The program encodes a string with run-length encoding, decodes it again, and checks that nothing was lost. It also prints the sizes before and after.
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Every lesson is open to read. Enrolling also lets you:
Log in to join the discussion.
Loading…
This lesson is free to read. Enroll free to keep your place and take the tests.