Data Compression: Lossless vs Lossy, with Run-Length Encoding

Beginner35 min3 exercises40 XP

Prerequisites

Python Strings: Create, Access, Slice, and Manipulate Text Python For Loops: Iterate Over Anything with Examples Python Functions: Define, Call, and Return Values

0/3 exercises

Compression rewrites data so it takes fewer bits, which means it fits in less storage and travels across a network faster. Almost every photo, song, video and app download on your phone is compressed. The trick is to spot patterns in the data and describe them more briefly, and the big decision is whether you need every bit back exactly.

What does compression do?

Data compression reduces the size of data, measured as a number of bits, before it is stored or sent. A smaller file leaves more room on your phone and downloads in less time. A four-minute song stored as raw sound samples takes about 40 megabytes; as a typical music file it takes about 4, a tenth of the space. The other half of the job is decompression: turning the compressed version back into data an app can use.

Here is one row of pixels from a pixel-art game, where W is a white pixel and B is a black one:

WWWWWWWWWWBBBBBWWWWW

That is 20 symbols. You could describe the same row as "10 white, then 5 black, then 5 white", or 10W5B5W, which is 7 symbols. Nothing is missing: anyone who knows the rule can rebuild the row exactly. Fewer bits does not necessarily mean less information. The short version says the same thing in less space.

How does run-length encoding work?

The pixel row compresses well because it is full of redundancy: parts of the data repeat or are easy to predict. Ten W's in a row carry little more information than "ten W's".

Run-length encoding (RLE) uses exactly that kind of redundancy. A run is a stretch of the same symbol repeated. RLE replaces each run with its length and its symbol. The encoder below walks through the text one symbol at a time. If the symbol matches the current run, the run gets longer; if not, a new run starts.

A run-length encoder

def rle_encode(text):

"""Return a list of [count, symbol] pairs, one pair per run."""

runs = []

for symbol in text:

if runs and runs[-1][1] == symbol:

runs[-1][0] += 1 # same symbol: the run gets longer

else:

runs.append([1, symbol]) # a new symbol starts a new run

return runs

row = "WWWWWWWWWWBBBBBWWWWW"

runs = rle_encode(row)

print(runs)

print("".join(f"{count}{symbol}" for count, symbol in runs))

Output

[[10, 'W'], [5, 'B'], [5, 'W']]
10W5B5W

Exercise 1: Fix the Run-Length Encoder

Fix the Bug

This rle_encode(text) should return the run-length code of text as a string: the count followed by the symbol, for every run. For 'AAAABBC' it should return '4A2B1C', but it returns '4A2B'. Find the bug and fix it.

The text never contains digits.

def rle_encode(text):

if text == "":

return ""

result = ""

current = text[0]

count = 0

for symbol in text:

if symbol == current:

count += 1

else:

result += f"{count}{current}"

current = symbol

count = 1

return result

How much space does compression save?

To measure a compression algorithm, compare the size before and after. The program below counts characters; each one takes the same number of bits, so the percentage saved is the same either way. It tries RLE on three kinds of data: a row of solid sky, a row across a striped flag, and a checkerboard row where the color changes at every pixel.

Measuring what RLE saves

def compressed_size(text):

runs = rle_encode(text)

return len("".join(f"{count}{symbol}" for count, symbol in runs))

samples = {

"sky": "B" * 50,

"striped flag": "R" * 15 + "W" * 15 + "B" * 15,

"checkerboard": "BW" * 20,

}

for name, data in samples.items():

before = len(data)

after = compressed_size(data)

saved = (before - after) / before * 100

print(f"{name:<13} {before:>3} -> {after:>3} characters ({saved:.0f}% saved)")

Output

sky            50 ->   3 characters  (94% saved)
striped flag   45 ->   9 characters  (80% saved)
checkerboard   40 ->  80 characters  (-100% saved)

Exercise 2: Measure the Saving

Write Code

Write percent_saved(original, compressed). Both arguments are strings, and size is measured in characters. Return the percentage of the original size that compression saved, rounded to 1 decimal place. If the compressed version is bigger, the result is negative.

percent_saved('AAAAAAAAAA', '10A')  ->  70.0

def percent_saved(original, compressed):

# (size before - size after) as a percentage of size before

pass

Does the algorithm matter as much as the data?

How much compression saves depends on two things: how much redundancy the original data has, and which compression algorithm is applied. RLE only notices symbols repeated side by side. Other algorithms look for longer patterns, such as a word that shows up again and again.

