= Run-length encoding
{wiki}
= RLE
{c}
{synonym}
<Run-length encoding> replaces each maximal consecutive group of equal values, called a run, by its value and length. Decoding repeats each value the specified number of times. It is <lossless source coding>: no values are discarded. For a <binary string>, successive maximal runs alternate between 0 and 1, so storing the first <bit> and all run lengths is enough.
Take this $8\times8$ <raster image>, with 0 black and 1 white, read left to right across each row and then top to bottom:
``
00000000
00001111
11110000
00001111
11110000
00001111
11110000
00000000
``
Reading the whole image as one 64-<bit> <binary string> gives exactly seven runs:
$$
(\text{value},\text{length})=(0,12),(1,8),(0,8),(1,8),(0,8),(1,8),(0,12).
$$
The lengths sum to $12+8+8+8+8+8+12=64$. Repeating the alternating values for these lengths and splitting after every eighth <pixel> reconstructs every displayed row exactly.
Here is a complete toy <file format>. Its <file header> is an eight-<bit> unsigned width, an eight-<bit> unsigned height, then a one-<bit> mode: 0 means raw <pixels>, 1 means <run-length encoding>. Fields are written most significant <bit> first; this profile accepts only width and height 8, so both decoders know to stop at 64 <pixels>. Raw mode contains 64 <bits>. <RLE> mode contains the initial <bit>, followed by seven-<bit> unsigned run lengths in the range 1 to 64. Zero and lengths above 64 are invalid; a decoder rejects a run that would exceed the remaining <pixel> count. It stops when the decoded lengths sum to 64, so no run-count field or end marker is needed.
For this image, the complete <RLE> serialization is:
``
00001000 00001000 1 | 0 | 0001100 0001000 0001000 0001000 0001000 0001000 0001100
``
Spaces and vertical bars are explanatory separators, not stored characters. The seven-<bit> fields directly store the lengths; 64 would be `1000000`. The payload costs $1+7\cdot7=50$ <bits>, versus 64 raw <bits>. The 17-<bit> <file header> has the same size in either mode, giving complete sizes of 67 versus 81 <bits>. If packed into eight-<bit> units, append zero padding only at the end: the sizes become 72 versus 88 <bits>. These are sizes of this toy representation, not sizes of <PNG> files.
The field design matters. Restarting <RLE> on every row costs eight initial <bits> plus four <bits> per run when lengths are stored directly: three <bits> represent only 0 through 7, whereas a row can have length 8. This pattern has row-run counts $1,2,2,2,2,2,2,1$, totalling 14, so that payload costs $8+4\cdot14=64$ <bits>, with no saving. Storing length minus one would instead fit lengths 1 through 8 into three <bits>, but is a different declared <file format>. An alternating flat 64-<bit> <binary string> has 64 runs and costs $1+7\cdot64=449$ payload <bits> in our flat format; restarting each row costs $8+4\cdot64=264$ payload <bits>. A one-run image costs only eight payload <bits>. These extremes explain when <RLE> is useful: long uninterrupted regions make short instructions, while frequent changes make instructions expensive.
<Prefix codes> of unequal lengths can replace fixed-width run lengths, provided the decoder knows the code and any necessary code description is counted. <Run-length encoding> names a technique, not one universal serialization. For a real implementation, Microsoft's bitmap documentation specifies `BI_RLE8` with count and value fields plus special commands, rather than our initial-<bit> convention.https://learn.microsoft.com/en-us/windows/win32/gdi/bitmap-compression[Microsoft, Bitmap Compression, BI_RLE8 encoded and absolute modes]{ref}
\Image[/run-length-image-compression.png]
{title=Seven runs serialize an 8 by 8 binary image and reconstruct every pixel exactly}
Back to article page
