Run-length encoding (RLE) is a form of lossless data compression in which runs of data (consecutive occurrences of the same data value) are stored as a single occurrence of that data value and a count of its consecutive occurrences, rather than as the original run. For example, a sequence of "green green green green green" in an image built up from colored dots could be shortened to "green x 5".

Run-length encoding is most efficient on data that contains many such runs, for example, simple graphic images such as icons, line drawings, games, and animations. For files that do not have many runs, encoding them with RLE could increase the file size.

RLE may also refer to particular image formats that use the encoding. RLE is an early graphics file format supported by CompuServe for compressing black and white images, that was widely supplanted by their later Graphics Interchange Format (GIF). It is also the name of a little-used image format in Windows 3.x that is saved with the file extension <code>rle</code>, consisting of a run-length encoded bitmap; it was used as the format for the Windows 3.x startup screen.

History and applications

Run-length encoding (RLE) schemes were employed in the transmission of analog television signals as far back as 1967. RLE is particularly well suited to palette-based bitmap images (which use relatively few colors) such as computer icons, and was a popular image compression method on early online services such as CompuServe before the advent of more sophisticated formats such as GIF.

Decoding algorithm

The decoding process involves reconstructing the original data from the encoded format by repeating characters according to their counts. The steps are as follows:

  1. Traverse the encoded data.
  2. For each count-character pair, repeat the character count times.
  3. Append these characters to the result string.

Python implementation

<syntaxhighlight lang="python">

def rle_decode(iterable, *, length_first=True):

"""

>>> "".join(rle_decode("4A3B2C1D2A"))

'AAAABBBCCDAA'

>>> "".join(rle_decode("A4B3C2D1A2", length_first=False))

'AAAABBBCCDAA'

"""

return chain.from_iterable(

repeat(b, int(a)) if length_first else repeat(a, int(b))

for a, b in batched(iterable, 2)

)

</syntaxhighlight>

</references>

  • Run-length encoding implemented in different programming languages (on Rosetta Code)
  • Single Header Run-Length Encoding Library smallest possible implementation (about 20 SLoC) in ANSI C. FOSS, compatible with Truevision TGA, supports 8, 16, 24 and 32 bit elements too.