CoreSource checked

LZ78

Compresses by emitting dictionary references while growing a phrase dictionary from the input stream.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Compression
Difficulty: Intermediate
Family: Dictionary Compression
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 0
Relationships: 4
Code example: Ready
Visualization: Ready

Overview

LZ78 reads the longest phrase already in the dictionary, emits its dictionary index plus the next symbol, and adds the longer phrase to the dictionary.

Core Concepts

dictionary compressioncompression

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1)

Average

O(log n)

Worst

O(n)

Space

O(n)

When to Use

Use it when an adaptive dictionary should be learned from the stream.
Use it to understand phrase-dictionary compression.
Use modern descendants or formats for production compression.

When Not to Use

Avoid it when small inputs make dictionary overhead larger than the savings.
Avoid it when a sliding-window LZ77-style reference is required by the format.
Avoid encoder and decoder dictionary update mismatches.

What It Does

Builds a dictionary of phrases
Emits index-and-symbol pairs for repeated structure

Use Cases

Dictionary compression
Teaching Lempel-Ziv family methods
Streams with repeated phrases

Inputs

Input byte or symbol stream
Model, dictionary, or coding parameters

Outputs

Compressed representation
Updated model or dictionary state

Pseudocode

1.Preprocess the input alphabet, pattern/grammar rules, or symbol frequency tables for LZ78.
2.Construct the lookup automaton, suffix/shift index, or coding state (dictionary compression, compression).
3.Scan the input sequence by Compresses by emitting dictionary references while growing a phrase dictionary from the input stream.
4.Emit matches, derivation nodes, or encoded tokens while advancing the state transition table.
5.Finalize trailing state and return the completed dictionary compression output.

Canonical Example

Input: text = "ABABABA"
Output: a sequence of phrase indexes and next symbols
Explanation: As phrases like A, B, and AB enter the dictionary, later repetitions can be represented by indexes.

Implementation Notes

Initialize the dictionary and grow it in exactly the same order during encoding and decoding.
Emit a pair containing the matched phrase index and next symbol.
Define dictionary reset or code-width growth behavior.

Common Pitfalls

Updating the encoder and decoder dictionaries at different times.
Failing to handle the final phrase when the stream ends.
Letting dictionary indexes outgrow the chosen code width without a reset policy.