Elias Code

Learned in CS451.

Elias gamma code is a universal code encoding positive integers developed by Peter Elias.

Encoding x

1. Let $N=\lfloor {\log }_{2}x\rfloor$
2. Write N 0s
3. Write x as an N+1-bit number
   • This number starts with 1.

Decoding x:

1. Read 0s until a 1, call this N
2. Interpret next N+1 bits as a binary number, including the 1

Does γ work well?

• Does well for term frequencies (how many times the term appears in the document)
• Does OK for gaps, too

The Elias code assumes the values are distributed by a power law: Most numbers should be small, or it doesn’t save any space.

Related

• Golomb Code