> elias | gamma | universal <
// Elias Gamma - Universal code for positive integers without parameters
Universal Code
Works for any positive integer without parameters.
Prefix-Free
No code is a prefix of another, enabling unique decoding.
Asymptotically Optimal
Approaches optimal compression for certain distributions.
>> technical info
How Elias Gamma Works:
Elias Gamma encodes a positive integer n by: 1) Finding N = floor(log₂(n)), 2) Writing N zeros as unary code, 3) Appending the binary representation of n (which is N+1 bits). The result is a (2N+1)-bit code.
Encoding Examples:
n=1: log₂(1)=0 Code: 1 (no zeros + "1") n=2: log₂(2)=1 Code: 010 (one zero + "10") n=5: log₂(5)=2 Code: 00101 (two zeros + "101") n=10: log₂(10)=3 Code: 0001010 (three zeros + "1010") Length formula: 2⌊log₂(n)⌋ + 1
Why Use Elias Gamma:
- >No parameters needed
- >Simple implementation
- >Good for small integers
- >Universal code property
- >Theoretical importance
>> frequently asked questions
What is Elias Gamma coding?
Elias Gamma is a universal code for positive integers developed by Peter Elias. It encodes each integer using its bit length in unary, followed by the binary representation. It's called 'universal' because it works without knowing the data distribution.
When is Elias Gamma efficient?
Elias Gamma is most efficient for integers that follow a power-law distribution (P(n) ∝ n^(-2)). It uses approximately 2log₂(n) + 1 bits, making it good for small integers but less efficient for large ones.
Gamma vs Delta vs Omega?
Elias Gamma uses 2log₂(n)+1 bits. Delta improves this to log₂(n)+2log₂(log₂(n)+1)+1 bits. Omega further improves for very large numbers. Gamma is simplest, Delta is better for medium values, Omega for large values.
Where is Elias coding used?
Elias codes are used in information theory, data compression research, and some specialized compression algorithms. They're important theoretically as universal codes but less common in practice than Huffman or arithmetic coding.