A-Level · Data Representation · Compression

LZW Dictionary Compression

A step-by-step simulation of encoding and decoding the same text using a dynamically-built dictionary.
Pease porridge hot, pease porridge cold,
Pease porridge in the pot, nine days old.
Some like it hot, some like it cold,
Some like it in the pot, nine days old.
Encoding Compress
Turns the 31-word rhyme into a short list of codes, building a dictionary of repeated phrases as it goes.
Step 0
Word sequence
Current phrase being tracked
-
Codes output so far
-
Dictionary (working memory — grows as repeated phrases are found)
Encoding finished. The only things that leave this step are the 13-word starting alphabet and the list of 23 codes. The full 34-entry dictionary above was scratch memory used to make decisions while encoding — it is not stored or transmitted anywhere.
Decoding Decompress
Starting from just the 13-word alphabet and the 23 codes, rebuilds the same dictionary independently and reconstructs the original rhyme.
Step 0
Compressed codes (given)
Reading code
-
Words rebuilt so far
-
This step
Dictionary (starts with 13, given — grows live)
Rebuilt words so far
About this resource · A-Level

How LZW compression works

LZW (Lempel–Ziv–Welch) is a lossless, dictionary-based compression method. It starts with a small dictionary of single symbols, here the 13 distinct words in the rhyme. As it reads the input, it keeps extending the current phrase while that phrase is already in the dictionary. When it meets a phrase that isn't there, it outputs the code for the longest known phrase and adds the new, longer phrase to the dictionary.

The key exam point is that the full dictionary is never transmitted. The decoder starts with the same initial alphabet and rebuilds the dictionary itself, following the same rules as it reads the codes. Only the starting alphabet and the list of codes need to be sent, which is why the output is smaller than the input.

Step through the encoding panel and notice how repeated phrases like "pease porridge" quickly get their own codes. Then step through the decoding panel to see the receiver reconstruct identical dictionary entries.

Exam tips

Specification

Dictionary-based lossless compression, OCR H446 and AQA 7517.

Related resources

Browse all free Computer Science resources →

Want one-to-one help with this topic? I'm Damian Biasone, a qualified Computer Science teacher with 20 years' experience, tutoring GCSE and A-Level students online.

OCR A-Level (H446) tuitionAQA A-Level (7517) tuition