These are two specific algorithms for achieving lossless compression, each suited to different types of data.
Run Length Encoding (RLE)
Run Length Encoding is one of the simplest compression algorithms. It works by replacing a run of consecutive identical values with a count and a single copy of the value.
Definition
Run Length Encoding (RLE) stores consecutive occurrences of the same data value as a count of how many times it repeats, followed by a single copy of the value.
Worked Example
Worked Example: Compressing with RLE
Original string: AAAAAABBBCCCCCCCCDD
Step 1: Identify runs of identical characters
• A appears 6 times consecutively
• B appears 3 times consecutively
• C appears 8 times consecutively
• D appears 2 times consecutively
Step 2: Write each run as its count followed by the value
6A 3B 8C 2D
Result:
• Original: 19 characters
• Compressed: 8 characters (6A3B8C2D)
• Saving: 11 characters, a 58% reduction
When RLE fails:
Original: ABCDEFGH (no repetition)
"Compressed": 1A1B1C1D1E1F1G1H
Result: 16 characters, twice the size of the original
Original string: AAAAAABBBCCCCCCCCDD
Step 1: Identify runs of identical characters
• A appears 6 times consecutively
• B appears 3 times consecutively
• C appears 8 times consecutively
• D appears 2 times consecutively
Step 2: Write each run as its count followed by the value
6A 3B 8C 2D
Result:
• Original: 19 characters
• Compressed: 8 characters (6A3B8C2D)
• Saving: 11 characters, a 58% reduction
When RLE fails:
Original: ABCDEFGH (no repetition)
"Compressed": 1A1B1C1D1E1F1G1H
Result: 16 characters, twice the size of the original
Key Point
RLE is effective when:
• Data has long runs of identical values
• Simple graphics with large areas of same colour
• Fax transmissions (long runs of white/black)
RLE is ineffective when:
• Data is highly varied with little repetition
• Photographs (pixels rarely repeat exactly)
• Encrypted or random data
• Data has long runs of identical values
• Simple graphics with large areas of same colour
• Fax transmissions (long runs of white/black)
RLE is ineffective when:
• Data is highly varied with little repetition
• Photographs (pixels rarely repeat exactly)
• Encrypted or random data
Dictionary Encoding
Dictionary encoding identifies frequently occurring sequences and replaces them with shorter codes, maintaining a dictionary that maps codes to their original values.
Definition
Dictionary encoding replaces frequently occurring data sequences with shorter codes. A dictionary mapping codes to original sequences is stored alongside the compressed data.
Worked Example
Worked Example: Dictionary Compression
Original text:
"the cat sat on the mat and the rat ate the fat"
Step 1: Identify frequently occurring patterns
• "the " appears 4 times
• "at" appears 6 times (in cat, sat, mat, rat, ate and fat)
Step 2: Build dictionary
Dictionary:
• Code 1 = "the "
• Code 2 = "at"
Step 3: Replace occurrences
"1c2 s2 on 1m2 and 1r2 2e 1f2"
Result:
• Original: 46 characters
• Compressed text: 28 characters, plus the dictionary, which has to be stored with it
• The saving grows with the length of the text, because the dictionary is stored once however many times its entries are used
Original text:
"the cat sat on the mat and the rat ate the fat"
Step 1: Identify frequently occurring patterns
• "the " appears 4 times
• "at" appears 6 times (in cat, sat, mat, rat, ate and fat)
Step 2: Build dictionary
Dictionary:
• Code 1 = "the "
• Code 2 = "at"
Step 3: Replace occurrences
"1c2 s2 on 1m2 and 1r2 2e 1f2"
Result:
• Original: 46 characters
• Compressed text: 28 characters, plus the dictionary, which has to be stored with it
• The saving grows with the length of the text, because the dictionary is stored once however many times its entries are used
Exam Tip
Dictionary vs RLE: Dictionary encoding works better for text with repeating words/phrases. RLE works better for data with repeating individual values. Real compression algorithms (like ZIP) often combine multiple techniques.