Elias Omega

Esta codificación es una codificación universal de enteros positivos desarrollada por Peter Elias en 1975. Es parecida a las otras codificaciones desarrolladas por Elias (la gamma y delta) porque combinan representaciones del número como prefijo.

Codificación

A continuación se presenta un algoritmo para codificar a un entero positivo \(n\).

1. El código inicial es un \(0\).
2. Si \(n = 1\), retornar codificación.
3. Colocar la representación binaria de \(n\) como prefijo del código.
4. \(n \gets \lfloor \lg n \rfloor\).
5. Ir al paso 2.

Y esta sería una implementación básica en Python.

# Returns Elias omega encoding of n as a str
def elias_omega_encode(n):
    assert(n > 0)

    c = '0'
    while n > 1:
        c = bin(n)[2:] + c
        n = n.bit_length() - 1 # same as n = floor(lg(n))
    return c

Decodificación

Para decodificar un código \(c\) simplemente hacemos el proceso inverso: Cada prefijo nos dice cuánto debemos leer y si llegamos a un cero, entonces terminamos el proceso. El pseudocódigo sería el siguiente:

1. \(n \gets 1\), \(i \gets 0\).
2. Si \(c[i] = 0\), retornar \(n\).
3. Ahora el bit actual es un \(1\), así que leer los siguientes \(n\) bits y hacer que \(n\) tenga el valor que representan los bits leídos en binario. Luego \(i \gets i + n + 1\).
4. Ir al paso 2.

Una implementación simple en Python sería esta:

# Decodes an Elias omega encoded sequence c
def elias_omega_decode(c):
    n = 1
    i = 0
    while c[i] != '0':
        m = c[i:(i + n + 1)]
        i += n + 1
        n = int(m, 2) # second argument is radix base
    return n

Aplicaciones

Como este código es universal es muy bueno para representar enteros y tiene aplicaciones prácticas para la compresión de información. Además, es posible representar cualquier entero si asociamos biyectivamente \(\mathbb{Z}\) a \(\mathbb{N}\) usando, por ejemplo, representación zigzag, la cual consiste en ordenar los enteros de la siguiente manera \(0, -1, 1, -2, 2, -3, 3,\ldots\) y asociarlos con los enteros positivos en ese orden.

Además, si los enteros que se quieren guardar son más o menos pequeños, vemos que mientras más pequeño el número menos bits usa, así que este código se acerca a la entropía en esos casos. Además, si el valor máximo no se conoce a priori, esta codificación también es aplicable pues maneja bien esta situación.

Referencias

• Elias, P. (1975). Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory. 21 (2): 194–203.