Python Elias Gamma Encoding

Peter Elias created the Elias Gamma Encoding, which is used to encode a sequence of positive numbers. Let’s examine how we can use Python to encode a positive integer using this encoding technique.

What is Elias Gamma Encoding?

The Elias gamma code is a universal code for encoding a series of positive integers. It’s particularly beneficial when the upper bound of an integer can’t be determined in advance.

Assume the number to be encoded is N. The steps for Elias Gamma Encoding of N are as follows:

• Find the greatest integer x that meets the following criteria.
• 2^x ≤ N.
• Now, in the resulting encoding string, add x number of zeroes followed by 1. This is referred to as Unary Encoding.
• To the result obtained in the previous step, add the x-digit binary representation of (N – 2^x).
•  The result string is the Elias Gamma Encoded.

Example

Let the Number = 19

As (19 = 2^4 + 3), the greatest feasible value of  ‘x’ in this scenario is 4.

Unary encoding:  By performing unary encoding we get 00001.

Then we need to get the four-digit binary representation of 3, which is 0011.

It should be added to 00001.

As a result, our encoded string is 000010011.

Elias Gamma Encoding in Python

Approach:

• Import parse from urllib module using the import keyword
• Perform the Unary encoding by using the lambda function
• Perform the binary encoding by using the lambda function
• Create a function say eliasEncoding() which returns the Elias Encoded string for the given number
• Check if the number is equal to 0 using the if conditional statement
• If it is true then return ‘0’
• Get the base-2 log value of the given number using the log() function and
• Store it in a variable
• Pass the above log value to the unary_encoding() function and b, log value to the binary_encoding() function and sum up both the unary and binary encoded values
• Return the above result
• Pass some random number to the above-created eliasEncoding() function to perform the Elias Encoding operation and print the result.
• The Exit of the Program.

Below is the implementation:

# Import parse from urllib module using the import keyword 
import math
# Perform the Unary encoding by using the lambda function
unary_encoding = lambda num: num * '0' + '1'
# Perform the binary encoding by using the lambda function
binary_encoding = lambda num, l = 1:("{0:0%db}" % l).format(num)
# Create a function say eliasEncoding() which returns the Elias Encoded string for the given number
def eliasEncoding(num):
    # Check if the number is equal to 0 using the if conditional statement
    if(num==0):
        # If it is true then return '0'
        return '0'
    
    # Get the base-2 log value of the given number using the log() function and 
    # Store it in a variable
    logval = int(math.log(num, 2))
 
    b = num - 2 ** logval
    # Pass the above log value to the unary_encoding() function and b, log value to the binary_encoding() function
    # and sum up both the unary and binary encoded values  
    rslt = unary_encoding(logval) + binary_encoding(b, logval)
    # Return the above result
    return rslt

# Pass some random number to the above created eliasEncoding() function 
# to perform the Elias Encoding operation and print the result
print("The Elias Encoding of the given number{10}:")
print(eliasEncoding(10))

Output:

The Elias Encoding of the given number{10}:
0001010

NOTE: It should be noted that Elias Gamma Encoding is useful when the upper bound of integers cannot be determined.