Python includes zlib, which uses the same method (called DEFLATE) as ZIP files and PNG images. One of its ideas is to replace a repeat of something it has already seen with a short note that points back to it. In go team go! go team go!, the second go team go! becomes something like "go back 12 characters and copy 11". The note is much shorter than the text it replaces.

Here are both algorithms on the same three pieces of data. Sizes are in bytes, and zlib's results include a few bytes it always adds to describe its own format.

RLE vs zlib on the same data

import zlib

datasets = {

"striped flag": "R" * 15 + "W" * 15 + "B" * 15,

"checkerboard": "BW" * 20,

"team chant": "go team go! " * 20,

}

print(f"{'data':<14}{'original':>9}{'RLE':>6}{'zlib':>6}")

for name, data in datasets.items():

zlib_size = len(zlib.compress(data.encode(), 9))

print(f"{name:<14}{len(data):>9}{compressed_size(data):>6}{zlib_size:>6}")

Output

data           original   RLE  zlib
striped flag         45     9    17
checkerboard         40    80    13
team chant          240   480    23

RLE wins on the flag, where the data is a few long runs. zlib wins easily on the checkerboard and the chant, because it notices that BW and go team go! repeat, even though no symbol repeats next to itself. Picking the best algorithm means knowing what your data looks like.

Can you compress a file twice?

If compression saves space once, it is tempting to run it again on its own output. Try it:

Compressing already-compressed data

import zlib

chant = ("go team go! " * 20).encode()

once = zlib.compress(chant, 9)

twice = zlib.compress(once, 9)

print(f"original: {len(chant)} bytes")

print(f"compressed once: {len(once)} bytes")

print(f"compressed twice: {len(twice)} bytes")

Output

original:          240 bytes
compressed once:   23 bytes
compressed twice:  32 bytes

The second pass makes the data bigger. The first pass already removed the redundancy, so the output looks almost random, and there is nothing left for the second pass to describe more briefly. This is why putting photos or videos in a ZIP file barely shrinks them: those formats are compressed already.

What is the difference between lossless and lossy compression?

Lossless compression algorithms can usually reduce the number of bits stored or sent while guaranteeing that the original can be rebuilt exactly, bit for bit. RLE and zlib are both lossless, and so are ZIP files and PNG images. Decoding RLE is a matter of repeating each symbol by its count:

Lossless: the decoded row is an exact copy

def rle_decode(runs):

return "".join(symbol * count for count, symbol in runs)

row = "WWWWWWWWWWBBBBBWWWWW"

rebuilt = rle_decode(rle_encode(row))

print(rebuilt)

print("Exact copy of the original:", rebuilt == row)

Output

WWWWWWWWWWBBBBBWWWWW
Exact copy of the original: True

Exercise 3: Decode Run-Length Text

Write Code

