How Compression Works | LZ77, LZ78 and LZW — How Repetition Became Dictionaries, Pointers and Codes

LZ77, LZ78 and LZW are foundational lossless compression algorithms built around one of the simplest facts in data: repetition does not need to be transmitted twice in full. LZ77 turns repeated substrings into backward distance–length references inside a sliding history window. LZ78 grows an explicit phrase dictionary and transmits dictionary references plus new symbols. LZW refines that dictionary idea so the stream can be represented largely as dictionary codes that encoder and decoder build in lockstep.

Together, the Lempel–Ziv family sits underneath a huge part of practical dictionary compression: DEFLATE in ZIP, gzip and PNG descends from the LZ77 side; GIF historically uses LZW; LZMA extends the LZ77 tradition with longer-range matching, probability modeling and range coding. The family also introduced a general engineering pattern that remains powerful decades later: discover repeated structure in what has already been seen, replace the repeated material with a shorter reference, and let the decoder reconstruct the same structure without needing the original dictionary in advance.

This guide explains how LZ77, LZ78 and LZW work from first principles: sliding windows, search buffers, look-ahead, overlapping copies, phrase parsing, dictionary growth, code-width changes, dictionary resets, encoder–decoder synchronisation, why LZW differs from LZ78, how DEFLATE uses LZ77-style matches with Huffman coding, why GIF uses LZW, where match finding ends and parsing begins, why already-compressed or random data defeats the mechanism, and how modern compressors still inherit the central Lempel–Ziv insight—the past can be a dictionary when the receiver can rebuild the same past.

---

Quick Read

LZ77 replaces a repeated substring with a reference to where the same bytes appeared recently: distance back plus match length. LZ78 parses the stream into new phrases, stores those phrases in a growing explicit dictionary, and represents each new phrase using the index of a known phrase plus one additional symbol. LZW begins with a dictionary of basic symbols, outputs dictionary codes, and adds longer phrases to the dictionary implicitly as the stream is processed.

The algorithms are lossless. The decoder reconstructs the exact source because every reference points to data or dictionary state the decoder can reproduce deterministically. No human-readable phrase table needs to be transmitted separately if both sides follow the same construction rules.

Ziv and Lempel’s 1977 and 1978 papers established two major branches. Terry Welch’s 1984 LZW algorithm became an influential refinement of the LZ78 branch. Later formats combine these ideas with entropy coding, match-finding heuristics, block structure and probability models.

Lempel–Ziv compression does not ask the sender and receiver to share a dictionary beforehand. It teaches both sides to build the same dictionary from the message itself.

The Three Mechanisms in One View

• LZ77: history itself is the dictionary → find a previous occurrence → encode distance + length.
• LZ78: build explicit phrases → new phrase = known phrase + new symbol → encode phrase index + symbol.
• LZW: preload alphabet → output longest known phrase code → add previous phrase + first symbol of next phrase → decoder mirrors dictionary growth.

1. Why Repetition Is Compressible

Consider the sequence the cat sat on the cat. The second occurrence of the cat contains no new literal information if the receiver already reconstructed the first occurrence and the format allows a reference to it. Instead of sending seven bytes again, the encoder can send an instruction meaning “copy seven bytes from sixteen bytes back,” assuming the chosen format and positions make that reference legal.

Compression works when the reference costs fewer bits than the repeated material. A two-byte match may not be worth referencing if the distance and length codes cost more than the two literal bytes. A hundred-byte match usually is.

This economic test—reference cost versus literal cost—lies underneath the entire dictionary-compression family.

2. Dictionary Compression Is a Representation Strategy

A dictionary compressor identifies repeated strings and gives those strings shorter names. The dictionary can be implicit in recent output, as in LZ77, or explicit as numbered phrases, as in LZ78 and LZW.

The word dictionary does not imply human language. Entries can be arbitrary byte strings: pixels, executable instructions, JSON keys, DNA characters, or fragments of machine data. The mechanism cares only that sequences recur.

Meaning can create repetition, but the compressor does not need to understand the meaning to exploit it.

3. The Decoder’s Past Is the Most Convenient Shared Memory

The sender could transmit a complete dictionary before the data, but that dictionary would cost bits. Lempel–Ziv methods discovered a stronger idea: use information the decoder necessarily already possesses because it has reconstructed the earlier stream.

For LZ77, previously decoded bytes are directly available as copy sources. For LZ78/LZW, the decoder can build phrase entries from earlier decoded codes according to deterministic rules.

The dictionary is therefore synchronised by causality: both sides arrive at the same state because both have processed the same prefix.

4. LZ77: The Sliding-Window Branch

The 1977 Ziv–Lempel algorithm represents new input using substrings that occurred in a recent portion of the already processed sequence. Practical descriptions often divide the working area into a search buffer containing previous data and a look-ahead buffer containing upcoming input.

The encoder searches the history for a substring matching the beginning of the look-ahead. When a useful match exists, it emits a reference containing a backward distance and a length, or a closely related tuple depending on the specific variant.

Then the window advances and the newly encoded bytes join the history.

5. A Backward Reference Has Two Core Numbers

Distance tells the decoder how far backward to begin copying. Length tells it how many bytes to copy. If the current output position is 1000, a distance of 20 begins at output position 980. A length of 12 copies twelve bytes from that source.

Different formats encode the numbers differently. DEFLATE, for example, uses Huffman-coded length and distance symbols plus extra bits and permits backward distances up to 32 KiB and match lengths up to 258 bytes. Those are DEFLATE format choices, not universal properties of LZ77.

LZ77 is the family concept; concrete formats specify the legal reference space.

6. Literals Cover What Cannot Be Referenced Economically

Every input begins with data the decoder has never seen. A sliding-window compressor therefore needs a way to emit literal bytes. Even later, a byte may be unique or part of a match too short to justify a reference.

Practical LZ77 descendants produce a stream containing literals and matches. The entropy coder then gives common literals, lengths and distances shorter representations.

The dictionary stage and entropy-coding stage should remain conceptually separate. One describes repetition; the other prices the symbols representing that description.

7. The Window Bounds How Far Back Memory Reaches

An infinite history could discover a phrase repeated millions of bytes apart, but searching and representing unlimited distance would be expensive. Practical sliding-window compressors cap history.

A small window uses less memory and shorter distance codes but misses long-range repetition. A large window discovers more matches but costs memory, match-search time and possibly extra bits for large distances.

