Run-length encoding

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, relatively simple graphic images such as icons, line drawings, and animations. It is not recommended for use with files that don't have many runs as it could potentially double the file size.

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 the run-length encoding (RLE) datacompression algorithm to the above hypothetical scan line, we get the following:

: 12W1B12W3B24W1B14W

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

While:

: WBWBWBWBWBWBWB

would be:

: 1W1B1W1B1W1B1W1B1W1B1W1B1W1B

The encoding data is quite longer.

The run-length code represents the original 67 characters in only 18. 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 DEFLATE 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 TGA, 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.

Run-length encoding is used in fax machines (combined with other techniques into Modified Huffman coding). It is relatively efficient because most faxed documents are mostly white space, with occasional interruptions of black.

Data that have long sequential runs of bytes (such as lower-quality sound samples) can be RLE compressed after applying a predictive filter such as delta encoding.

Example code

Note: this basic code assumes that the input valid alphabet string onlyimport java.util.regex.Matcher;import java.util.regex.Pattern;

public class RunLengthEncoding {

public String encode(String source) { StringBuffer dest = new StringBuffer(); int counter = -1; for (int i = 0; i < source.length() - 1; ++i) { if (source.charAt(i) != source.charAt(i + 1)) { dest.append(i - counter); dest.append(data.charAt(i)); counter = i; } } dest.append(data.length() - counter - 1); dest.append(data.charAt(data.length() - 1)); return dest.toString(); }

public String decode(String source) { StringBuffer dest = new StringBuffer(); Pattern pattern = Pattern.compile(" [0-9] +| [a-zA-Z] "); Matcher matcher = pattern.matcher(source);

while (matcher.find()) { int number = Integer.parseInt(matcher.group()); matcher.find(); while (number-- != 0) { dest.append(matcher.group()); } } return dest.toString(); }

public static void main(String [] args) { RunLengthEncoding RLE = new RunLengthEncoding(); String example = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"; System.out.println(RLE.encode(example)); System.out.println(RLE.decode("1W1B1W1B1W1B1W1B1W1B1W1B1W1B"));

See also

* Look-and-say sequence
* Golomb coding
* Modified Huffman coding
* Burrows-Wheeler transform
* Run Length Limited
* Bitmap index

External links

* [http://www.binaryessence.com/dct/en000045.htm Run Length Encoding (RLE) and other encoding]


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Run-length encoding — Saltar a navegación, búsqueda La compresión RLE o Run length encoding es una forma muy simple de compresión de datos en la que secuencias de datos con el mismo valor consecutivas son almacenadas como un único valor más su recuento. Esto es más… …   Wikipedia Español

  • Run-length encoding — Die Lauflängenkodierung (engl. Run length encoding, kurz RLE) ist ein sehr einfacher verlustfreier Kompressionsalgorithmus für digitale Daten. Sie ist besonders gut geeignet, Wiederholungen oder Sequenzen von gleichen Werten verkürzt darzustellen …   Deutsch Wikipedia

  • Run-length encoding — Le run length encoding, appelé en français le codage par plages, est un algorithme de compression de données en informatique. Le système s applique essentiellement à des documents scannés en noir et blanc : au lieu de coder un bit par point …   Wikipédia en Français

  • Run-length encoding — La compresión RLE o Run lenght enconding es una forma muy simple de compresión de datos en la que secuencias de datos con el mismo valor son almacenadas como un único valor más su recuento. Esto es más útil en datos que contienen muchas de estas… …   Enciclopedia Universal

  • run-length encoding — noun A simple data compression scheme in which sequences of the same item are replaced by one such item and a count (so for example the text BBBBB is stored as a single B with count of 5) …   Wiktionary

  • Run-length encoding —   Refer instead to Data compression …   International financial encyclopaedia

  • Run length limited — or RLL coding is a technique that is used to store data on recordable media. Specifically, RLL prevents long stretches of repeated bits from causing the signal recorded on media to not change for an excessive period, by modulating the data. RLL… …   Wikipedia

  • Run-length-kodierung — Die Lauflängenkodierung (engl. Run length encoding, kurz RLE) ist ein sehr einfacher verlustfreier Kompressionsalgorithmus für digitale Daten. Sie ist besonders gut geeignet, Wiederholungen oder Sequenzen von gleichen Werten verkürzt darzustellen …   Deutsch Wikipedia

  • Run Length Encoded — Die Lauflängenkodierung (engl. Run length encoding, kurz RLE) ist ein sehr einfacher verlustfreier Kompressionsalgorithmus für digitale Daten. Sie ist besonders gut geeignet, Wiederholungen oder Sequenzen von gleichen Werten verkürzt darzustellen …   Deutsch Wikipedia

  • advanced run-length limited encoding —    Abbreviated ARLL. A technique used to store information on a hard disk that increases the capacity of runlength limited (RLL) storage by more than 25 percent and increases the data transfer rate to 9Mbps.    See also RLL encoding …   Dictionary of networking

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”