Compression

Lossy and lossless; run length encoding and Huffman coding.

F8.9Data representationGCSE20 min

Images, sound and video are large, and storage and networks are not free: a robot's radio can carry only 200 characters in one message. Compression makes files smaller. This lesson meets the two kinds, and two methods, run length encoding and Huffman coding, both written in Python.

Lossy and lossless

• Lossless compression makes a file smaller without losing any data: decompress it and you get back exactly the original. Text, programs and spreadsheets must be compressed this way, because a single changed character matters.
• Lossy compression makes a file much smaller by throwing away detail people are unlikely to notice: the faint colours in a photo (JPEG) or the quietest sounds in music (MP3). The original can never be recovered, but the result is usually good enough.

Run length encoding

Run length encoding (RLE) is lossless. It replaces a run of the same value with the value and how many times it repeats. A row of a black and white picture:

......#####...

becomes 6 light, 5 dark, 3 light: 6.5#3., 6 characters instead of 14.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def rle_encode(text):
    """'......#####...' -> '6.5#3.'"""
    if text == "":
        return ""
    out = ""
    count = 1
    for i in range(1, len(text)):
        if text[i] == text[i - 1]:
            count = count + 1
        else:
            out = out + str(count) + text[i - 1]
            count = 1
    return out + str(count) + text[-1]

def rle_decode(code):
    """'6.5#3.' -> '......#####...'"""
    out = ""
    number = ""
    for ch in code:
        if ch.isdigit():
            number = number + ch
        else:
            out = out + ch * int(number)
            number = ""
    return out

row = "......#####..."
packed = rle_encode(row)
print(packed, len(row), "->", len(packed))
print(rle_decode(packed) == row)

Run this in the simulator

RLE works well when there are long runs, as in simple pictures with big areas of one colour. On data that changes every character, such as .#.#.#, it makes the file bigger: 1.1#1.1#1.1#.

Huffman coding

Huffman coding is lossless too. Instead of giving every character the same number of bits, it gives the most frequent characters the shortest codes. The codes come from a binary tree built from the frequencies, and no code is the start of another, so a string of bits can only be read one way.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def huffman_codes(text):
    """A code for each character: frequent characters get short codes."""
    counts = {}
    for ch in text:
        counts[ch] = counts.get(ch, 0) + 1
    # each item is [total count, [characters]], and the codes grow as items are joined
    items = [[n, [ch]] for ch, n in counts.items()]
    codes = {ch: "" for ch in counts}
    while len(items) > 1:
        items.sort(key=lambda item: item[0])
        low, high = items.pop(0), items.pop(0)
        for ch in low[1]:
            codes[ch] = "0" + codes[ch]
        for ch in high[1]:
            codes[ch] = "1" + codes[ch]
        items.append([low[0] + high[0], low[1] + high[1]])
    return codes

message = "BEEP BEEP BOOP"
codes = huffman_codes(message)
for ch in sorted(codes, key=lambda c: len(codes[c])):
    print(repr(ch), message.count(ch), codes[ch])
bits = sum(len(codes[ch]) for ch in message)
print("Huffman:", bits, "bits; 7-bit ASCII:", len(message) * 7, "bits")

Run this in the simulator

Each step joins the two least frequent groups into one, putting a 0 in front of the codes on one side and a 1 on the other: that is building the tree from the bottom up. E and P, the most common letters, end up with the shortest codes.

sort(key=...) sorts the items by their counts; lambda item: item[0] is a tiny function that picks the count out of each item.

Which to use

Task: compress a row

Write rle_encode(text) and rle_decode(code) yourself. Encode the row ........######....######........ and print it as encoded: <code>, then print original: <n> characters, encoded: <m> characters, and finally decoded matches: True, using your decode function.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

row = "........######....######........"

Challenges

1. Find a row of 20 characters where RLE makes the result longer. What is the worst case?
2. Decode a Huffman-coded message: turn codes round into a dictionary from code to character, and read bits until they match a code.
3. Why would lossy compression be a bad idea for the robot's program files?