Window size is therefore a compression-ratio and resource trade-off, not simply a maximum-memory setting.

8. Overlapping Copies Are One of LZ77’s Most Powerful Details

Suppose the decoder has output one A, then receives a match with distance 1 and length 100. The copy source begins one byte back, but as copying proceeds, newly produced A bytes become part of the source. The decoder can therefore generate a long run from a tiny seed.

This overlap is legal in many LZ77 descendants and explains how repeated periodic structures can be represented by matches longer than the original distance.

A decoder implemented with an ordinary non-overlapping memory copy can therefore be wrong. Copy semantics matter.

9. Distance 1 Encodes Runs Efficiently

Long runs such as 0000000000... are the simplest overlapping case. Once one zero exists, a distance-1 match can extend the run arbitrarily within the format’s maximum length.

Longer periodic patterns behave similarly: distance 2 can repeat ABABAB...; distance 3 can repeat XYZXYZ....

LZ77 therefore captures both exact previous phrases and local periodicity using the same copy mechanism.

10. The Longest Match Is Not Automatically the Best Match

If two matches cover the same region, one may be longer but much farther away. The farther distance may require more bits. A shorter nearby match followed by another match may produce a smaller total code.

This introduces the parsing problem: once candidate matches exist, which sequence of literals and matches should represent the input?

The fourth article in this approved batch owns that decision in depth: Match Finding and Parsing. This article keeps the family mechanism separate from encoder-search strategy.

11. Match Finding Is an Encoder Problem

The decoder does not need to search for matches. It receives a distance and length and copies. This creates an important asymmetry: encoders can spend much more computation searching for better references without making the decompressor equally expensive.

Fast encoders may check a few hash-chain candidates. Slow encoders may explore many candidates or use more elaborate structures. As long as they emit a valid format, the same decoder can accept both.

Compression level is often an encoder-effort setting rather than a change in the decompression format.

12. The Search Buffer Is an Implicit Dictionary

LZ77 is called a dictionary method even though it may store no explicit list of phrases. Every substring inside the history window is a potential dictionary entry. The bytes themselves are the dictionary.

This implicit dictionary can contain an enormous number of overlapping substrings without separately storing each one. Match-finding data structures merely index the history to make useful substrings discoverable.

The distinction between dictionary content and search index is important: the output history owns the actual bytes; the hash table or tree only helps the encoder find them.

13. Why LZ77 Is Naturally Streaming

A sliding-window compressor needs only bounded recent history and a bounded amount of look-ahead. It can therefore compress arbitrarily long sequential input with bounded working memory. RFC 1951 explicitly highlights this property for DEFLATE’s LZ77+Huffman design.

The decoder is similarly incremental: literals are written immediately, matches copy from already produced output, and old history can be discarded once it falls outside the legal distance.

Streaming and bounded state helped make the LZ77 branch enormously practical.

14. Random Access Is Harder Than Streaming

A match can point to bytes in earlier output. To begin decoding in the middle of a raw LZ77 stream, the decoder may need previous history that has not been reconstructed.

File formats solve this by inserting independent blocks, reset points, indexes or separately compressed chunks. Those boundaries improve seeking and parallel decoding but prevent matches from crossing them.

Random access buys independence by shortening the effective dictionary horizon.

15. LZ77’s 1977 Contribution Was More Than a File Format

Ziv and Lempel’s 1977 paper described a universal sequential compression algorithm that did not require prior probabilistic knowledge of the source. The algorithm exploited recurring phrases in the already observed sequence and supplied a constructive route toward asymptotically strong compression for broad source classes.

The historical importance is not that every modern LZ77 codec reproduces the original paper literally. Later engineers changed tuple formats, match limits, search strategies and entropy coding. The durable inheritance is the sliding-history phrase-reference mechanism.

Modern descendants are a family tree, not byte-for-byte copies of one 1977 implementation.

16. LZSS Removes the Mandatory Next Symbol

Some textbook LZ77 descriptions encode tuples such as distance, length and next literal. Later variants such as LZSS separate literals and matches so a match need not always carry a trailing unmatched symbol. This can avoid wasting space when a long match already explains the data.

The exact token grammar varies among descendants. What remains LZ77-like is backward phrase referencing within a history window.

When learning the family, understand the reference mechanism before memorising a particular tuple notation.

17. DEFLATE Is LZ77 Plus Huffman Coding

DEFLATE is one of the most widely deployed LZ77 descendants. Its specification states that each compressed block uses a combination of LZ77 and Huffman coding. The LZ stage emits literals or length–distance references; Huffman codes then represent literal/length and distance symbols compactly.

Dynamic DEFLATE blocks can also transmit block-specific Huffman code lengths, themselves compressed. Fixed-Huffman blocks use predefined codes. Stored blocks bypass compression for data that would not benefit.

DEFLATE is therefore a pipeline. Calling Huffman coding “the compression algorithm” omits the dictionary stage; calling LZ77 the entire format omits the entropy stage.

18. ZIP and gzip Are Containers Around Compression Methods

Users often treat ZIP, gzip and DEFLATE as synonyms. They are related but not identical. DEFLATE defines a compressed data representation. gzip adds a file wrapper with metadata and checks. ZIP is an archive format that can store multiple entries and supports several compression methods, with DEFLATE historically prominent.

The distinction matters when diagnosing compatibility or overhead. Archive structure, checksum and filename metadata are not part of the LZ77 match mechanism.

Compression format, file wrapper and archive container are different layers.

19. PNG Uses DEFLATE After Image Filtering

PNG is lossless image compression, but LZ77 does not directly “understand images.” PNG first applies reversible scanline filters that transform pixel values into forms with more local regularity, then compresses the resulting bytes using DEFLATE.

This is a powerful systems lesson: dictionary compression improves when upstream representation makes redundancy easier to see.

The transform remains lossless because the decoder can invert the filter after decompression.

20. LZ78 Takes a Different Route: Build Explicit Phrases

The 1978 Ziv–Lempel branch does not use a bounded sliding history as the dictionary. Instead, it parses input into phrases and grows an explicit dictionary of previously created phrases.

A new phrase is formed from a phrase already in the dictionary plus one additional symbol. The encoder transmits the index of the known phrase and the new symbol, then inserts the combined phrase into the dictionary.

The decoder receives the same pair, reconstructs the new phrase, outputs it and adds it at the same dictionary index. Dictionary synchronisation emerges from deterministic insertion order.

