RLE
This article was accepted into the corpus but its outbound wikilinks were never NER-processed — typical at the deepest BFS hop or when the run's entity cap was reached. No expansion funnel to show.
| RLE | |
|---|---|
 | |
| Name | RLE |
| Caption | Run-length encoding example |
| Type | Lossless data compression |
RLE
RLE is a lossless data compression technique that represents consecutive repeated values as a single value and a count. It is widely used in contexts ranging from early Punch card storage and Fax machines to modern TIFF and BMP image formats, and has influenced algorithms in Huffman coding, Lempel–Ziv families, and JPEG pre-processing. Implementations appear in software from companies such as Microsoft and Adobe Systems, in hardware in devices from Intel and ARM Holdings, and in standards developed by organizations including ISO and the ITU.
Introduction
RLE encodes runs of identical symbols by storing a symbol paired with its run length, reducing redundancy when input contains long homogeneous segments. Early practical uses include magnetic storage workflows at IBM and teleprinter facsimile standards developed by the International Telecommunication Union for Group 3 and Group 4 Fax protocols. RLE interacts with statistical compressors like Arithmetic coding or Huffman coding when used as a preprocessor or postprocessor in systems such as ZIP and PNG.
Principles and Algorithms
The basic principle maps sequences like AAAAA to a pair (A,5) or a byte-stuffed representation; encoders must choose representations that avoid ambiguity with data bytes. Common algorithms include simple byte-level RLE used in BMP and bit-level runs used in raster formats for Fax, with run-lengths often constrained by fixed-size counters. Encoders must handle edge cases such as runs exceeding counter limits, non-repeating symbols, and escape values; strategies include run splitting, sentinel bytes, and length-prefix schemes similar to those in C++'s std::basic_filebuf or POSIX stream utilities. Decoders reverse the process deterministically, enabling lossless reconstruction compatible with error-detecting schemes like CRC32.
Variants and Extensions
Many variants extend base RLE for improved efficiency or broader applicability. PackBits (used by Apple and TIFF) uses a signed count byte and literal copying; PackBits-like schemes influenced run-length approaches in Mac OS imaging systems. Delta-RLE encodes differences between adjacent values before run encoding, used in telemetry systems by organizations such as NASA. Burrows–Wheeler Transform (BWT) often precedes RLE in compressors like bzip2 to cluster symbols into longer runs, while Move-to-Front coding and Run-Length Golomb–Rice combinations are used in specialized encoders in projects by Free Software Foundation contributors. RLE is also adapted to two-dimensional data in techniques such as CCITT Group 4 for monochrome scanning and in tile-based map formats by companies like Esri.
Applications
RLE finds use across many domains: bitmap image formats (BMP, TIFF, PCX), icon and cursor graphics in Microsoft Windows and X Window System resources, and simple video codecs and frame delta encodings used in early QuickTime and AVI implementations. In printing and facsimile, ITU standards like those from the International Telecommunication Union rely on run-length schemes for line-by-line encoding. In gaming, sprite sheets and texture atlases from studios using Unity (game engine) or Unreal Engine sometimes use RLE for resource packing; embedded systems from vendors such as Texas Instruments and STMicroelectronics use RLE for ROM image compression. RLE also supports archival formats and memory-efficient representations in projects maintained by Apache Software Foundation and GNU Project contributors.
Performance and Complexity
RLE's performance depends on data redundancy: worst-case expansion occurs when input lacks runs, leading to larger output than input unless adaptive schemes are used; best-case compression is linear with run-length. Computational complexity is O(n) time for both encoding and decoding, with O(1) additional space for streaming implementations, though buffer-based approaches trade space for faster I/O as seen in libraries from Google and Mozilla. Compression ratio and throughput vary widely by implementation and data type; hardware-accelerated RLE in GPUs from NVIDIA and AMD offers high throughput for graphics workloads, while software decoders in interpreters like Python and Java Virtual Machine target portability.
Implementation Examples
Common code patterns appear across languages and platforms. In C and C++ libraries shipped by GNU Project and Boost (C++) Library contributors, RLE appears as simple loops emitting (value, length) pairs or as tokenized streams with escape markers. In image processing toolchains such as ImageMagick and GraphicsMagick, RLE-based readers and writers handle multiple variants like PackBits and CCITT group encodings. Scripting languages (examples from Perl CPAN modules, Python packages on PyPI, and Node.js npm modules) provide high-level APIs for run-length operations; database systems like SQLite and PostgreSQL sometimes use RLE for index compression in columnar extensions developed by academic groups.
Limitations and Alternatives
RLE is most effective on data with long runs; it performs poorly on high-entropy inputs, where statistical compressors like Huffman coding and Lempel–Ziv–Markov chain algorithm (used in 7-Zip) outperform it. For multidimensional or correlated data, transforms such as Burrows–Wheeler Transform or predictive coding (used in FLAC and JPEG-LS) often yield superior results. Where adaptive, dictionary-based approaches are required, implementations favor LZ77/LZ78 derivatives or hybrid schemes like those in DEFLATE (used by gzip and PNG). Error resilience and random access needs sometimes motivate columnar RLE formats in analytical databases developed by companies such as Facebook and Snowflake.
Category:Data compression methods