Overview
LZMA searches for repeated sequences in a large dictionary and encodes match decisions with adaptive probability models.
ExtendedSource checked
LZMA
Compresses data with LZ-style matches and range-coded probability models.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Compression
- Difficulty
- Advanced
- Family
- Dictionary Compression
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
dictionary matchrange codingadaptive probabilityliteral context
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n log n)
Space
O(window)
When to Use
- Use when reducing storage size needs dictionary match.
- Use when the input matches the assumptions behind dictionary Compression.
When Not to Use
- Avoid when the data is already compressed or the format overhead exceeds the savings.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Compresses data with LZ-style matches and range-coded probability models
- Uses dictionary match and range coding to guide the work.
- Produces encoded stream.
Use Cases
- Reducing storage size
- Compressing repeated data
- Preparing data for transmission
Inputs
- Input byte stream
- Coding model or dictionary state
Outputs
- Encoded stream
- Decoder metadata
Key Formulas (1)
Match reference
copy(length, distance)
copy(length, distance)Represents repeated bytes by length and distance into the dictionary.
Pseudocode
- 1.Prepare the inputs and state needed for LZMA.
- 2.Apply the dictionary match step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return encoded stream.
Canonical Example
- Input
- LZMA input with a small representative case
- Output
- Encoded stream
- Explanation
- LZMA applies dictionary match to produce encoded stream.
Implementation Notes
- Define bit packing and stream termination rules before optimizing compression ratio.
- Keep the dictionary match step separate enough to test independently.
Common Pitfalls
- Encoder and decoder state must evolve in exactly the same order.
- Forgetting to check edge cases can make LZMA look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow symbols being transformed into codes and reconstructed by the decoder state.
Input:ABABABCABAB
Window:ABAB
Step 1 of 4: Prepare the inputs and state needed for LZMA.
compression-mechanismNotes
LZMA should be used with the assumptions and tradeoffs of dictionary Compression in mind.
Sources (2)
What each reference supports for this entry.
LZMA SDK
DocumentationOfficial SDK documentation for LZMA dictionary compression, range coding, and implementation details.
Open sourceData Compression: The Complete Reference
BookCompression reference for LZMA LZ-style dictionary compression and range-coding context.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborLZ77
LZMA builds on dictionary match ideas in the LZ family.
Alternative toZstandard Compression
Both are general-purpose compressors with different speed and ratio tradeoffs.
Related Algorithms
Tags
CompressionDictionary CompressionEntropy CodingPredictive Coding