21. A Tiny LZ78 Example

Start with dictionary entry 0 representing the empty string. Suppose the input begins ABABABA.... The first phrase may be A, represented as (0, A), and added as entry 1. Next B becomes (0, B), entry 2. The next unseen phrase beginning at the current position might be AB, represented as (1, B), because A is already entry 1.

Later, longer phrases can be built from earlier dictionary entries. The exact parse depends on the formal algorithm, but the key mechanism remains: known phrase index + one new symbol creates a new phrase.

The dictionary acquires vocabulary from the source itself.

22. LZ78’s Dictionary Is a Phrase Tree

Because each new phrase extends an existing phrase by one symbol, the dictionary naturally forms a trie. The parent is the known phrase; the edge label is the new symbol; the child is the newly created phrase.

This structural relationship makes dictionary construction and lookup conceptually clean. Every phrase has ancestry back to the empty string.

Unlike LZ77, old phrases need not disappear simply because they are far back in the stream—unless the implementation imposes a dictionary size limit or reset policy.

23. The Dictionary Index Is a Name for a Phrase

Once phrase 317 means a particular byte string, later output can refer to 317 instead of retransmitting the phrase. The dictionary transforms variable-length strings into integer names.

The name becomes useful only after the phrase has been introduced. Early occurrences pay dictionary-building cost; repeated later occurrences harvest the benefit.

This is the same amortisation logic seen throughout compression: pay once to establish structure, save repeatedly if the structure returns.

24. LZ78 Does Not Need a Sliding Distance

Because phrases receive explicit dictionary indexes, a phrase can remain addressable independent of how far back its literal bytes occurred. This differs from a bounded LZ77 history where a phrase eventually slides out of the legal reference window.

The cost is dictionary memory. If entries accumulate without bound, memory and code widths grow. Practical descendants need caps, resets, pruning or dictionary reuse rules.

LZ77 bounds memory by recency; LZ78-style methods often need explicit dictionary management.

25. LZ78 Is Not Merely LZ77 With Different Numbers

Both are universal dictionary methods, but their references name different things. LZ77 references a location in recent output. LZ78 references a phrase entry created by the parser.

This changes memory, search, random-access behaviour and what happens as the file grows. It also changes how a decoder reconstructs the dictionary.

Treat them as two related architectures, not notation variants of one codec.

26. LZW Refines the LZ78 Family

Terry Welch’s 1984 LZW algorithm builds on the LZ78 idea but removes the need to transmit an explicit “next symbol” beside every dictionary index. The dictionary is initialised with the base alphabet, so individual symbols already have codes. Encoder and decoder then construct longer phrases as codes are processed. Welch described the method as dynamically adapting to redundancy in the data.

The encoder repeatedly finds the longest phrase currently in the dictionary, outputs its code, then adds a new phrase formed from that phrase plus the first symbol of the next phrase.

The decoder can infer the same new phrase from the code sequence without receiving the added characters separately.

27. LZW Starts With the Alphabet Already Known

If the source alphabet is bytes, the initial dictionary can contain all 256 one-byte strings. A code directly identifies any literal byte from the start.

Longer dictionary entries begin at higher code numbers. As input is parsed, those entries capture recurrent byte sequences.

Preloading the alphabet removes LZ78’s need to pair a known phrase index with one raw symbol for every new phrase.

28. A Small LZW Encoding Walkthrough

Imagine the input ABABABA and a starting dictionary containing A and B. Begin with phrase A. The next symbol B makes AB, which is not yet in the dictionary. Output the code for A, add AB, and begin a new phrase with B.

Next symbol A forms BA, new again. Output B, add BA, begin A. The next B produces AB, which now exists, so extend the current phrase rather than output immediately. Add the next A; ABA is new, so output the code for AB, add ABA, and continue.

The dictionary learns longer recurring phrases from shorter ones without any dictionary payload transmitted separately.

29. The Decoder Rebuilds LZW From Code Adjacency

After decoding one phrase and then the next, the decoder adds a dictionary entry formed from the previous phrase plus the first symbol of the current phrase. This mirrors the entry the encoder added when it discovered that extension was new.

The rule depends on processing order. Encoder and decoder must agree exactly on when entries become available and when code width changes.

LZW is a synchronised state machine disguised as a stream of integers.

30. The Famous LZW “Code Not Yet in Dictionary” Case

LZW has a subtle decoder case where a received code can equal the next dictionary index—the very entry being defined by the current transition. This can happen for patterns where a phrase is immediately followed by its own first symbol.

The decoder resolves the case deterministically: the unknown phrase is the previous decoded phrase plus its own first character. This is not corruption; it follows from the encoder being one dictionary insertion ahead in that particular structural situation.

Any correct LZW implementation must handle this case explicitly.

31. Dictionary Codes Need Enough Bits

A dictionary with 256 entries fits in eight bits. Once it grows beyond 256, nine bits are needed; beyond 512, ten bits; and so on. Practical formats choose rules for variable-width codes or fixed maximum widths.

If code width grows without limit, the dictionary can eventually become inefficient: new long codes cost more while many old entries may never be reused.

Dictionary reset policies are therefore central to practical LZW.

32. Clear Codes Reset the LZW Dictionary

Formats such as GIF reserve special codes including a clear code so the dictionary can be reset to its initial state. Resetting lowers code width and removes stale phrases when the source changes.

The cost is cold start: useful learned phrases disappear and must be rebuilt. A good reset policy balances dictionary saturation against the value of retained history.

Reset is a form of controlled forgetting.

33. GIF’s LZW Is a Specific Format Contract

GIF uses an LZW-based compression scheme with format-specific initial code size, clear code, end-of-information code and code-width growth rules. LZW is therefore the compression family; GIF specifies one concrete way to embed it in image data.

The dictionary operates over palette-index values, not raw RGB triples. Repeated index patterns in scan order become phrases. Image structure and palette arrangement therefore influence compression.

Understanding the format requires separating LZW’s dictionary mechanism from GIF’s framing and image model.

34. TIFF Has Also Used LZW

TIFF is a flexible image container supporting multiple compression methods, one of which has historically been LZW. The same LZW family can therefore appear in different file formats with different surrounding metadata, pixel organization and interoperability rules.

Again, algorithm and container are separate layers. A decompressor needs both the image format specification and the correct LZW variant details.

File extensions tell you the outer contract, not the complete coding path.

