Cambridge O Level Computer Science · Syllabus 2210 · Data Representation
Run-Length Encoding
What is Run-Length Encoding?
Run-length encoding is a lossless compression method that replaces a run of consecutive identical values with the value and the number of times it repeats, so the original data can be rebuilt exactly.
This definition is part of the Data Representation chapter in Cambridge O Level Computer Science.
Run-Length Encoding in context
Lossy compression reduces the file size by permanently removing data. The original cannot be reconstructed exactly, and quality may fall — the more the file is compressed, the more noticeable that loss becomes. Lossless compression reduces the file size without permanently losing any data, so the original can be reconstructed exactly. Run-length encoding is the syllabus example of a lossless method.
Run-length encoding (RLE) is a lossless method. Wherever the data contains a run of consecutive identical values, RLE replaces that run with two pieces of information: the value and the run length (how many times it repeats). Because the run length is recorded exactly, decoding rebuilds the original data perfectly. RLE works best on data containing long runs of repeated values, and can fail to reduce — or even increase — the size of data with little repetition.
Common mistakes with Run-Length Encoding
- M21. "Lossless compression always produces a smaller file, and RLE works equally well on all data." Why it fails Lossless methods exploit patterns. Where there is no pattern there is nothing to exploit, and RLE in particular stores two items for every run — so data with no repetition gets bigger. Correct model RLE is most effective on data containing long runs of identical values, such as a two-colour logo with large flat areas. On a detailed photograph the runs are one pixel long and the encoded form can exceed the original. Exam-safe "Run-length encoding reduces file size only when the data contains long runs of repeated values; with little repetition each single value is stored as a pair, so the file may not shrink and could grow." Test yourselfHideQ. Apply RLE to ABCDEF and count the items.A. 1A 1B 1C 1D 1E 1F — 6 pairs = 12 items, against 6 originally. It has doubled.