Overview
Elias delta coding improves gamma coding for larger integers by compressing the length field itself.
ExtendedSource checked
Elias Delta Coding
Encodes positive integers by gamma-coding the binary length before the 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 codelength-of-lengthbinary 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 by gamma-coding the binary length before the payload
- Uses universal code and length-of-length 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)
Delta components
N = ⌊log2(n)⌋ + 1
N = floor(log2(n)) + 1Encodes the bit length N with Elias gamma coding before the remaining bits of n.
Pseudocode
- 1.Prepare the inputs and state needed for Elias Delta 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 Delta Coding input with a small representative case
- Output
- Encoded stream
- Explanation
- Elias Delta 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 Delta 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 Delta Coding.
compression-mechanismNotes
Elias Delta 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 gamma and delta integer codes.
Open sourceIntroduction to Data Compression
BookCompression textbook support for Elias Delta 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 pageImproves onElias Gamma Coding
Delta coding improves gamma coding for larger integers.
Variant ofVariable-Length Encoding
Elias delta is a variable-length integer code.
Related Algorithms
Tags
CompressionEncodingInteger DataBit Level