3.3.8 - Run length encoding
Use frequency/value pairs to describe repeated consecutive data, then encode and decode bitmap rows without losing their pixel positions.
Frequency and value pairs
Run length encoding describes each consecutive run of the same value with a count and that value.
Run length encoding
A lossless representation that replaces a run of repeated data with a frequency/value pair: how many consecutive items occur, followed by what the item is.
For AAAAABBCC, the runs are five As, two Bs and two Cs. Using (frequency, value) order, the pairs are (5, A), (2, B), (2, C). The count is the length of this run, not the total number of that character anywhere in the file. ABBA therefore becomes (1, A), (2, B), (1, A); the separated As are different runs.
Decoding reverses the process. The pair (4, X) outputs XXXX. Append the decoded runs in their original order to recover the data exactly. The encoder and decoder must agree on the pair format and how counts are stored.
Long runs can reduce the representation size. Highly alternating data may instead need many pairs, each with count overhead, and can become larger. Merely calling a method “compression” does not guarantee a saving for every file. A bitmap with large areas of the same colour often offers longer runs than a noisy image.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account