🔁 Run-Length Coding (RLE)

🔁 Run-Length Coding (RLE)

B.Sc. Computer Science Honours – Data Compression

📚 1. Introduction to Run-Length Coding

Run-Length Coding (RLC), commonly called Run-Length Encoding (RLE), is a simple lossless data compression technique.

The basic idea is to replace a sequence of consecutive identical symbols by a single symbol together with the number of times that symbol occurs consecutively.

Example:

Original:

AAAAAABBBBCCCCC

RLE representation:

6A4B5C

Instead of storing every repeated symbol individually, RLE stores the run length and the corresponding symbol.

⌨️ 2. Interactive Run-Length Encoder

Enter Data

Try These Examples

AAAAAABBBBCCCCC

AAABCCCCDDDDDD

111111100001111

🎯 3. Encoded Output

Enter data and click Encode.

🔎 4. Step-by-Step Encoding

The individual runs will appear here.

📈 5. Compression Statistics

📖 6. Detailed Theory for B.Sc. Computer Science Honours

6.1 What is a Run?

A run is a consecutive sequence of identical symbols.

For example:

AAAABBBCCCCCCDD

contains the following runs:

AAAA → 4A
BBB → 3B
CCCCCC → 6C
DD → 2D

Therefore, the RLE representation is:

4A3B6C2D

6.2 Basic Principle

Suppose a data sequence contains:

XXXXXXYYYYZZZZZZZ

Instead of storing every character separately, RLE stores:

6X2Y7Z

The two important components are:

• Run length: Number of consecutive occurrences.
• Symbol: The repeated character or data value.

6.3 Mathematical Representation

A sequence can be represented as:

S = s₁s₂s₃...sₙ

If several consecutive symbols are identical:

sᵢ = sᵢ₊₁ = ... = sᵢ₊ₖ

then they can be represented by:

(k + 1, sᵢ)

where k + 1 is the run length and sᵢ is the repeated symbol.

6.4 RLE Encoding Algorithm

1. Read the input sequence from left to right.
2. Take the first symbol as the current symbol.
3. Initialize the run count to 1.
4. Compare the next symbol with the current symbol.
5. If they are equal, increase the count.
6. If they are different, output the count and current symbol.
7. Make the new symbol the current symbol.
8. Reset the count to 1.
9. Continue until the end of the input.
10. Output the final run.

6.5 RLE Decoding

Decoding reverses the encoding process.

For example:

5A3B4C

is decoded as:

AAAAABBBCCCC

The decoder reads the run length and repeats the corresponding symbol that many times.

6.6 Time Complexity

For an input containing n symbols, a simple RLE encoder examines each symbol once.

Time Complexity = O(n)

The basic algorithm therefore has linear time complexity.

The additional working space is generally:

Auxiliary Space = O(1)

excluding the space required to store the encoded output.

6.7 When Does RLE Work Well?

RLE is particularly effective when the input contains long runs of identical values.

For example:

AAAAAAAAAAAAAAAAAAAA

can be represented compactly as:

20A

This produces a significant reduction in the amount of data.

6.8 When Does RLE Perform Poorly?

If consecutive symbols rarely repeat, RLE may provide little or no compression and can even increase the data size.

For example:

ABCDEFGH

could become:

1A1B1C1D1E1F1G1H

The encoded representation is clearly longer than the original.

Important: RLE is data-dependent. Its effectiveness depends on the number and length of repeated runs in the input.

6.9 RLE for Binary Images

Run-Length Coding is commonly explained using binary images. Consider one row of pixels:

111111000001111111

This can be represented as:

6(1), 5(0), 7(1)

This is useful because image regions often contain long sequences of the same pixel value.

6.10 RLE and Bitmap Images

RLE can be useful for simple images containing large areas of the same colour or intensity.

For example, a monochrome image containing large white backgrounds and black regions can contain long sequences of identical pixel values. These sequences can be represented using run lengths.

6.11 RLE in Data Compression Systems

RLE can be used as a standalone compression method or as one stage of a larger compression pipeline.

It may be combined with other techniques such as:

• Huffman coding
• Arithmetic coding
• Dictionary-based compression
• Entropy coding

6.12 Advantages of Run-Length Coding

• Very simple to understand and implement.
• Linear-time encoding.
• Linear-time decoding.
• Lossless compression.
• Requires relatively little computational processing.
• Effective for data containing long repeated sequences.
• Useful for simple bitmap and binary data.

6.13 Limitations of Run-Length Coding

• Not effective for highly random data.
• May increase the size of data with few repetitions.
• Compression ratio depends strongly on the input characteristics.
• Very short runs may create considerable overhead.
• It does not exploit complex statistical relationships between symbols.

6.14 RLE vs Arithmetic Coding

Feature	Run-Length Coding	Arithmetic Coding
Basic idea	Represents repeated symbols using counts.	Represents a sequence using a fractional interval.
Primary requirement	Repeated consecutive symbols.	Probability model.
Complexity	Simple.	More mathematically involved.
Best suited for	Data containing long runs.	Data with useful statistical probability models.
Type	Lossless.	Lossless.

6.15 Compression Ratio

A simple compression ratio can be calculated as:

Compression Ratio = Original Size / Compressed Size

For example, if the original representation requires 100 units and the compressed representation requires 50 units:

Compression Ratio = 100 / 50 = 2:1

A larger ratio indicates greater reduction in representation size, although the actual storage cost of counts, delimiters and symbol representations must be considered in a real implementation.

6.16 Important Examination Points

• RLE stands for Run-Length Encoding.
• It is a lossless compression technique.
• A run consists of consecutive identical symbols.
• The run is represented using a count and symbol.
• Encoding and decoding are computationally simple.
• Basic encoding has O(n) time complexity.
• RLE performs well when long repeated runs exist.
• RLE may increase the size of data containing many unique consecutive symbols.
• It is useful in some bitmap, binary and structured data compression applications.

🧠 7. Concept Summary

Repeated Symbols → Count the Run → Store Count + Symbol

Example:

AAAAAAAAABBBBCCC

becomes:

9A4B3C

Thus, Run-Length Coding reduces redundancy by representing consecutive identical symbols using their run length and symbol.

CREATED BY BIJAN KRISHNA PAUL B.Sc. Computer Science Honours • Data Compression • Run-Length Coding

```