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.\nThis 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.\nThere will be many long runs of white
pixels in the blank space, and many short runs of black pixels within the text.\nLet 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.\nThe run-length code represents the original 67 characters in only 16.\nOf 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.\nEven binary data files can be compressed with this method; file format specifications often dictate repeated bytes in files as padding space.\nHowever, newer compression systems often use
deflation or other
LZ77-based algorithms, which can take advantage of runs of strings of characters (such as BWWBWWBWWBWW).
Common formats for run-length encoded data include
PackBits,
PCX and
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.
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.
Category:Compression algorithms