Write rle_decode(code), which takes run-length code written as a string, such as '4A2B1C', and returns the original text, 'AAAABBC'. A count can have more than one digit ('12W' means twelve W's), and the original text never contains digits.

def rle_decode(code):

# Collect digits until you reach a symbol, then repeat the symbol

pass

Lossy compression algorithms throw some detail away on purpose. They can reduce the number of bits significantly, usually much more than lossless algorithms can, but they only let you rebuild an approximation of the original. Photos (JPEG), music (MP3) and streaming video use lossy compression.

Good lossy formats choose what to throw away by how people see and hear. Photo formats keep changes in brightness sharper than changes in color, because eyes notice brightness more. Music formats drop very high pitches that most people cannot hear, and quiet sounds that a louder sound at the same moment would cover up. Most of the time you cannot tell, until the compression is pushed too far and photos turn blocky or music sounds watery.

The demo below shows the idea on eight pixel brightness values from 0 to 255, which take 8 bits each. It keeps only which of 8 brightness bands each value falls in, which takes 3 bits.

Lossy: fewer bits, approximate values

brightness = [12, 15, 14, 200, 203, 201, 90, 88] # 0-255, 8 bits each

BAND = 32 # 256 values / 8 bands

stored = [value // BAND for value in brightness] # 0-7, 3 bits each

restored = [band * BAND + BAND // 2 for band in stored] # middle of each band

print("original:", brightness)

print("stored: ", stored)

print("restored:", restored)

print(f"size: {len(brightness) * 8} bits -> {len(stored) * 3} bits")

errors = [abs(a - b) for a, b in zip(brightness, restored)]

print("largest error:", max(errors))

Output

original: [12, 15, 14, 200, 203, 201, 90, 88]
stored:   [0, 0, 0, 6, 6, 6, 2, 2]
restored: [16, 16, 16, 208, 208, 208, 80, 80]
size: 64 bits -> 24 bits
largest error: 10

The file shrank by more than half, and the restored values are close. But 12, 15 and 14 all became 16, and nothing in the stored data can tell them apart again. That loss is permanent.

Which kind of compression should you choose?

Ask what matters most in the situation.

When quality or rebuilding the original exactly matters most, lossless is the usual choice. One wrong bit can break an app, change a grade in a spreadsheet, or hide a detail in a medical scan.

When making the data small or sending it fast matters most, lossy is the usual choice. A video call that freezes is worse than one that looks a little blurry.

To compare specific algorithms for a job, three questions settle most cases. Must the original come back exactly? How small does the data need to be, and how fast must it travel? What does the data look like: long runs, repeated words, or natural photos and sound?

Take a drawing app that saves pixel-art sprites. Artists edit the same sprite for weeks, so every pixel must survive (lossless), and the sprites have big areas of one color, so a run-based method like RLE does well. Now take a doorbell camera that streams live video to a phone over a cell network. The owner needs to see who is at the door right now, not every leaf on the hedge, so a lossy video format is the better fit.

Situation	Usual choice	Why
Sending an app update	Lossless	Every bit of the program must arrive unchanged
A spreadsheet of test scores	Lossless	Numbers must be exact
A live video call on slow Wi-Fi	Lossy	Speed matters more than perfect detail
Storing thousands of songs on a phone	Lossy	Saves the most space, and small losses are hard to hear

The same photo can go both ways. A photographer might keep a lossless original for editing and post a lossy copy online.

Check your understanding

A student club keeps a spreadsheet of who has paid their dues and how much. The treasurer wants to compress it before emailing it. Which choice is best?

ALossless, because every name and amount must be rebuilt exactlyBLossy, because it makes the file smallestCLossy, because spreadsheets have no redundancyDEither one, because both rebuild the original exactly

A video chat app needs calls to stay smooth for people on slow home connections. Which compression approach fits best?

ALossless, because people need to see every pixel exactlyBLossy, because cutting the amount of data sent matters more than perfect qualityCNo compression, because compression always lowers qualityDLossless, because it always produces smaller files than lossy

Which of the following statements about data compression are true? Select two answers.

Select 2 answers.

ALossless compression allows the original data to be rebuilt exactly.BLossy compression can usually reduce the number of bits more than lossless compression.CA compressed file always contains less information than the original.DEvery compression algorithm shrinks every file by the same amount.

Each image below is stored row by row and compressed with run-length encoding. Which image would most likely shrink the most?

AA flag made of three wide stripes, each one solid colorBA photo of a crowded stadiumCA picture of TV static, where every pixel is a random colorDA checkerboard where the color changes at every pixel

The code segment below rebuilds a row of pixels from run-length data, where 0 is a white pixel and 1 is a black one. What does the list pixels contain after it runs?

counts ← [3, 1, 2]
colors ← [0, 1, 0]
pixels ← []
i ← 1
REPEAT LENGTH(counts) TIMES
{
  REPEAT counts[i] TIMES
  {
    APPEND(pixels, colors[i])
  }
  i ← i + 1
}

A[0, 0, 0, 1, 0, 0]B[3, 0, 1, 1, 2, 0]C[0, 1, 0]D[0, 0, 0, 1, 1, 0, 0]

Run this pseudocode

Two files of the same size are compressed with the same lossless algorithm. File A shrinks by 80%, and file B shrinks by only 5%. Which of the following best explains the difference?

AFile A contains more redundancy, such as repeated patterns, than file B.BThe algorithm used lossy compression on file A only.CFile A was larger than file B.DFile B was damaged during compression.

A 9,000-bit message is compressed with a lossless algorithm to 3,000 bits. Which statement is true?

AThe 3,000-bit version contains all the information in the original message.BTwo thirds of the information in the message was lost.CThe receiver can rebuild only an approximation of the message.DThe message must have been one symbol repeated 9,000 times.

Exam topics: 2.2 Data Compression (DAT-1.D)

What does compression do?

How does run-length encoding work?

How much space does compression save?

Does the algorithm matter as much as the data?

Can you compress a file twice?

What is the difference between lossless and lossy compression?

Which kind of compression should you choose?

Check your understanding

Related Tutorials