Overview
LZSS improves on basic LZ77 encoding by emitting a flag that says whether the next item is a literal or a length-distance reference.
CoreSource checked
LZSS
Compresses by choosing between literal bytes and LZ77-style back-references.
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
- 2
- Code example
- Ready
- Visualization
- Ready
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 repeated substrings should become back-references but literals must remain cheap.
- Use it as a clear LZ77-family teaching implementation.
- Use format-specific variants when interoperability matters.
When Not to Use
- Avoid it when entropy coding or modern compression ratio is required.
- Avoid it when window search cost dominates and no match finder is available.
- Avoid ambiguous flag and token framing.
What It Does
- Encodes literals and back-references
- Avoids references that would cost more than literals
Use Cases
- Dictionary compression
- Simple LZ-family compressors
- Teaching literal/reference tradeoffs
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 LZSS.
- 2.Construct the lookup automaton, suffix/shift index, or coding state (dictionary compression, compression).
- 3.Scan the input sequence by emitting a flag that says whether the next item is a literal or a length-distance reference.
- 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 = "ABCABC"
- Output
- literals for ABC followed by a reference to the earlier ABC
- Explanation
- The repeated suffix can be encoded as a length-distance pair instead of three more literals.
Implementation Notes
- Search the recent window for a useful match.
- Emit a literal when the match is too short to pay for its token.
- Keep window updates identical in the encoder and decoder.
Common Pitfalls
- Emitting a back-reference that is larger than the literal sequence it replaces.
- Letting encoder and decoder disagree on window position.
- Failing to bound distance and length fields.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow encoding repeated substrings as offset-length references on a small dictionary compression example.
Input:ABABABCABAB
Window:ABAB
Step 1 of 5: Preprocess the input alphabet, pattern/grammar rules, or symbol frequency tables for LZSS.
compression-mechanismNotes
LZSS operates in O(log n) time and O(n) space within the Dictionary Compression family. Often compared with Cuckoo Hashing and Hash-DRBG.
Sources (2)
What each reference supports for this entry.
Introduction to Data Compression
BookCompression textbook support for LZSS's coding model, decoder behavior, and implementation tradeoffs.
Open sourceStorer-Szymanski Textual Substitution
PaperOriginal LZSS reference for textual substitution, literal/reference decisions, and dictionary phrase replacement.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageRelated Algorithms
Tags
CompressionStrings