Run Length Encoding

Source coding aims to remove redundancy from data before transmission. Run Length Encoding (RLE) is one of the simplest lossless compression schemes that exploits the repetition of identical symbols in a sequence. It is foundational to understanding data compression and appears in GATE problems related to source coding efficiency.

Core Concept Explanation

A run is defined as a maximal sequence of consecutive identical symbols. RLE replaces each run with a pair: the length of the run and the symbol itself. For example, the binary string 0000011100 has three runs: five 0s, three 1s, and two 0s, giving the RLE representation (5,0)(3,1)(2,0).

The fundamental advantage of RLE is that it is completely lossless. The original sequence can be reconstructed exactly from the encoded pairs without any ambiguity. This makes it suitable for text, binary images, and any source where long repetitive runs are expected.

RLE is not always efficient. If a source has very few repetitions, for example alternating symbols like ABABAB, the encoded output may actually be longer than the original. The compression ratio depends directly on the statistical structure of the source, specifically on the average run length.

In practice RLE is used as a pre-processing step in more complex schemes. The ITU T.4 fax standard uses RLE on binary scanned lines before Huffman coding. JPEG and BMP formats also use RLE internally. Understanding RLE helps build intuition for why statistical redundancy, not randomness, is what compression targets.

Mathematical Expression

Let a source sequence of length N contain R distinct runs with average run length L. Then the number of encoded symbols is 2R (since each run produces one count and one symbol). The compression ratio CR is defined as the ratio of original sequence length to encoded output length:

CR = N / (2R)

Since the average run length L = N / R, this gives CR = L / 2. For efficient compression, the average run length must exceed 2. If L = 1 (every symbol is different from its neighbor), the output is twice the size of the input, representing worst-case expansion.

For binary sources, only the run lengths need to be transmitted if both parties know that runs alternate between 0 and 1, starting with 0. This reduces the pair to just the count, halving the encoded size further. This is the principle used in fax transmission standards.

Practical Understanding

RLE performs best on sources with high spatial or temporal correlation, meaning neighboring symbols tend to be the same. Scanned documents, satellite images with large uniform regions, and binary bitmaps are classic examples. For such sources, run lengths can easily be 10 to 100 symbols, giving compression ratios of 5 to 50.

RLE performs poorly on natural language text or random data because characters rarely repeat consecutively. Modern compressors like ZIP and LZ77 extend the RLE idea by finding repeated patterns that are not necessarily adjacent, using a dictionary-based approach. RLE can thus be viewed as the simplest member of the family of dictionary and pattern-substitution coders.

Given:
A binary sequence: 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0
Total symbols N = 15

Why this formula applies:
RLE encodes each run as a (count, symbol) pair.
Runs: (5,0), (3,1), (2,0), (1,1), (4,0) → R = 5 runs

Formula:
CR = N / (2R)

Substitution:
CR = 15 / (2 × 5) = 15 / 10

Calculation:
CR = 1.5

Final Answer:
Compression ratio = 1.5 (output is 1.5x smaller than input)

Exam Tip: In GATE, if a sequence is given with alternating symbols (like 010101), RLE expansion occurs (CR < 1). Always check average run length before claiming compression benefit.

Key Properties of RLE

• RLE is lossless: original data is perfectly reconstructed from encoded pairs.
• Compression is beneficial only when average run length L exceeds 2.
• For binary sequences with known alternating structure, only run counts need transmission.
• CR = N / (2R) = L / 2 where L is average run length and R is total number of runs.
• RLE has O(N) time complexity for both encoding and decoding.
• It is insensitive to the alphabet size but highly sensitive to source correlation structure.

Quick Revision

• RLE replaces each run of repeated symbols with a (count, symbol) pair.
• Compression ratio CR = N / (2R) = L / 2, where L is average run length.
• Efficient only when L > 2; for alternating symbols, output is larger than input.
• Used in fax standards (ITU T.4), BMP, and as preprocessing in JPEG.
• Completely lossless: no information is lost during encoding.
• GATE trap: do not assume RLE always compresses; check structure of the source first.
• For binary alternate-known sequences, only counts are sent, improving efficiency further.