35. Why LZW Was Attractive for Hardware and Transparent Compression

Welch’s 1984 presentation emphasized transparent, adaptive compression suitable for systems where applications need not know the data type. The dictionary grows directly from input, and the algorithm can be implemented with comparatively regular table operations.

For storage devices and communication links of that era, a self-adapting dictionary method offered a practical way to exploit redundancy without manual file-specific models.

The historical environment matters: memory, CPU, disk and network costs were different, but the design goal—automatic transparent compression—remains recognizable today.

36. LZ77 and LZW Learn Different Dictionaries

LZ77’s dictionary is every substring available inside a recent window. It forgets by age. LZW’s dictionary is a finite set of phrases explicitly constructed by parsing. It forgets only when the format resets or replaces entries.

A phrase that occurred long ago can remain an LZW dictionary entry even after its literal bytes would have fallen outside an LZ77 window. Conversely, LZ77 can reference arbitrary overlapping substrings without having created a numbered phrase entry first.

Both are adaptive, but their memories have different geometry.

37. Repetition Distance Matters in LZ77, Not in LZW

In a bounded LZ77 format, a phrase repeated within the window can be referenced; the same phrase repeated just beyond the maximum distance cannot. LZW has no equivalent geometric distance constraint once a phrase is in the dictionary.

But LZW’s code width grows with dictionary size, and the phrase must have been constructed through the parsing process. It cannot reference every arbitrary old substring automatically.

One system pays attention to recency; the other to phrase vocabulary.

38. LZ77 Can Reuse a Phrase Immediately

As soon as bytes appear in output history, an LZ77 encoder can match against them, including overlapping matches. There is no separate phrase-registration stage.

LZW must encounter a sequence through its parsing process before a dictionary code for that sequence exists. The dictionary evolves in discrete entries.

This difference can change behaviour on highly periodic short patterns and on abrupt repeated records.

39. Phrase Boundaries Matter More in LZ78/LZW

Explicit-dictionary methods parse the stream into phrases. Which phrase is emitted determines which new phrase is added, which changes the future dictionary. Parsing decisions therefore have a state-building effect.

LZ77 parsing also matters, but choosing one match does not create a numbered dictionary entry that blocks or enables future entries in the same way. The underlying history remains the reconstructed bytes.

Dictionary structure and parsing are more tightly coupled in LZ78-style schemes.

40. Why Dictionary Growth Eventually Becomes a Problem

Every new LZ78/LZW phrase consumes memory and another code point. If growth never stops, code widths expand and lookup tables become large. Many old phrases may never recur.

Practical systems cap the dictionary, freeze it, reset it or recycle entries. Each choice changes adaptation. Freezing preserves known phrases but cannot learn new ones. Resetting adapts to new domains but forgets useful old phrases.

Bounded dictionary management turns an elegant unbounded algorithm into a production codec.

41. Fixed-Width Codes Waste Early Space

If a format reserves twelve bits for every LZW code from the beginning, the initial 256-symbol dictionary uses only a small portion of the code space. Eight- or nine-bit codes would suffice early.

Variable-width coding starts narrow and grows as dictionary indices require more bits. This improves early efficiency but creates transition rules the decoder must mirror precisely.

Bit packing is therefore part of the format contract, not merely an implementation convenience.

42. Code-Width Transition Timing Can Break Compatibility

Encoder and decoder must agree on whether the code width grows immediately before a threshold code is emitted or after the dictionary crosses the threshold. Off-by-one differences can decode correctly for thousands of symbols and then fail abruptly at the first width transition.

Specifications therefore need exact state-machine rules. “Use variable-width LZW” is not enough for interoperability.

Compression formats are protocols, not just mathematical ideas.

43. LZ78/LZW Lookup Can Use Tries or Hash Tables

The encoder repeatedly asks whether current phrase + next symbol already exists in the dictionary. A trie maps naturally to the phrase tree; hash tables can find composite keys efficiently; specialized structures reduce memory.

The decoder’s job is simpler because codes directly identify entries, but it must reconstruct entry strings or parent links efficiently.

Data-structure choices change speed and memory without changing the abstract LZW code stream.

44. Parent Links Can Store Phrases Compactly

An LZW phrase need not be stored as a full copied string. Because each new phrase extends a previous phrase by one symbol, a dictionary entry can store parent-code + appended byte.

To output the phrase, the decoder follows parent links backward until it reaches a base symbol, then reverses the collected bytes. This saves dictionary memory at the cost of traversal work.

The phrase tree’s structural redundancy can itself be compressed in memory.

45. LZ77 Decoding Is Often Faster Than Encoding

The encoder may spend substantial work finding and comparing candidate matches. The decoder simply reads a literal or performs a copy. This asymmetry is highly useful in distribution systems where content is compressed once and decoded many times.

High compression settings can therefore increase encoding time dramatically while leaving the output format and decoder almost unchanged.

Optimization should distinguish producer cost from receiver cost.

46. LZW Encoding and Decoding Are More Symmetric

Both LZW sides build dictionaries, though the encoder must search for the longest dictionary phrase while the decoder receives phrase codes directly. The asymmetry exists, but dictionary construction is substantial work on both sides.

Memory footprints can also be similar because both require the same phrase vocabulary.

The family’s practical profile therefore differs from sliding-window formats with very simple copy decoders.

47. Already-Compressed Data Defeats All Three

A ZIP, JPEG, MP4 or other compressed stream has already removed much accessible redundancy. Exact repeated phrases may be rare and dictionary codes may not recur often enough to compensate for reference overhead.

Running LZ compression again can enlarge the data because framing, dictionary codes or entropy tables add bytes without discovering useful repetition.

A good compressor needs a stored/raw mode or a higher-level decision not to recompress incompressible blocks.

48. Encryption Defeats Dictionary Compression by Design

Strong ciphertext should look statistically random. Repeated plaintext patterns are deliberately hidden. LZ77 cannot find useful exact matches; LZW cannot grow a vocabulary that pays for itself.

Compression generally belongs before encryption when both are required. Reversing the order removes the structure the compressor needs.

The same unpredictability that protects secrecy destroys compressibility.

49. Random Data Is the Honest Failure Case

Random data can contain accidental short repeats, but a reference to them often costs as much as the literals. There is no systematic redundancy to exploit.

No lossless compressor can make every possible input shorter. If it did, the mapping could not remain one-to-one. Some inputs must stay the same size or grow.

