Run-Length Encoding (Warmup)

Before Huffman, the simplest compression: run-length encoding (RLE). Replace a run of repeated bytes with (count, byte):

Input:  AAAAABBBCCD
Output: 5A 3B 2C 1D

Compression ratio depends entirely on input. Long uniform runs compress massively (e.g., images with large solid-color regions). Random data EXPANDS (each byte becomes 2 — count + value).

Practical encoding tricks:

• Escape byte for non-runs: <byte> <byte> (literal run of 1)
• Variable-length counts: 1 byte for counts up to 255; then a longer encoding
• Specialized escape codes: PCX uses high 2 bits as marker

RLE is used by:

• BMP images (4-bit and 8-bit run-length)
• TGA images
• PCX images
• FAX modem encoding (Group 3, Group 4)
• The run-length step inside bzip2 (after BWT)

Modern compressors don't use RLE alone — but it's an excellent intuition for "exploit redundancy" before getting to Huffman or LZ77.