Run-length encoding (RLE) is a lossless compression technique that replaces a sequence of identical consecutive values with the value and the number of times it repeats. It reduces storage requirements when data contains long repeated runs, while allowing the original data to be reconstructed exactly.
How Run-Length Encoding Works
An RLE algorithm reads the data sequentially and counts how many times each value occurs consecutively. It stores each run as a pair containing the run count and the repeated value.
For example, the string:
AAAAABBCCCCCCCC
can be represented as:
5A2B8C
The algorithm follows these steps:
- Read the first value and set its count to one.
- Compare the next value with the current value.
- If they match, increase the count.
- If they differ, output the count-value pair and begin a new run.
- Output the final run when the end of the data is reached.
During decompression, each stored value is repeated according to its count. Therefore, 5A2B8C reconstructs the original string exactly.
| Data pattern | Effect of RLE |
|---|---|
AAAAAAAAAA | Efficient because one long run replaces ten repeated values |
ABABABABAB | Inefficient because every value creates a separate run |
| Simple bitmap with large areas of one colour | Often effective because adjacent pixels may repeat |
| Detailed photograph | Usually ineffective because pixel values change frequently |
A common misconception is that RLE records the total frequency of each value. It does not: it records only consecutive repetitions. Another misconception is that RLE always makes a file smaller. Short runs may increase file size because both a count and a value must be stored.