Lempel–Ziv methods are powerful because real-world data are structured, not because information theory has been bypassed.

50. Small Files Can Lose to Overhead

A forty-byte file may contain repetition, but archive headers, checksums, code tables or dictionary state can cost more than the savings. LZW may not have enough time to build useful phrases. LZ77 may find only short matches.

Compression effectiveness must be measured on final stored size, not on match statistics alone.

Startup cost is part of the system.

51. Large Files Reward Recurrence at More Scales

As a file grows, it offers more chances for repeated phrases, recurring field names, repeated headers, common substrings and learned dictionary entries. Compression ratios can therefore improve with scale on homogeneous data.

But a bounded LZ77 window cannot use repetition farther back than its maximum distance. LZW can retain old phrases until reset, though code width and dictionary saturation impose different limits.

Source scale interacts with dictionary architecture.

52. Homogeneous Data Helps More Than Mixed Data

A large file containing one stable data type tends to reuse structures. A file that alternates unrelated compressed blobs, text, random identifiers and encrypted regions creates weaker reuse.

Solid archives can improve compression by grouping similar files together so later files reuse earlier vocabulary. The cost is poorer independent extraction and more damage propagation.

Ordering becomes part of compression design.

53. Sorting Similar Files Can Improve LZ77 Compression

If a solid compressor has a large enough dictionary or window spanning multiple files, placing similar source files adjacent creates nearby repetition. Templates, headers and code fragments become easy matches.

If unrelated files are interleaved, the useful phrase may fall out of the window before it returns.

Physical ordering changes the effective distance between repetitions.

54. LZ77 Distances Form Their Own Statistical Distribution

Recent matches are often more common than very distant ones. Formats exploit this by assigning shorter codes to small distances or by maintaining recent-offset shortcuts.

The match itself and the code used to describe its distance therefore interact. A compressor may prefer a slightly shorter match at a cheap recent distance over a longer expensive distance.

This boundary leads directly into the separate parsing article.

55. Match Lengths Also Have a Distribution

Short matches are common but may not save enough bits. Long matches are valuable but rarer. Formats define minimum match lengths and encode different length ranges with different code costs.

DEFLATE starts matches at length 3 and represents lengths through a combination of symbols and extra bits, with a maximum of 258. Again, these are DEFLATE choices rather than universal LZ77 laws.

A parser should evaluate encoded cost, not raw match length alone.

56. Lazy Matching Can Beat Greedy Matching

A greedy LZ77 encoder may take the best match starting at the current byte immediately. A lazy encoder checks whether advancing one byte reveals a much better match before committing.

This can improve compression because consuming a mediocre match may destroy access to a longer match starting one byte later. More advanced optimal parsers consider many future choices.

These are parsing strategies, not changes to the LZ77 reference mechanism. They are intentionally deferred to article four.

57. Hash Chains Are a Common Match-Finding Tool

An encoder can hash a few upcoming bytes and use the hash to locate previous positions that begin with the same prefix. A chain links positions sharing that hash. The encoder compares candidates until it finds a good match or reaches a search limit.

Searching more candidates tends to improve matches and increase CPU time. Compression levels often adjust this search budget.

The hash chain indexes history; the LZ77 dictionary remains the actual bytes.

58. Binary Trees and Suffix Structures Search Differently

Binary trees can organize candidate suffixes lexicographically and prune comparisons. Suffix arrays and suffix trees provide other routes to repeated-substring search. Each structure trades build cost, memory, locality and search quality differently.

High-ratio encoders may spend substantial time on sophisticated match finding. Fast encoders may prefer simple hashes and limited probes.

The format does not dictate the search algorithm unless explicitly specified.

59. Decoder Complexity Can Remain Stable Across Compression Levels

Two DEFLATE encoders can produce different token sequences for the same source: one found better matches, one stopped searching early. Both streams still contain ordinary literals and length–distance pairs and are decoded by the same mechanism.

This lets a system expose “fast,” “normal” and “best” encoder modes without requiring separate decoders.

Format stability decouples producer effort from receiver complexity.

60. LZW Dictionary Search Is a Different Problem

An LZW encoder does not search arbitrary recent substrings by position. It asks whether the current phrase extended by one symbol exists in the explicit dictionary.

A hash table keyed by parent code + next symbol can answer this efficiently. Once the extension is absent, the current phrase code is emitted and the extension receives the next dictionary code.

The search domain is phrase vocabulary, not every position in a sliding window.

61. LZW Phrase Growth Can Capture Long Repetition Incrementally

A phrase of length ten may never be inserted all at once. It emerges through a sequence of extensions learned from previous parsing. Common short patterns become nodes from which longer patterns grow.

This hierarchical phrase growth is efficient when the source repeatedly reuses expanding sequences. It can be slow to adapt when long phrases appear only once.

Dictionary compression benefits from recurrence, not merely length.

62. Phrase Codes Become Valuable Only After Reuse

Creating a dictionary entry does not itself save bits. The entry earns its cost when later input can be represented by its code more cheaply than by smaller pieces.

A dictionary full of one-use phrases consumes memory and wider codes without producing repeated savings. This is why stale-entry management matters in bounded variants.

A useful dictionary is not a museum of everything seen; it is a working vocabulary that receives repeat traffic.

63. Dictionary Saturation Can Degrade Compression

Once a fixed-size LZW dictionary is full, a format may freeze it. If the source distribution later changes, no new phrases can be learned while wide codes continue to represent old entries.

Resetting can restore adaptation but sacrifices old vocabulary. Some systems monitor compression effectiveness and reset when performance deteriorates.

The right forgetting policy depends on source stability.

64. Dictionary Reset Is Analogous to Model Reset in PPM

PPM can reset context statistics; LZW can clear phrase entries. Both actions trade accumulated knowledge for faster adaptation and lower state cost.

The analogy stops at the representation: PPM forgets probability counts, while LZW forgets numbered phrase vocabulary. But both face the same system question: when does old history stop paying rent?

Adaptive compression is also memory governance.

65. LZ77 Uses Distance as Recency; LZW Uses Code Age Indirectly

In LZ77, recency is explicit: distance measures how far back the source lies. In an LZW dictionary, a code number often correlates with creation time because entries are added sequentially, but the code itself usually does not encode physical stream distance.

An old LZW phrase can remain cheaply accessible if its code width is unchanged. An old LZ77 phrase becomes illegal once it falls outside the window.

