Run length encoding and dictionary coding for lossless compression

Run length encoding and dictionary coding for lossless compression.

1.3.1 Compression, Encryption and Hashing

Compression, Encryption and Hashing — Note 2 of 4

Candidates need to understand how run-length encoding can reduce the size of a file for example with a text file or image. Candidates should understand how dictionary coding works by substituting entries with a unique code. Candidates should have practical experience of using these algorithms with small example files.

What you need to know

Run length encoding and dictionary coding are two lossless compression methods. Both work by finding repetition in the data and storing it more efficiently, so the original can be rebuilt exactly.

What to know

Key terms

Run length encodingRLE: Replaces a run of repeated values with a single copy of the value and a count of how many times it repeats.
RLE works well for data with long runs of the same value, e.g. simple images with large blocks of one colour.
RLE can make a file LARGER if there are few repeated values, because each single value now needs a count too.
Dictionary coding: Frequently occurring words or patterns are replaced by shorter codes, and a dictionary that maps codes to the original patterns is stored with the file.
Dictionary coding works well for text with many repeated words. The dictionary itself takes up space, so it is less effective on short files.

Exam technique

Tip:You should be able to apply both methods to a small example and work out the compressed result.

Example:RLE on the row WWWWWBBBWW gives 5W 3B 2W (or W5B3W2), reducing 10 values to 3 value-count pairs.

Code examples

Run length encoding in Python

python

def rle(data):
    result = []
    count = 1
    for i in range(1, len(data) + 1):
        if i < len(data) and data[i] == data[i - 1]:
            count = count + 1
        else:
            result.append(str(count) + data[i - 1])
            count = 1
    return " ".join(result)

print(rle("WWWWWBBBWW"))   # 5W 3B 2W

Dictionary coding example

text

Text:        the cat sat on the mat the end
Dictionary:  1 = the   2 = cat   3 = sat   4 = on   5 = mat   6 = end
Encoded:     1 2 3 4 1 5 1 6

← Previous noteLossy vs lossless compression1.3.1 Compression, Encryption and Hashing Next note →Symmetric and asymmetric encryption1.3.1 Compression, Encryption and Hashing

Back to Compression, Encryption and Hashing