Run Length Encoding & Dictionary Coding

Overview

Compression is the process of reducing the size of data files, making storage and transmission more efficient. Two common compression techniques are Run-Length Encoding (RLE) and Dictionary Coding. These algorithms reduce file sizes in different ways and are often used for specific types of data. Understanding how these techniques work can help you recognise which is best suited to a given file type and application.

Run-Length Encoding (RLE)

What is Run-Length Encoding?

• Run-length encoding (RLE) is a simple compression algorithm that reduces file size by identifying sequences of repeated data (runs) and encoding them as a single data value and a count.
• This technique is effective when there are long sequences of repeated values, such as in simple images with large areas of the same color or text files with repeating characters.

How RLE Works

• RLE identifies consecutive identical elements in the data, known as "runs."
• Each run is stored as a single value and a count that represents how many times the value repeats.

Applications of RLE

• Images: RLE is commonly used in bitmap images where pixels of the same colour are grouped together. For example, an image with a large area of white pixels can be compressed by representing the pixel colour and the count of pixels in each sequence.
• Text Files: RLE can be applied to text with repeating characters, though it's less effective for natural language text with fewer repetitions.

Benefits and Drawbacks of RLE

Benefits:

• Simple and Fast: RLE is easy to implement and efficient for encoding data with long runs of the same value.
• Good for Specific Data: RLE works well for simple images or data with many repeating values.

Drawbacks:

• Limited Usefulness: If there are few or no repeating values, RLE may increase file size instead of reducing it.
• Not Effective for Complex Data: RLE doesn't compress well for data with varied or non-repetitive content.

RLE Example in Images

Dictionary Coding

What is Dictionary Coding?

• Dictionary Coding is a compression technique that reduces file size by replacing repeated data patterns with shorter, unique codes.
• A dictionary is created where each unique pattern (e.g., a word, phrase, or symbol) in the data is stored with a code. The file is then rewritten using these shorter codes instead of the full patterns.

How Dictionary Coding Works

• Step 1: Analyse the data to identify unique patterns (such as words in a text).
• Step 2: Assign each unique pattern a code and store these in a dictionary.
• Step 3: Replace each occurrence of the pattern in the data with its corresponding code.

Applications of Dictionary Coding

• Text Files: Dictionary coding is commonly used for text compression, especially when there are recurring words or phrases.
• File Compression Formats: Dictionary coding forms the basis of popular compression formats like ZIP and LZW (used in GIF images). These formats replace patterns of bytes with shorter codes to achieve compression.

Benefits and Drawbacks of Dictionary Coding

Benefits:

• Effective for Repeated Patterns: Ideal for data with recurring words or sequences, such as text files or certain images.
• Adaptable: Dictionary coding can be dynamically built and optimised during compression, making it versatile.

Drawbacks:

• Memory Overhead: Storing the dictionary adds memory usage, especially for data with many unique patterns.
• Initial Complexity: Dictionary coding is more complex to implement than RLE, as it requires building and managing a dictionary.

Dictionary Coding Example with LZW (Simplified)

Comparison Table

Aspect	Run-Length Encoding (RLE)	Dictionary Coding
Compression Method	Encodes repeating sequences as value + count	Replaces patterns with dictionary-based codes
Best For	Simple images or text with long repetitions	Text files or data with recurring patterns
Data Structure	No additional data structure required	Requires a dictionary
Efficiency	High for simple, repetitive data	High for complex data with repeated patterns
Drawbacks	Ineffective for varied data	Increased memory usage for large dictionaries

Choosing Between RLE and Dictionary Coding

Simple Images (e.g., Monochrome Bitmaps)

• Recommended Compression: Run-Length Encoding (RLE)
• Reason: Large blocks of uniform colour make RLE highly effective for simple image formats.

Text Files with Repeated Words (e.g., Documents or Logs)

• Recommended Compression: Dictionary Coding
• Reason: Repeated words and phrases are best compressed by replacing them with shorter codes in a dictionary.

High-Resolution Images (e.g., Photographs)

• Recommended Compression: Neither RLE nor Dictionary Coding alone
• Reason: High-resolution images have complex colour patterns and do not typically benefit from either RLE or dictionary-based compression. Instead, other image compression methods like JPEG are more suitable.