Students should be familiar with the process of using frequency/data pairs…

The idea

Run length encoding (RLE) stores data as frequency/data pairs: a count of how many times a value repeats, followed by that value. Instead of writing every item, you record how many there are and what they are. For example, a row of pixels reading black, black, black, black, white, white becomes the pair 4/black then 2/white. The file is smaller because repeated runs collapse into one count plus one value. The saving is greatest when long runs repeat; if values rarely repeat, each run has frequency 1 and the pairs may take as much space as the original, so RLE is not always worthwhile. Learners should be able to explain why the pair representation reduces stored data and identify when it does not help.

What earns the marks

• RLE replaces a repeated run of identical values with a frequency (how many times the value occurs) and the data value itself.
• A frequency/data pair records the count first and the value second, for example 4/black meaning four black pixels in a row.
• Data is reduced because a long run of identical items is stored as one count plus one value rather than many separate items.
• Compression is most effective when there are long runs of the same value; when values rarely repeat, pairs of frequency 1 add little or no saving.
• The technique is lossless for this representation because the original sequence can be rebuilt exactly from the pairs.

Common mistakes and how to put them right

• Writing the value before the frequency.

  Put it right: The pair is frequency first, then the data value, so four black pixels is 4/black.

• Assuming RLE always shrinks a file.

  Put it right: If values seldom repeat, each run has frequency 1 and the pairs may be no smaller than the original.

• Confusing RLE with lossy compression.

  Put it right: RLE here is lossless because the exact original sequence can be reconstructed from the pairs.

Exam tips

• Read the question carefully to check whether it asks for the frequency first or the value first, and follow the stated order.
• When explaining the saving, compare the number of stored items before and after, not just the number of runs.
• For a 'when is it not useful' question, state that short or non-repeating runs give little or no reduction.