Run-length encoding
From Free net encyclopedia
←Older revision | Newer revision→
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. 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 methods such as deflation often use LZ77-based algorithms, a generalization of run-length encoding that 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.
Example
RLE is used in Facsimilie machines. They operate as follows:
RLE recognizes that most documents are white space with brief interruptions for the black typing. So FAX compresses a document by adding a repeat count to the next transition. It may tell the receiver that 100 of the next pixels are white. Another common encoding technique is string compression. This is used for data files. The encoder has a dictionary of strings. It matches the incoming text to the strings in the dictionary and when found, it will send a single number to the receiver which is the index to the string. All known implementations of string compression are adaptive in nature and allow the encoder to create new strings and transmit them to the decoder so the two dictionaries remain the same.
Data that has long sequential runs of bytes (such as lower-quality sound samples) can be RLE compressed after applying a predictive filter such as Delta encoding.
See also
External links
es:Run-length encoding fr:Run-length encoding ko:반복 길이 부호화 it:Run-length encoding nl:Run-length encoding ja:連長圧縮 pl:RLE pt:Codificação Run-length ru:Кодирование длин серий fi:RLE