The two methods make different assumptions about which past structure remains useful.

66. Repetition Can Be Exact Without Being Semantically Related

Two byte strings can match exactly even if one occurs in a header and the other inside unrelated binary data. LZ77 will happily reference the bytes. LZW will happily reuse a phrase if its parse reaches the same sequence.

Compression is syntactic at this layer. It exploits equality, not meaning.

This is why transformations that preserve values but alter byte representation can change compressibility dramatically.

67. Whitespace Can Matter

Pretty-printed JSON repeats indentation and line breaks, which are highly compressible, but also increases raw size. Minified JSON removes those bytes but may slightly change match structure. The compressed result is not always proportional to raw size.

Similarly, normalizing line endings or whitespace can improve or reduce repetition. If the transform is not reversible or changes the original file, it is no longer transparent lossless compression of the exact source.

Representation choices alter the dictionary the compressor sees.

68. Structured Data Creates Repeated Keys and Shapes

JSON, XML, logs and CSV files often repeat field names, delimiters and record schemas. LZ77 can match entire repeated key sequences; LZW can build phrase codes around recurring fragments.

Random IDs, timestamps and checksums break long matches, but stable prefixes and separators remain useful. Reordering fields consistently can increase recurrence.

Compression reveals regularity in data representation even when values differ.

69. Source Code Is Dictionary-Friendly

Programming languages repeat keywords, indentation, punctuation, type names, API calls and naming prefixes. Projects also repeat boilerplate and templates across files.

A sliding dictionary can reference long repeated code fragments; explicit phrase dictionaries can learn common token-like character sequences.

The compressor does not parse the programming language to benefit from its grammar, although language-aware preprocessing can expose additional structure.

70. Executables Mix Repetition With Hard Regions

Machine code contains recurring instruction patterns, zero-filled regions, alignment and repeated data structures. It also contains addresses, relocations and already-compressed resources that disrupt matches.

Specialized executable compressors may preprocess addresses or instruction streams to improve locality before applying LZ-style compression.

Again, reversible transformation can make a dictionary’s job easier.

71. Images Need Representation-Level Repetition

Raw raster images can contain repeated pixel bytes, but direct LZ compression is often less efficient than applying predictors or filters first. PNG’s reversible filtering makes neighboring pixel structure appear as smaller, more repetitive residual values before DEFLATE.

GIF’s indexed-color representation can create repeated index sequences that LZW captures effectively, especially for flat-color graphics and patterns.

Compression quality depends on the representation presented to the dictionary.

72. Audio and Video Usually Need Domain-Specific Front Ends

Raw audio and video contain correlation, but modern codecs exploit prediction, transforms, quantisation and perceptual models far beyond generic LZ matching. Lossless audio codecs also use signal predictors that turn samples into lower-entropy residuals.

Generic LZ compression may still appear around metadata or uncompressed structures, but it is not the core mechanism of modern lossy media coding.

A general-purpose dictionary is not automatically the best model for every domain.

73. LZ77 Can Be Combined With Many Entropy Coders

DEFLATE pairs LZ77-style tokens with Huffman coding. LZMA pairs an LZ-style dictionary with adaptive probability models and range coding. Zstandard uses LZ-style sequences with entropy coding tailored to its format.

The dictionary stage transforms raw bytes into a more compressible symbolic stream; the entropy stage exploits frequency differences among those symbols.

This modularity explains why “LZ77” can underlie many formats with very different compression ratios and speeds.

74. LZW Often Uses Fixed or Expanding Integer Codes Directly

Classic LZW does not require a separate Huffman stage to be intelligible. The dictionary code stream itself is already a variable-to-fixed or variable-to-variable representation depending on code-width policy.

Additional entropy coding can sometimes compress the code stream further, but it complicates the system. Historical applications valued LZW’s self-contained dictionary coding.

The algorithm family and format determine whether a second coding layer is worthwhile.

75. Why LZW Can Expand Incompressible Data

If the source rarely reuses phrases, the dictionary fills with entries that are not revisited. Code width grows while phrases remain short. The output can become larger than the original.

Smart wrappers can monitor performance and reset or store raw data. But pure LZW by itself does not guarantee size reduction on every input.

Lossless universal coding guarantees decodability, not universal compression of every finite file.

76. Why LZ77 Can Also Expand Data

On data with no profitable matches, the encoder emits literals plus block and entropy-coding overhead. If literal codes average more than eight bits after framing, output grows.

DEFLATE addresses this at block level by allowing uncompressed stored blocks. Other formats have analogous raw modes.

A practical codec needs an escape from compression itself.

77. Minimum Match Length Is a Cost Threshold

Why not encode a distance–length pair for any repeated two bytes? Because the reference has overhead. A minimum match length approximates the point at which a match begins to compete with literal coding.

The true break-even point depends on the entropy codes for literals, lengths and distances. Sophisticated parsers compute cost more accurately than a fixed heuristic.

Minimum length is an economic rule disguised as a format parameter.

78. Distance Cost Can Change With Block Statistics

In dynamic entropy-coded formats, a distance used frequently in one block can become cheaper than another through shorter entropy codes. The best parse can therefore depend on token frequencies that the parse itself helps create.

This circularity makes globally optimal encoding more difficult. Encoders estimate costs, parse, update statistics and sometimes iterate.

The dictionary family sets candidate references; the parser and entropy model determine which references are worth buying.

79. Repeat Offsets Are a Modern Refinement

Some modern LZ formats remember recently used distances so they can be represented with very cheap special codes. This exploits the fact that nearby structured data often repeats with the same stride—for example, fields across records.

Zstandard explicitly defines recent offsets and sequence components of literal length, offset and match length. These are descendants of the LZ77 reference idea, refined for modern coding efficiency.

The fourth article will use such formats to show how parse cost differs from raw match length.

80. LZMA Extends the LZ77 Branch Rather Than the LZW Branch

Despite the shared “LZ” prefix, LZMA is conceptually closer to LZ77’s sliding-dictionary phrase references than to LZW’s numbered phrase dictionary. It finds matches in previous output, models literals/matches/lengths/distances probabilistically, and range-codes the decisions.

The third article in this batch owns that combined machine in depth.

Family names are historical clues; mechanism boundaries matter more.

81. The Lempel–Ziv Family Is Universal in a Technical Sense

The original theoretical work established universal coding properties: the methods can asymptotically approach strong compression performance for broad classes of sources without knowing the source probability model in advance.

