Repeated text, pixel patterns and symbol sequences contain structure that need not be written out every time. Lempel–Ziv–Welch compression replaces recurring phrases with dictionary codes. Encoder and decoder begin with the same alphabet, then build matching dictionaries as they process the stream; the dictionary itself need not be transmitted entry by entry. The encoder keeps the longest phrase already known, emits its code when the next symbol would make a new phrase, and adds that extended phrase. The decoder reconstructs the same additions from preceding output. Mathematics matters because prefix structure, induction and bit-width accounting explain why decoding is unambiguous, when compression saves space and why short or irregular data can expand.
The practical search question is not simply “what is this named method?” but “which mathematical structure makes the method work, what does it guarantee, and what evidence would show that it is a poor choice?” This article keeps those questions together so students can connect mathematics education with computing, engineering, data reasoning and careful everyday decisions without turning one technique into a career promise.
Quick navigation: Why it matters · Mechanism · Worked example · Deeper ideas · Investigations · Limits · Learning route · Parent guidance · FAQs · Sources
Why this mathematics matters
Mathematics is important here because it turns an apparently visual or computational trick into a chain of reasons. The representation tells us what information is kept. The equation or invariant explains each legal step. The complexity analysis describes the work. The boundary conditions say when a conclusion should not be trusted. That combination is a practical form of problem-solving literacy.
A strong learner should be able to move in both directions: from a real task to a mathematical model, and from a formal guarantee back to its real meaning. Naming an algorithm is not enough. The useful achievement is to explain why the next operation is valid, check a small instance independently, and notice which assumptions the implementation has added.
Source: Terry Welch’s 1984 IEEE Computer paper.
Primary or implementation reference: Graphics Interchange Format 89a specification.
How the mechanism works
Initialise the dictionary with every single input symbol. Let w be the current phrase. Read the next symbol k. If wk is already in the dictionary, replace w with wk and continue. Otherwise emit the code for w, add wk under the next code, and set w=k. Emit w at end of stream. The decoder reads the first code, outputs its phrase as w, then for each next code obtains entry. Usually entry is already in the dictionary; in the special case where the code equals the next unused code, entry is w followed by the first symbol of w. Output entry, add w plus the first symbol of entry, and set w=entry.
Let the initial alphabet have q symbols. Dictionary entries correspond to phrases, and codes are integers. If a stream currently uses b-bit codes, at most 2^b distinct code values fit; a format must define when the width increases, whether the dictionary clears, and its maximum size. For m emitted b-bit codes, payload size is approximately mb bits plus framing, while raw fixed-width input of N symbols costs N log2(q) bits when q is a power of two. Compression occurs only when average phrase length grows enough to offset code width and format overhead. The encoder and decoder remain synchronised because each new entry is determined by the previous phrase and the first symbol of the current phrase.
Keep a four-column notebook labelled object, rule, guarantee and caveat. In the first column name the inputs and stored state. In the second write one update precisely. In the third state what remains true after the update. In the fourth record a tie, approximation, domain restriction or hardware assumption. This routine prevents symbols from drifting away from their meaning.
Worked example and core calculations
Use alphabet {A,B} with initial codes A=0 and B=1, and encode ABABABA. Start w=A. Reading B makes AB unknown: emit 0, add AB=2, set w=B. Reading A makes BA unknown: emit 1, add BA=3, set w=A. Reading B finds AB, so w=AB. Reading A makes ABA unknown: emit 2, add ABA=4, set w=A. The final B then A extend w from A to AB to ABA, so emit 4. Codes are [0,1,2,4]. During decoding, code 4 arrives exactly when 4 is the next unused code; the special rule constructs AB+A=ABA. The output is ABABABA.
How to audit the calculation
- Recompute every intermediate value directly from the definition.
- Keep labels, indices, signs, units and normalisation visible.
- Test a case with a known exact answer.
- State tie rules, random seeds, tolerances and boundary conventions.
- Compare with a slower transparent baseline or trusted implementation.
- Separate agreement of numbers from suitability of the real-world model.
Small examples are not childish; they are diagnostic instruments. A five-line trace can reveal a reversed inequality, a missing scale factor or an inconsistent label convention before a large dataset hides the same error behind plausible output.
Four deeper ideas
The dictionary captures phrases, not frequencies alone
An entry is created from a known phrase plus one new symbol, exploiting recurring sequential structure.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Encoder and decoder evolve in lockstep
Both can infer the same next entry from already processed material, which avoids transmitting the whole dictionary.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
The special case follows from the invariant
When the next code is referenced before its entry appears, the only consistent phrase is previous w plus its own first symbol.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
A file format adds another layer
Code packing, clear codes, end markers, width changes and bit order are format rules beyond the abstract LZW idea.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Twelve practical investigations
1. ABABABA
Trace the worked example. Emit [0,1,2,4] under the stated alphabet.
What the mathematics reveals: Repeated phrases earn short references. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Code values depend on initial conventions. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
2. No repetition
Encode a short irregular string. Compare payload and raw size.
What the mathematics reveals: Overhead can cause expansion. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Do not promise compression. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
3. Special decoder code
Decode the final 4 in the example. Construct w plus first(w).
What the mathematics reveals: The edge case is implied by synchronisation. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Reject codes beyond the next slot. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
4. Growing width
Cross a power-of-two dictionary size. Increase b under a declared rule.
What the mathematics reveals: Code capacity is discrete. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Encoder and decoder must switch together. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
5. Dictionary cap
Reach the format maximum. Freeze or issue a clear code.
What the mathematics reveals: Finite memory needs a policy. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: The policy is format-specific. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
6. GIF stream
Read the GIF89a LZW section. Identify clear and end-of-information codes.
What the mathematics reveals: A standard instantiates the abstract algorithm. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Image framing is separate. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
7. Duplicate phrases
Encounter a phrase again. Reuse its existing code.
What the mathematics reveals: Dictionary identity prevents ambiguity. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Do not add duplicates. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
8. Unicode text
Choose bytes or characters as symbols. Compare alphabets and raw sizes.
What the mathematics reveals: Symbolisation changes the model. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: State the encoding first. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
9. Corrupted code
Flip bits in a packed stream. Observe desynchronisation.
What the mathematics reveals: Compression lacks inherent integrity. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Use format-level checks where available. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
10. Compression ratio
Measure raw and final bytes. Include headers and padding.
What the mathematics reveals: Honest evaluation counts the container. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Tiny samples are unstable. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
11. Round-trip test
Encode then decode varied data. Check byte-for-byte equality.
What the mathematics reveals: Losslessness is testable as an invariant. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Tests complement rather than replace proof. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
12. Security context
Compress sensitive mixed-origin data. Discuss length leakage.
What the mathematics reveals: Output size can reveal patterns. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Do not treat compression as a security boundary. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
Limits and misconceptions
LZW is lossless but not guaranteed to make every input smaller. Short, random or rapidly changing data can grow because codes and headers add overhead. Memory is finite, so real formats cap, freeze or reset dictionaries. GIF’s LZW variant has specified clear codes and variable code widths; other LZW formats can differ and are not interchangeable merely because they share a name. Compression ratio depends on symbol representation and sequence order. LZW does not provide encryption, integrity or error correction, and one corrupted code can disturb later dictionary synchronisation. Modern codecs may outperform it for particular media or data distributions.
Five misconceptions to challenge
- Lossless means the file always shrinks: It means exact recovery; some inputs expand.
- The dictionary must be sent with the codes: Encoder and decoder normally rebuild it deterministically.
- LZW counts individual symbol frequencies: It learns repeated phrases through incremental dictionary entries.
- Every LZW stream uses one identical bit format: Container rules for widths, clearing and packing vary.
- Compression protects confidential data: It does not supply secrecy or authentication.
Another broad misconception is that advanced mathematics automatically creates intelligence, admission, income or employment. It does not. Deliberate study can strengthen modelling, abstraction, calculation and explanation, while real pathways also depend on interests, communication, domain knowledge, opportunities and circumstances outside one topic.
A learning route for students
Move from a visible trace to a symbolic rule, then to code and critique. For every step below, prepare three pieces of evidence: a correct hand example, a boundary or failure case, and a short explanation using the relevant invariant. Do not advance merely because software returned a number.
Step 1: Model a finite symbol alphabet
Begin with the smallest non-trivial instance that lets you model a finite symbol alphabet. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 2: Trace longest-prefix matching
Begin with the smallest non-trivial instance that lets you trace longest-prefix matching. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 3: Build an encoder dictionary
Begin with the smallest non-trivial instance that lets you build an encoder dictionary. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 4: Reconstruct a decoder dictionary
Begin with the smallest non-trivial instance that lets you reconstruct a decoder dictionary. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 5: Handle the next-code special case
Begin with the smallest non-trivial instance that lets you handle the next-code special case. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 6: Calculate code-width capacity
Begin with the smallest non-trivial instance that lets you calculate code-width capacity. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 7: Separate algorithm from file format
Begin with the smallest non-trivial instance that lets you separate algorithm from file format. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 8: Measure compression ratio honestly
Begin with the smallest non-trivial instance that lets you measure compression ratio honestly. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 9: Test round-trip losslessness
Begin with the smallest non-trivial instance that lets you test round-trip losslessness. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 10: Recognise security and integrity limits
Begin with the smallest non-trivial instance that lets you recognise security and integrity limits. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
A four-week practice plan
- Week 1 — vocabulary and diagrams: define each object, redraw the mechanism and reproduce the worked example.
- Week 2 — equations and manufactured tests: derive the key relation and test inputs with known answers.
- Week 3 — implementation and evidence: use a trusted library, record parameters and compare with a transparent baseline.
- Week 4 — transfer and critique: apply the method to a new context, report limits and identify when a different method is better.
Guidance for parents and educators
Ask “what stays true?” and “what could make this conclusion fail?” before asking for speed. Invite the student to draw the input and output, estimate the result and locate the first step that disagrees with a reference. These prompts reveal conceptual understanding more clearly than memorised terminology.
Advanced enrichment should sit beside secure school foundations in algebra, functions, geometry, statistics and computational thinking. It need not accelerate a student into a fixed career identity. A healthy goal is curiosity with discipline: the learner becomes comfortable reading unfamiliar notation, checking an example, revising a model and communicating uncertainty.
Evidence prompts for a useful conversation
- Which quantity is observed and which is inferred?
- Which step saves work, and why is it allowed?
- Is the claim exact, approximate, probabilistic or empirical?
- What units and conventions are in use?
- Which input makes the method struggle?
- What simple baseline could check the answer?
- What would count as evidence that the parameters are poor?
Mini-project assessment
A strong mini-project contains the original question, a small reproducible dataset, a hand-worked example, code or a spreadsheet trace, at least one boundary test, a comparison with a baseline, and a paragraph on limits. Assess the reasoning trail as well as the final output. Repairing a model after a surprising result is valuable mathematical progress.
Six evidence checks for a finished project
Check 1: Model a finite symbol alphabet
Ask the student to demonstrate how to model a finite symbol alphabet without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 2: Trace longest-prefix matching
Ask the student to demonstrate how to trace longest-prefix matching without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 3: Build an encoder dictionary
Ask the student to demonstrate how to build an encoder dictionary without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 4: Reconstruct a decoder dictionary
Ask the student to demonstrate how to reconstruct a decoder dictionary without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 5: Handle the next-code special case
Ask the student to demonstrate how to handle the next-code special case without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 6: Calculate code-width capacity
Ask the student to demonstrate how to calculate code-width capacity without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Frequently asked questions
What does LZW stand for?
Lempel–Ziv–Welch.
Is LZW lossless?
Yes, a valid decoded stream reproduces the original symbols exactly.
What is stored in the dictionary?
Phrases built from a known phrase followed by one symbol.
Why need the dictionary not be transmitted?
The decoder rebuilds the same entries in the same order.
Can LZW make data larger?
Yes, especially for short or irregular data.
What is the special decoder case?
A code equal to the next unused slot represents previous phrase plus its first symbol.
Why do code widths change?
More bits are needed when the dictionary outgrows the current code space.
Does GIF use LZW?
Yes, GIF image data uses a specified LZW variant with format rules.
Does LZW encrypt data?
No.
What should students know first?
Strings, dictionaries, binary codes, induction and information size.
Useful next reading and sources
Source: Terry Welch’s 1984 IEEE Computer paper.
Source: Graphics Interchange Format 89a specification.
Related eduKateSG reading: Elias–Fano monotone integer encoding.
Related eduKateSG reading: Boyer–Moore string search.
Related eduKateSG reading: Checksums, CRCs and data integrity.
Read sources with a question in mind: which definition, theorem, default or limitation is being supported? An authoritative link is useful evidence, but it does not replace a worked calculation or a clear statement of how the source applies to the example.
A cheerful final thought
Mathematics becomes friendlier when every symbol has a job and every claim has a boundary. Start small, make the state visible, test the awkward case, and celebrate the moment when a pattern becomes explainable. That is the practical benefit of learning mathematics: not certainty about every future, but a growing ability to ask better questions and build trustworthy answers.