runlength

Runlength, in data processing, refers to the number of consecutive occurrences of the same value in a sequence. A run is a maximal subsequence of identical items, such as a string of equal bits or characters. Run-length encoding (RLE) is a simple compression technique that replaces each run with a representation of its length and the value shared by the run.

In a typical RLE scheme, an input sequence is scanned from start to finish, counting how many times the current symbol repeats before a new symbol appears. This run is then encoded as a pair (length, value). For example, the sequence A A A B B C C C C can be encoded as (3, A), (2, B), (4, C). Decoding reverses the process by expanding each pair back into a run of the indicated length and symbol.

RLE is most effective on data with lots of repeated values, such as simple graphics, monochrome bitmaps, or data with large flat regions. It is widely used in older or simpler image formats and in certain communication protocols (for example, some fax and archival formats). However, RLE performs poorly on data with high entropy or many short runs, and it can even increase size in those cases. Many implementations mitigate this with variants such as limiting run lengths, using escape codes to switch between run and literal modes, or applying RLE as a preprocessing step before more advanced compression.

Variants and practical considerations include handling long runs that exceed a maximum count, choosing whether to store the value first or the length first, and deciding how to mark the end of data.