“Universal” does not mean every finite file shrinks, every implementation is optimal, or one parameter setting dominates all data.

It refers to asymptotic source-coding behaviour under formal assumptions, not magical finite-file superiority.

82. LZ77 Teaches Recency as Memory

The sliding window says recent history is valuable because it can be copied cheaply and bounded memory is practical. Old history eventually disappears from consideration even if it might contain useful matches.

This is a deliberate engineering compromise. The algorithm sacrifices infinite memory to gain streaming and bounded resource use.

Recency becomes an address space for repetition.

83. LZ78 Teaches Vocabulary as Memory

LZ78 says useful history can be distilled into phrases rather than raw recent bytes. Each new phrase extends a previous phrase and receives a reusable identity.

The dictionary is therefore a compressed memory of recurring sequence structure. It does not preserve every location where a phrase appeared; it preserves the phrase itself.

The representation of memory changes what can be referenced cheaply.

84. LZW Teaches Implicit Shared State

The sender does not transmit each new dictionary entry. The receiver infers it from prior codes and the construction rule. That is a striking form of protocol compression: shared deterministic state eliminates metadata.

The benefit comes with fragility. One code-width mismatch or corrupted code can desynchronise dictionary state and ruin the remaining stream.

Implicit state saves bits because both sides agree on the same machine.

85. Error Corruption Can Propagate

If an LZ77 token is corrupted, the decoder may copy the wrong bytes. Future references can then point into already corrupted output. In LZW, one wrong code can change dictionary entries and cause continuing divergence.

Containers add checksums, block boundaries and integrity checks to detect damage. Network stacks add lower-layer protection.

Compression reduces redundancy that might otherwise help error recovery, so robustness usually comes from separate mechanisms.

86. Decompression Bombs Exploit Expansion Ratios

A small compressed input can legitimately expand into enormous output if it encodes long repetitions efficiently. Malicious archives can exploit this to exhaust disk, memory or CPU.

Safe systems impose output-size, nesting and resource limits before fully trusting compressed data. The decoder should treat declared or implied expansion as untrusted.

High compression ratio is beneficial until the receiver did not consent to the expanded workload.

87. Compression Can Create Length Side Channels

If attacker-controlled input and secret data are compressed together, a correct guess can create a longer match or phrase and change the compressed length. Observing that length can leak information even if the compressed output is later encrypted.

Security-sensitive protocols therefore need separation, padding or disabled compression around secrets. Dictionary sharing is a compression benefit and potentially an information-flow channel.

Shared context should be treated as shared state with security consequences.

88. Patent History Affected Deployment

LZW was historically associated with patents that affected software and image-format ecosystems. Those patents have long expired, but the episode influenced engineering choices and public perception of formats such as GIF.

The important technical lesson is separate: algorithm adoption depends not only on compression quality but also on legal, licensing, interoperability and ecosystem constraints.

A technically elegant codec can lose deployment share for reasons outside information theory.

89. GIF Survived Beyond the Patent Era

GIF’s continuing use is not proof that LZW remains the best general image compressor. Format survival depends on installed software, browser support, animation conventions and ecosystem inertia.

PNG often compresses static lossless graphics better and supports richer color and alpha, while modern animation/video formats can be far more efficient for moving imagery. Yet GIF persists because interoperability has value.

Compression formats are socio-technical standards as well as algorithms.

90. Why DEFLATE Persists

DEFLATE is not the newest or highest-ratio general-purpose compressor, yet it remains deeply embedded because decoders are ubiquitous, implementations are mature, memory demands are modest and formats such as ZIP, gzip and PNG depend on it.

Compatibility can outweigh marginal compression gains. Replacing a codec means replacing an ecosystem of hardware, libraries, standards and stored archives.

The LZ77 branch became infrastructure, not merely an algorithm lesson.

91. Why Modern Codecs Still Look Lempel–Ziv-Like

Zstandard, Brotli, LZMA and many others still represent repeated sequences through references to earlier data, then improve match search, distance coding, entropy coding, context modeling, block structure and parallelism.

The fundamental abstraction remains attractive because copy references are cheap to decode and real data contains repeated substrings at many scales.

Modern compression often looks less like replacing LZ77 than building a more sophisticated machine around it.

92. LZ77 Versus PPM: Copy or Predict?

Prediction by Partial Matching gives probabilities to next symbols based on context. LZ77 searches for exact repeated strings and emits copy references.

PPM can benefit when a context strongly predicts a symbol even if the exact long phrase never recurs. LZ77 can benefit enormously when a long phrase repeats exactly even if character probabilities around it are otherwise complicated.

Both exploit history, but one turns history into a probability distribution and the other into an addressable copy source.

93. LZ77 Versus CTW: Reference or Weighted Context

Context Tree Weighting recursively combines predictions from context trees. It models conditional probability rather than outputting explicit copy distances.

CTW is mathematically elegant for context prediction; LZ77 is mechanically direct for phrase reuse. Their performance depends on what redundancy the source provides.

There is no single universal representation of redundancy.

94. LZW Versus Huffman Coding: Phrase Learning or Frequency Coding

Huffman coding assigns shorter bit strings to more frequent symbols from a defined alphabet. LZW changes the alphabet itself by adding phrases and giving them codes.

A Huffman coder can be applied to literals and match symbols after an LZ transform, as DEFLATE demonstrates. The stages solve different problems.

See How Compression Works | Entropy Coding for the separate frequency-coding owner.

95. LZMA Versus LZW: Similar Prefix, Different Machine

LZW is an explicit phrase-code dictionary descendant of LZ78. LZMA is a sliding-dictionary match compressor descended from LZ77-style ideas, augmented with adaptive probability models and range coding.

They should not be grouped together merely because both begin with “LZ.” The history traces back to Lempel and Ziv; the mechanics differ sharply.

The next article separates the LZMA pipeline in detail.

96. A Useful Mental Model for LZ77

Imagine writing a document while being allowed to say “copy the next 40 characters from 800 characters ago.” Your previous output is the dictionary. You never name phrases permanently; you address them by where they currently live in the allowed history.

When the phrase falls outside the window, it stops being addressable. When the same pattern appears nearby, it becomes cheap again.

That is the sliding-window intuition.

97. A Useful Mental Model for LZ78

Imagine building a numbered phrasebook while reading. Every new phrase must be made by taking a phrase already in the book and appending one new symbol. You transmit the old phrase number and the new symbol, then add the combined phrase to the book.

