rle

RLE, or Run-Length Encoding, is a simple lossless data compression technique that encodes consecutive runs of the same symbol as a single value and a count. It is most effective for data with long runs of identical elements, such as monochrome images, simple graphics, or fax data, and is less effective for data that is highly random or noisy.

The basic algorithm operates in one pass. A current symbol and its run length are tracked as the input is processed. When the next symbol matches the current one, the run length is incremented; when it differs, the encoded representation of the completed run is emitted and a new run starts. In common implementations the run length uses a fixed width (for example 8 bits), which may require splitting longer runs. Some formats store pairs as (length, value) or use additional literals to represent non-repeated data. Variants exist that optimize for different bit depths or include special codes to distinguish raw data from repeated runs.

Variants and formats include simple RLE, PackBits (a variant used in some image formats), and modified forms used in specific file types. RLE has been employed in various contexts, including early fax standards, monochrome bitmap compression, and as a pre-processing step in more complex codecs.

Applications and limitations: RLE is valued for its simplicity, speed, and low memory requirements, making it suitable for embedded systems and scenarios with long runs. Its disadvantage is a tendency to inflate data when runs are short or the data lacks repetition, and it is not a general-purpose solution for noisy or random data.

Example: the input AAA BBB CC can be encoded as 3A1B2C.