Overview
Variable-length encoding saves space when symbol frequencies are uneven, provided the code can be decoded unambiguously.
CoreSource checked
Variable-Length Encoding
Represents common values with shorter codes and uncommon values with longer codes.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Compression
- Difficulty
- Beginner
- Family
- Entropy Coding
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
Core Concepts
codeword lengthsymbol frequencyprefix-free decodingbit packing
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(k)
When to Use
- Use when reducing storage size needs codeword length.
- Use when the input matches the assumptions behind entropy Coding.
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
- Represents common values with shorter codes and uncommon values with longer codes
- Uses codeword length and symbol frequency 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)
Expected code length
E[length] = sum p(symbol) · codelength(symbol)
E[length] = sum p(symbol) * code_length(symbol)Estimates average bits per encoded symbol.
Pseudocode
- 1.Initialize encoder state, dictionary, model, or block metadata
- 2.Read symbols or blocks in the defined order
- 3.Emit codes, references, predictions, or transformed coefficients
- 4.Update encoder state exactly as the decoder will
- 5.Return the compressed stream and required metadata
Canonical Example
- Input
- Variable-Length Encoding
- Output
- Encoded stream
- Explanation
- Variable-Length Encoding applies codeword length to produce encoded stream.
Implementation Notes
- Define bit packing and stream termination rules before optimizing compression ratio.
- Keep the codeword length step separate enough to test independently.
- Compression can expand small or already-compressed inputs because metadata has a cost.
Common Pitfalls
- Encoder and decoder state must evolve in exactly the same order.
- Test edge cases, not only clean examples.
- Encoder and decoder state must stay synchronized across dictionary updates, blocks, and metadata boundaries.
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 5: Initialize encoder state, dictionary, model, or block metadata
compression-mechanismNotes
Variable-Length Encoding should be used with the assumptions and tradeoffs of entropy Coding in mind.
Sources (1)
What each reference supports for this entry.
Introduction to Data Compression
BookCompression textbook support for Variable-Length Encoding's coding model, decoder behavior, and implementation tradeoffs.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Often paired withDelta Encoding
Compression · Core
Small deltas are often compacted with variable-length codes.
Compare with thisOften paired withBit-Packing
Compression · Extended
Bit packing is often used alongside compact integer encodings.
Compare with thisRelationships
View full relationship pageGeneralizesElias Delta Coding
Elias delta coding is one variable-length integer code.
GeneralizesElias Gamma Coding
Elias gamma coding is one variable-length integer code.
Related Algorithms
Tags
CompressionEncodingPrefix CodeBit Level