Run Length Encoding & Dictionary Coding (OCR A-Level Computer Science): Flashcards

Compression definition

Process of reducing the size of data files

What RLE stands for and does

Run-Length Encoding - compresses repeated data as value + count

How RLE stores a run

As a single data value and a count of repetitions

RLE compression of AAABBBBCCCCCDDD

3A4B5C3D

RLE applications (data types)

Simple images (bitmaps) & text files with repeating chars

RLE benefit

Simple and fast to implement

When RLE is ineffective

When there are few or no repeating values

Dictionary Coding definition

Replaces repeated patterns with shorter unique codes

Dictionary Coding 3 steps

1. Identify patterns 2. Assign codes 3. Replace with codes

Dictionary Coding formats example

ZIP and LZW (used in GIF images)

Dictionary Coding drawback

Memory overhead from storing the dictionary

Data structure needed for RLE

No additional data structure required

Data structure needed for Dictionary Coding

Requires a dictionary

Best compression for simple monochrome bitmaps

RLE - effective for large blocks of uniform colour

Best compression for text with repeated words

Dictionary Coding - replaces words with shorter codes