Elias Gamma Encoding in Python

In this tutorial, we are going to learn Elias Gamma Encoding in Python. Elias Gamma Encoding has been developed by Peter Elias and it is used to encode a sequence of positive integers. Let’s see how we can encode a positive integer using this encoding technique with Python.

Elias Gamma Encoding

Let’s say the number we want to encode is N. Here are the steps for Elias Gamma Encoding of N.

• Find the largest integer x that satisfies the following condition.
  2^x ≤ N
• Now add x number of zeroes in the resulting encoding string followed by 1. This part is called Unary Encoding.
• Now add x-digit binary representation of (N – 2^x) to the result obtained in previous step.
• The resultant string is Elias Gamma Encoded.

Let’s see an example to understand this in a better way.

Suppose we want to perform Elias Gamma Encoding for number 19.

In this case, the largest possible value of x is 4 as (19 = 2⁴ + 3). Therefore, after performing unary encoding we get, 00001. Next, we need to find 4-digit binary representation of 3 which is 0011. Add it to 00001. Thus our resultant encoded string is 000010011.

Python Implementation of Elias Gamma Encoding

Have a look at the following code to see how we can implement Elias Gamma Encoding in Python.

import math

unary= lambda n: n * '0' + '1'

binary = lambda n, l = 1:("{0:0%db}" % l).format(n)

def elias(n):
    if(n==0):
        return '0'
    x = int(log(n, 2))
    
    u = x
    b = n - 2 ** x
    
    return unary(u) + binary(b, x)

print(elias(19))

Output:

000010011

As you can see we can easily find Elias Gamma Encoding of a number using the above Python program.

Note that Elias Gamma Encoding is useful in cases where we cannot determine upper bound of integers.

Thank you.

Also read: Python program to find roots of an equation using secant method