Run-length encoding

Run-length encoding (RLE) is a very simple form of data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

This is most useful on data that contains many such runs; for example, simple graphic images such as icons and line drawings.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

For example, consider a screen containing plain black text on a solid white background.

Related Topics:
Black - White

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

There will be many long runs of white pixels in the blank space, and many short runs of black pixels within the text.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Let us take a hypothetical single scan line, with B representing a black pixel and W representing white:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

If we apply a simple run-length code to the above hypothetical scan line, we get the following:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: 12WB12W3B24WB14W

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Interpret this as twelve W's, one B, twelve W's, three B's, etc.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The run-length code represents the original 67 characters in only 16.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Of course, the actual format used for the storage of images is generally binary rather than ASCII characters like this, but the principle remains the same.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Even binary data files can be compressed with this method; file format specifications often dictate repeated bytes in files as padding space.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

However, newer compression systems often use deflation or other LZ77-based algorithms, which can take advantage of runs of strings of characters (such as BWWBWWBWWBWW).

Related Topics:
Deflation - LZ77

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Common formats for run-length encoded data include PackBits, PCX and ILBM.

Related Topics:
PackBits - PCX - ILBM

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Run-length encoding performs lossless data compression and is well suited to palette-based iconic images. It does not work well at all on continuous-tone images such as photographs, although JPEG uses it quite effectively on the coefficients that remain after transforming and quantizing image blocks.

Related Topics:
Lossless data compression - Palette - JPEG - Quantizing

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Data that has long sequential runs of bytes (such as lower-quality sound samples) can be RLE compressed after Delta encoding is applied to it.

Related Topics:
Sound samples - Delta encoding

~ ~ ~ ~ ~ ~ ~ ~ ~ ~