Run-length encoding (RLE) is a form of lossless data compression that represents consecutive occurrences of the same value as a single run, usually described by the value and a repetition count. It is effective for data containing long stretches of identical symbols, such as simple raster images, binary masks, and repeated values in database columns. RLE is a family of encoding schemes rather than a single standardized file format: different schemes use different count representations, literal blocks, and rules for identifying runs.
Basic principle
A run is a maximal consecutive sequence of equal symbols. For example, the sequence
AAAAABBBCCAAAA
contains four runs and can be represented as:
(A, 5), (B, 3), (C, 2), (A, 4)
Decoding expands each pair into the indicated number of copies of its value, recovering the original sequence exactly.
More formally, a sequence of length can be divided into runs:
where is the value of run , is its positive length, and adjacent run values differ. The lengths satisfy
The symbols being encoded need not be characters. They may be individual bits, bytes, pixels, integers, or larger records. What counts as repetition depends on the unit selected: repeated pixels do not necessarily form repeated bytes when each pixel occupies several bytes.
The notation (A, 5) is explanatory, not a universal storage format. An actual encoding must specify field sizes, count limits, and how a decoder distinguishes counts, values, and control information.
Encoding and decoding
A basic encoding algorithm scans the input from left to right, retaining the current value and its count. When a different value appears, it emits the completed run and starts another. After reaching the end, it emits the final run.
Using abstract pairs, the process can be expressed in pseudocode:
if input is empty:
return
value = first input symbol
count = 1
for each remaining symbol:
if symbol == value:
count = count + 1
else:
emit(value, count)
value = symbol
count = 1
emit(value, count)
A real implementation must also handle the largest representable count. A run that exceeds that limit can be split into several encoded records.
Encoding has time complexity. Decoding into a fully expanded sequence also takes time, because every output symbol must be written. Both operations can use constant auxiliary working memory when input and output are streamed and the count field has a fixed maximum size. Storing the entire encoded or decoded result requires additional space.
Compression effectiveness
RLE benefits from long consecutive repetitions, not merely from the frequent occurrence of particular values. The sequences AAAAABBBBB and ABABABABAB have the same symbol frequencies, but contain two and ten runs respectively.
Suppose each original symbol occupies bits and each encoded run uses bits for its value plus bits for its count. Ignoring headers, padding, and count overflow, the original and encoded sizes are
Compression occurs when
Thus, under this simplified format, the average run length must exceed the overhead associated with storing a count. With an eight-bit value and an eight-bit count, runs average more than two symbols before the representation becomes smaller.
RLE can expand data substantially when runs are short. In a format that always stores one value byte and one count byte per run, input with no identical adjacent bytes roughly doubles in size. Practical formats often reduce this penalty by providing literal blocks.
Main variants
Value–count pairs
The simplest form stores a value and a count for every run. Counts may have fixed width or use a variable-length integer representation. Fixed-width counts simplify parsing but limit run length; variable-length counts accommodate larger runs while making the encoding rules more elaborate.
Counts may represent either the actual run length or an offset from a minimum length. For example, a stored count of zero might mean one occurrence. Such conventions must be defined by the format.
Literal and repeated blocks
Many byte-oriented schemes distinguish between:
- Literal blocks, whose bytes are copied unchanged.
- Repeated blocks, which specify a value and its repetition count.
Control bytes identify the block type and length. This avoids attaching a count to every nonrepeating byte, although literal-block headers still introduce overhead.
PackBits, used as a compression option in TIFF images, is a familiar example. Its packet structure supports literal byte sequences and repeated-byte runs. Other image formats use different control conventions, so their RLE streams are not interchangeable.
Binary run lengths
For binary data, successive runs alternate between zero and one. If the initial value is known or stored separately, the encoded representation can contain only run lengths.
For example:
000011100
can be represented by initial value 0 and lengths 4, 3, 2. Image-oriented schemes may assume that a row begins with a particular color and use a zero-length initial run when necessary.
Runs of a designated value
Some schemes encode only runs of a selected value, commonly zero, while representing other values differently. This is useful when a transformation produces many zero values but few long runs of arbitrary nonzero values.
Applications and related techniques
Images and document transmission
RLE suits images with large uniform regions, including icons, diagrams, monochrome documents, and some screen graphics. Certain BMP variants provide RLE modes for indexed-color images, while TIFF supports PackBits.
Image layout affects effectiveness. Encoding rows independently prevents runs from crossing row boundaries. A different scanning order can produce different run lengths even when the image itself is unchanged.
Facsimile coding methods exploit alternating black and white runs in scanned documents. Their run lengths can be represented with variable-length codes rather than fixed-size integers.
Transform-based compression
RLE is often one stage in a larger compression pipeline. In common JPEG coding processes, quantized AC coefficients are scanned in an order that often groups zeros together. The coding represents runs of zeros together with information about subsequent nonzero coefficients, using special symbols for particular cases. It is not simply RLE applied directly to pixels.
RLE can also be combined with Huffman coding or arithmetic coding to compress the resulting counts and symbols. These methods exploit different forms of redundancy: RLE captures consecutive repetition, while entropy coding assigns representations according to symbol probabilities.
Databases and masks
In a database, a column containing many consecutive equal values can be represented by values and run lengths or run boundaries. Sorting may improve compression by grouping equal values, although sorting changes row order and may require additional structures to preserve relationships.
Some operations can work directly on encoded runs. Counting matching values, for example, may require summing run lengths rather than expanding every record. Benefits depend on the operation and the number of runs.
In image segmentation, binary masks can be stored as alternating background and foreground run lengths. The representation must specify image dimensions, traversal order, and the initial value to reconstruct the mask correctly.
Limitations and implementation concerns
Dependence on local repetition. RLE does not efficiently capture repeated phrases separated by other data, nor general statistical patterns without adjacent equal values.
Limited random access. Locating an arbitrary position may require accumulating run lengths from the beginning. Prefix sums, checkpoints, or a database index can accelerate access at the cost of extra storage.
Sensitivity to representation. Byte-level, pixel-level, and record-level RLE can produce very different results. The definition of equality and the unit being encoded are part of the scheme.
Parsing and resource limits. Decoders must distinguish literal values from control fields and reject malformed or truncated records. Untrusted counts can cause excessive output allocation, integer overflow, or writes beyond an output buffer. Implementations therefore need explicit bounds on both encoded input and expanded output.
Losslessness depends on the whole pipeline. RLE itself preserves its input exactly. When it follows a lossy transformation, as in many JPEG workflows, it preserves the transformed symbols rather than restoring information discarded earlier.