Dictionary coding: replacing repeats with references
Dictionary coding is the family of lossless compression methods that works by finding repeated sequences in the data and replacing later occurrences with a short reference to a "dictionary" rather than writing them out again. It is the unifying idea behind most fast general-purpose compressors: LZ77, LZ78 and LZW, DEFLATE, and LZMA are all dictionary coders under the hood, differing mainly in what the dictionary is and how it is searched.
The intuition is simple: text and code are full of repeated words and patterns. Instead of storing "compression" ten times, a dictionary coder stores it once in its dictionary and thereafter writes a short token meaning "that word again." The compression comes from trading long repeats for short tokens — and the richer or more adaptive the dictionary, the better the compression ratio.
What counts as the dictionary
The "dictionary" is not always a literal table you can point at. It can be one of three things. It can be an implicit sliding window — the last N bytes of recently processed data, which is the LZ77 approach and the one ZIP’s DEFLATE uses. It can be an explicit, growing table of strings built as the compressor runs, which is the LZ78/LZW approach. Or it can be a static, built-in dictionary shipped with the codec — common in web compressors like brotli, which carries a large dictionary of typical web text so even the first occurrence of a common phrase can be a token.
These are not academic distinctions; they drive real performance differences. A sliding window adapts to whatever data you feed it but starts empty, so short inputs gain little. A built-in dictionary helps small web payloads immediately but adds weight to the codec. An explicit string table (LZW) was historically compact to implement but tends to give weaker ratios than modern sliding-window designs.
Sliding window vs explicit table
The deepest split in the family is between LZ77 and LZ78. [LZ77](/glossary/lz77) uses an implicit sliding window and emits (distance, length) back-references — "copy these bytes from N bytes ago." Its dictionary is the data itself, so it needs no separate table and adapts locally, but a reference can only reach as far back as the window (32 KB in DEFLATE). LZ78/LZW build an explicit table of encountered strings and emit table indices; the table grows as new strings are seen, which is compact but eventually needs pruning and tends toward worse ratios.
Modern general-purpose compressors overwhelmingly chose the LZ77 side. DEFLATE, gzip, LZMA, zstd, and brotli are all sliding-window designs (brotli adds the built-in static dictionary on top). The reason is practical: a sliding window gives better ratios on general data, maps cleanly onto a fast entropy-coding second stage, and avoids the table-management complexity of LZW. The lossless guarantee is identical either way.
Dictionary coding and entropy coding
A dictionary coder is rarely the whole story. It produces a stream of tokens — literals and references, or table indices — and those tokens are then handed to an entropy coder (Huffman coding in DEFLATE, range coding in LZMA) that packs them into the fewest bits by giving common tokens short codes. The dictionary stage removes redundancy at the sequence level; the entropy stage removes redundancy at the symbol level. Together they are the two halves of nearly every modern lossless compressor.
This is why you cannot rank compressors by one number. DEFLATE and LZMA are both dictionary + entropy coders, yet LZMA reaches a much better ratio because its window is larger, its match search is more thorough, and its entropy stage (range coding with context modeling) squeezes harder than Huffman. The dictionary-coding skeleton is the same; the muscle on top differs.
Why the family matters for archives
Almost every archive format leans on a dictionary coder, because files are repetitive and dictionary methods exploit that well. ZIP uses DEFLATE (LZ77 + Huffman); 7z typically uses LZMA (a larger, smarter LZ77 plus range coding); the gzip layer of tar.gz is DEFLATE again. Knowing the shared skeleton makes their tradeoffs legible: bigger window and better search mean better ratio at the cost of speed, and a solid archive that compresses many files together lets the dictionary find matches across files instead of resetting per entry.
Frequently asked questions
What is dictionary coding?
Dictionary coding is a family of lossless compression methods that replaces repeated byte sequences with short references to a dictionary instead of writing them out again. The dictionary may be an implicit sliding window of recent data (LZ77), an explicit growing table of strings (LZ78/LZW), or a built-in static table (brotli). DEFLATE, LZMA, gzip, zstd, and brotli are all dictionary coders.
What is the difference between LZ77 and LZ78?
LZ77 uses an implicit sliding window over recently processed bytes and emits (distance, length) back-references; its dictionary is the data itself, so it needs no separate table but can only reference as far back as the window. LZ78 builds an explicit, growing table of encountered strings and emits table indices. Modern compressors overwhelmingly use the LZ77 approach, which gives better ratios on general data.
Is DEFLATE a dictionary coder?
Yes. DEFLATE’s first stage is an LZ77 dictionary coder with a 32 KB sliding window that turns the input into literals and match tokens; its second stage is Huffman entropy coding that packs those tokens. So a ZIP entry is decompressed by reversing a dictionary-coding stage followed by an entropy stage.
What is a static or built-in dictionary?
A dictionary that ships with the codec rather than being built from your data. Brotli carries a large built-in dictionary of common web text, so even the first occurrence of a frequent phrase can be encoded as a short token. This helps small payloads that would gain little from a sliding window that starts empty, at the cost of a heavier codec.
How does dictionary coding relate to entropy coding?
They are sequential stages. The dictionary coder removes redundancy at the sequence level, producing a stream of tokens (literals and references or table indices), and the entropy coder then removes redundancy at the symbol level by giving common tokens short codes (Huffman or range coding). Nearly every modern lossless compressor, from DEFLATE to LZMA, is dictionary coding followed by entropy coding.