Run Length Encoding & Dictionary Coding (OCR A-Level Computer Science): Flashcards
📚Flashcards
Practise the cards
15 cards from this deck
ShowHide
Practise the cards
15 cards from this deck
Compression definition
Compression definition
Process of reducing the size of data files
What RLE stands for and does
What RLE stands for and does
Run-Length Encoding - compresses repeated data as value + count
How RLE stores a run
How RLE stores a run
As a single data value and a count of repetitions
RLE compression of AAABBBBCCCCCDDD
RLE compression of AAABBBBCCCCCDDD
3A4B5C3D
RLE applications (data types)
RLE applications (data types)
Simple images (bitmaps) & text files with repeating chars
RLE benefit
RLE benefit
Simple and fast to implement
When RLE is ineffective
When RLE is ineffective
When there are few or no repeating values
Dictionary Coding definition
Dictionary Coding definition
Replaces repeated patterns with shorter unique codes
Dictionary Coding 3 steps
Dictionary Coding 3 steps
- Identify patterns 2. Assign codes 3. Replace with codes
Dictionary Coding formats example
Dictionary Coding formats example
ZIP and LZW (used in GIF images)
Dictionary Coding drawback
Dictionary Coding drawback
Memory overhead from storing the dictionary
Data structure needed for RLE
Data structure needed for RLE
No additional data structure required
Data structure needed for Dictionary Coding
Data structure needed for Dictionary Coding
Requires a dictionary
Best compression for simple monochrome bitmaps
Best compression for simple monochrome bitmaps
RLE - effective for large blocks of uniform colour
Best compression for text with repeated words
Best compression for text with repeated words
Dictionary Coding - replaces words with shorter codes