Overview
Elias gamma coding is compact for small positive integers and does not require a separate probability model.
ExtendedSource checked
Elias Gamma Coding
Encodes positive integers with a unary length prefix and binary payload.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Compression
- Difficulty
- Intermediate
- Family
- Universal Integer Coding
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
universal codeunary prefixbinary payloadpositive integer
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(log n)
Average
O(log n)
Worst
O(log n)
Space
O(1)
When to Use
- Use when reducing storage size needs universal code.
- Use when the input matches the assumptions behind universal Integer 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
- Encodes positive integers with a unary length prefix and binary payload
- Uses universal code and unary prefix 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)
Gamma code length
length(n) = 2 · ⌊log2(n)⌋ + 1
length(n) = 2 * floor(log2(n)) + 1Counts unary length bits plus the remaining binary payload bits.
Pseudocode
- 1.Prepare the inputs and state needed for Elias Gamma Coding.
- 2.Apply the universal code step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return encoded stream.
Canonical Example
- Input
- Elias Gamma Coding input with a small representative case
- Output
- Encoded stream
- Explanation
- Elias Gamma Coding applies universal code to produce encoded stream.
Implementation Notes
- Define bit packing and stream termination rules before optimizing compression ratio.
- Keep the universal code 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 Elias Gamma Coding 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 Elias Gamma Coding.
compression-mechanismNotes
Elias Gamma Coding should be used with the assumptions and tradeoffs of universal Integer Coding in mind.
Sources (2)
What each reference supports for this entry.
Elias Universal Codes
PaperReference for universal codeword sets including Elias-style integer codes.
Open sourceIntroduction to Data Compression
BookCompression textbook support for Elias Gamma Coding'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 pagePrerequisite ofElias Delta Coding
Elias delta coding builds on gamma-style length coding.
Variant ofVariable-Length Encoding
Elias gamma is a variable-length code for positive integers.
Related Algorithms
Tags
CompressionEncodingInteger DataBit Level