Overview
Deflate encodes repeated byte sequences as length-distance pairs and then entropy-codes literals and pairs with Huffman codes. Encoder and decoder process blocks with shared code descriptions.
CoreSource checked
Deflate
Compresses data by combining LZ77 backreferences with Huffman-coded symbols.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Compression
- Difficulty
- Intermediate
- Family
- Lossless Compression
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 5
- Code example
- Not ready
- Visualization
- Ready
Core Concepts
dictionary referenceprobability modelcodeword encodinglossless compressionsymbol representationlossless decodingstream encoding
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(nw)
Space
O(w)
When to Use
- Use when a widely supported lossless compression format is needed.
- Use when repeated substrings and entropy coding can both reduce size.
When Not to Use
- Avoid expecting gains on already-compressed or encrypted data.
- Avoid when very low latency matters more than compression ratio.
What It Does
- Finds repeated substrings with an LZ77-style window
- Emits literals or length-distance references
- Huffman-codes block symbols for compact storage
Use Cases
- General-purpose lossless byte compression
- Formats such as gzip and zlib streams
- Compressing data with repeated local structure
Inputs
- Byte stream
Outputs
- Deflate compressed stream
Key Formulas (1)
Length-distance copy
output[position + i] = output[position − distance + i] for i = 0…length−1
output[position + i] = output[position - distance + i] for i = 0..length-1Expands an LZ77-style copy token during decompression.
Pseudocode
- 1.Split input into blocks
- 2.Search the sliding window for repeated byte sequences
- 3.Emit literals or length-distance pairs
- 4.Build or choose Huffman codes for block symbols
- 5.Write block metadata and coded symbols
Canonical Example
- Input
- bytes for 'ABCABCABC'
- Output
- literal 'ABC' followed by length-distance references plus coded metadata
- Explanation
- The repeated suffix can be represented as references to earlier bytes and then entropy-coded.
Implementation Notes
- Keep literal, length, distance, and block metadata handling separate.
- Test dynamic and fixed Huffman blocks independently.
- Validate streams with round-trip encode/decode tests.
Common Pitfalls
- Encoder and decoder must agree on block boundaries and Huffman tables.
- Small inputs can grow because headers and tables have overhead.
- Window-size limits restrict how far back matches can refer.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow repeated text becoming references and then shorter bit codes.
Input:ABABABCABAB
Window:ABAB
Step 1 of 5: Split input into blocks
compression-pipelineNotes
Deflate is lossless; compression ratio depends heavily on match finding and block modeling.
Sources (2)
What each reference supports for this entry.
RFC 1951
DocumentationSpecification for Deflate blocks, LZ77 references, and Huffman-coded literals/distances.
Open sourceIntroduction to Data Compression
BookCompression textbook support for Deflate's coding model, decoder behavior, and implementation tradeoffs.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageUsesLZ77
Deflate uses LZ77-style length-distance references.
UsesHuffman Coding
Deflate entropy-codes literals and match symbols with Huffman codes.
Related Algorithms
Tags
CompressionDictionary CompressionEntropy CodingEncoding