The receiver follows the same instructions and therefore owns the same phrasebook without receiving it separately.

That is the incremental-dictionary intuition.

98. A Useful Mental Model for LZW

Imagine the phrasebook already contains every one-character word. You always transmit the number of the longest phrase currently in the book. Each transmission also gives both sides enough information to infer one new longer phrase.

The explicit “plus one new character” field disappears from the stream because code adjacency determines it.

That is LZW’s elegant refinement.

99. The Lempel–Ziv Engineering Audit

1. Which family is actually in use: LZ77-like, LZ78-like or LZW?
2. What is the source alphabet—bytes, symbols, palette indexes?
3. For LZ77, what is the maximum backward distance?
4. What is the minimum and maximum match length?
5. Are overlapping copies legal?
6. How are literals represented?
7. How are length and distance values represented?
8. What entropy coder follows the match stage?
9. What match-finding structure does the encoder use?
10. How deep is candidate search at each compression level?
11. Does the parser use greedy, lazy or optimal decisions?
12. Where are block/reset boundaries?
13. Can matches cross blocks?
14. What random-access granularity is required?
15. For LZW, what entries exist initially?
16. How does code width grow?
17. When is the dictionary cleared or frozen?
18. How is the special “next code” case decoded?
19. What integrity checks surround the compressed stream?
20. What happens when compression would enlarge the data?

100. Misconception: LZ77 Has One Fixed Token Format

No. The family is defined by backward-reference phrase reuse, not one universal tuple. Textbooks, LZSS, DEFLATE, Zstandard, Brotli and LZMA use different token grammars and coding layers.

Always distinguish the family concept from the concrete file format.

101. Misconception: LZ78 and LZW Are the Same Algorithm

LZW descends from LZ78 but changes the stream representation and dictionary procedure. LZ78 classically emits known-phrase index + next symbol. LZW starts with base symbols in the dictionary and emits dictionary codes while inferring new entries from code transitions.

The distinction matters for implementation and decoding.

102. Misconception: LZ77 Needs to Store Every Substring

No. The history bytes implicitly contain every substring. Match-finding indexes help locate candidates without materializing every substring as a dictionary entry.

The search structure is an index over the dictionary, not the dictionary itself.

103. Misconception: The Longest Match Is Always Best

No. Distance cost, length cost, literal cost and future match opportunities can make a shorter match or even a literal produce a smaller total stream.

This is why parsing deserves its own canonical article.

104. Misconception: Dictionary Compression Requires a Preloaded Dictionary

Classic Lempel–Ziv methods are powerful precisely because the useful dictionary is reconstructed from the stream. External preset dictionaries can improve some formats, but they are an optional extension, not the core idea.

The message teaches the receiver its own repeated vocabulary.

105. Misconception: LZW Is an Image-Only Algorithm

No. LZW is a general lossless dictionary method. GIF and TIFF are famous applications, but Welch presented the technique as a general high-performance adaptive compression approach.

The file format determines what symbols LZW receives.

106. Misconception: Better Compression Means Better for Every System

A higher ratio can cost CPU, memory, latency, energy or random access. A legacy codec can remain preferable when hardware support, interoperability or decompression speed dominates.

Choose the codec for the receiver and workload.

107. Research Basis and Further Reading

• Jacob Ziv & Abraham Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Transactions on Information Theory, 1977 — foundational LZ77 paper.
• Jacob Ziv & Abraham Lempel, Compression of Individual Sequences via Variable-Rate Coding, IEEE Transactions on Information Theory, 1978 — foundational LZ78 paper.
• Terry A. Welch, A Technique for High-Performance Data Compression, IEEE Computer, 1984 — foundational LZW article.
• RFC 1951, DEFLATE Compressed Data Format Specification — concrete LZ77 + Huffman descendant defining literals, lengths, backward distances and block coding.
• How Compression Works | Prediction by Partial Matching — statistical-context contrast.
• How Compression Works | Context Tree Weighting — context-tree contrast.
• How Compression Works | Entropy Coding — separate owner for Huffman, arithmetic and related coding principles.

108. Frequently Asked Questions

What is LZ77?

LZ77 is a family of lossless dictionary compression methods that replace repeated substrings with references to recently decoded data, typically represented by a backward distance and match length.

What is LZ78?

LZ78 builds an explicit growing phrase dictionary. A new phrase is formed from an existing dictionary phrase plus a new symbol and is represented using the known phrase index and that symbol.

What is LZW?

LZW is Terry Welch’s refinement of the LZ78 approach. It starts with the base alphabet in the dictionary, emits phrase codes and lets encoder and decoder infer new phrase entries from the sequence of codes.

Is DEFLATE the same as LZ77?

No. DEFLATE is a specific format that combines an LZ77-style sliding-window match stage with Huffman coding and defined block, length and distance rules.

Does GIF use LZW?

Yes. GIF image data uses an LZW-based coding scheme with format-specific clear, end and code-width rules.

Why can LZ77 matches overlap?

Because copied output becomes available as source while the match is being reproduced. This allows short periodic seeds to generate long repeated runs.

Why is LZW dictionary reset useful?

A full dictionary may contain stale phrases and require wide codes. Resetting returns to a small dictionary and lets the model adapt to a changed source, at the cost of forgetting useful old phrases.

Why doesn’t every file compress?

Dictionary methods need repeated structure whose reference costs less than the literals. Random, encrypted or already-compressed data often lacks profitable repetition.

Is LZMA a form of LZW?

No. LZMA belongs to the LZ77-style sliding-dictionary branch and combines match references with adaptive probability models and range coding.

109. The Larger Idea

Lempel–Ziv compression changed the question.

Before asking how frequently each symbol appears, it asks whether a whole sequence has already been paid for.

LZ77 says the earlier sequence still exists in recent output, so point back to it.

LZ78 says recurring sequences can become a numbered vocabulary.

LZW says that vocabulary can grow implicitly, code by code, without sending each new phrase definition.

All three exploit a deeper system fact: sender and receiver share the same reconstructed past.

Once that past becomes addressable, repetition stops being new information.

The engineering differences—window or phrasebook, distance or code, reset by age or explicit clear—are different answers to one design problem: what form of memory makes repeated structure cheapest to name?

Compression gets powerful when the receiver can reconstruct not only the data, but the memory needed to describe the rest of the data more cheaply.