Understanding Elias Delta Encoding

Elias Delta encoding is a universal code used for representing positive integers. It's particularly efficient for compressing integers that follow a geometric distribution. This encoding method builds upon the concept of Elias Gamma encoding, adding an extra layer of compression.

Binary Representation Without Most Significant Bit

First, we need a helper function that converts a number to its binary representation without the most significant bit (MSB).

def binary_without_msb(number):
    binary_str = bin(number)[2:]  # Convert to binary and remove '0b' prefix
    return binary_str[1:]  # Remove the first bit (MSB)

Elias Gamma Encoding

Elias Gamma encoding is a foundational component of Delta encoding. It works by first representing the length of the binary number in unary format, followed by the binary representation without the MSB.

def elias_gamma_encode(value):
    if value == 0:
        return '0'
    
    # Calculate the number of bits needed
    num_bits = value.bit_length()
    
    # Create unary representation of the bit length (N-1 zeros followed by a one)
    unary_part = '0' * (num_bits - 1) + '1'
    
    # Get the binary representation without the MSB
    binary_part = binary_without_msb(value)
    
    return unary_part + binary_part

Elias Delta Encoding Implementation

Delta encoding enhances Gamma encoding by first encoding the length of the number using Gamma encoding, then appending the binary representation of the original number without its MSB.

def elias_delta_encode(number):
    if number == 0:
        return '0'
    
    # Calculate the floor of log2(number)
    log_value = number.bit_length() - 1
    
    # Encode the length using Gamma encoding
    gamma_encoded = elias_gamma_encode(log_value + 1)
    
    # Get the binary representation without the MSB
    binary_part = binary_without_msb(number)
    
    return gamma_encoded + binary_part

Complete Example

Here's a complete implementation demonstrating Elias Delta encoding:

def binary_without_msb(number):
    binary_str = bin(number)[2:]
    return binary_str[1:]

def elias_gamma_encode(value):
    if value == 0:
        return '0'
    
    num_bits = value.bit_length()
    unary_part = '0' * (num_bits - 1) + '1'
    binary_part = binary_without_msb(value)
    
    return unary_part + binary_part

def elias_delta_encode(number):
    if number == 0:
        return '0'
    
    log_value = number.bit_length() - 1
    gamma_encoded = elias_gamma_encode(log_value + 1)
    binary_part = binary_without_msb(number)
    
    return gamma_encoded + binary_part

# Test the encoding
test_number = 14
encoded_result = elias_delta_encode(test_number)
print(f"Elias Delta encoded representation of {test_number}: {encoded_result}")

The output for the number 14 would be 00100110, which demonstrates how the Delta encoding compresses the original number by combining Gamma encoding of its length with its binary representation.

Understanding the Encoding Process

1. For the input number 14: - Binary representation: 1110 - Length of binary: 4 bits - Gamma encoding of length (4): 001 (unary for 2 bits + binary without MSB of 4) - Binary without MSB of 14: 110 - Combined result: 001 + 110 = 001110

This encoding scheme is particularly useful in data compression algorithms where integers need to be represented in a compact form.