Elias omega coding

La codificación ω de Elias o codificación omega de Elias es un código universal para codificar los enteros positivos, desarrollado por Peter Elias . Al igual que la codificación gamma de Elias y la codificación delta de Elias , funciona anteponiendo al entero positivo una representación de su orden de magnitud en un código universal. Sin embargo, a diferencia de estos dos códigos, la codificación omega de Elias codifica dicho prefijo de forma recursiva; por ello, a veces se la conoce como códigos recursivos de Elias .

La codificación Omega se utiliza en aplicaciones donde no se conoce de antemano el valor codificado más grande, o para comprimir datos en los que los valores pequeños son mucho más frecuentes que los valores grandes.

Para codificar un número entero positivo N :

Coloca un "0" al final del código.
Si N = 1, detenerse; la codificación ha finalizado.
Anteponga la representación binaria de N al principio del código. Serán al menos dos bits, el primero de los cuales es un 1.
Sea N igual al número de bits que se acaban de añadir, menos uno.
Vuelva al paso 2 para anteponer la codificación del nuevo N.

Para decodificar un entero positivo codificado en omega de Elias:

Comience con una variable N , a la que se le asigna el valor 1.
Si el siguiente bit es un "0", entonces deténgase. El número decodificado es N.
Si el siguiente bit es un "1", léalo más N bits adicionales y use ese número binario como el nuevo valor de N. Vuelva al paso 2.

Ejemplos

Los códigos Omega pueden considerarse como una serie de "grupos". Un grupo puede ser un solo bit 0, que finaliza el código, o dos o más bits que comienzan con 1, seguidos de otro grupo.

A continuación se muestran los primeros códigos. Se incluye la denominada distribución implícita , que describe la distribución de valores para los que esta codificación produce un código de tamaño mínimo; consulte la sección «Relación entre los códigos universales y la compresión práctica» para obtener más detalles.

La codificación para 1 googol , ^10¹⁰⁰ , es 11¹⁰⁰⁰ 10¹⁰⁰¹¹⁰⁰ (15 bits de encabezado de longitud) seguido de la representación binaria de 333 bits de 1 googol, que es 10010 01001001 10101101 00100101 10010100 11000011 01111100 11101011 00001011 00100111 10000100 11000100 11001110 00001011 11110011 10001010 11001110 01000000 10001110 00100001 00011010 01111100 10101010 10110010 01000011 00001000 10101000 00101110 10001111 00010000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 y un 0 final, para un total de 349 bits.

Un googol elevado a la centésima potencia ( ^{10¹⁰²⁰⁰⁰} ) es un número binario de 33 220 bits. Su codificación omega tiene una longitud de 33 243 bits: 11 11 1000000111000100 (22 bits), seguido de 33 220 bits del valor y un 0 final. Con la codificación delta de Elias , el mismo número tiene una longitud de 33 250 bits: 000000000000000 1000000111000100 (31 bits) seguido de 33 219 bits del valor. Las codificaciones omega y delta son, respectivamente, un 0,07 % y un 0,09 % más largas que la representación binaria ordinaria de 33 220 bits del número.

Longitud del código

Para la codificación de un entero positivo $N$ , el número de bits necesarios, $B (N)$ , es recursivamente: ${\begin{aligned}B(0)&=0\,,\\B(N)&=1+\lfloor \log _{2}(N)\rfloor +B(\lfloor \log _{2}(N)\rfloor )\,.\end{aligned}}$ Es decir, la longitud del código omega de Elias para el entero $N$ es $1+(1+\lfloor \log _{2}N\rfloor {})+(1+\lfloor \log _{2}\lfloor \log _{2}N\rfloor {}\rfloor {})+\cdots$ donde el número de términos en la suma está acotado superiormente por el logaritmo binario iterado . Para ser precisos, sea $f(x)=\lfloor \log _{2}x\rfloor {}$ . Tenemos $N>f(N)>f(f(N))>\cdots >f^{k}(N)=1$ para algunos $k$ y la longitud del código es $(k+1)+f(N)+f^{2}(N)+\dots +f^{k}(N)$ . Desde $f(x)\leq \log _{2}x$ , tenemos $k\leq \log _{2}^{*}(N)$ .

Dado que el logaritmo iterado crece más lentamente que todos $\log _{2}^{n}N$ para cualquier fijo $n$ , la tasa de crecimiento asintótico es $\Theta (\log _{2}N+\log _{2}^{2}N+\cdots )$ , donde la suma termina cuando cae por debajo de uno.

Optimalidad asintótica

La codificación omega de Elias es un código de prefijo asintóticamente óptimo. ^{[ 1 ]}

Bosquejo de la demostración. Un código de prefijo debe satisfacer la desigualdad de Kraft . Para la codificación omega de Elias, la desigualdad de Kraft establece: $\sum _{n=1}^{\infty }{\frac {1}{2^{O(1)+\log _{2}n+\log _{2}\log _{2}n+\cdots }}}\leq 1$ Ahora, la suma es asintóticamente la misma que una integral, lo que nos da $\int _{1}^{\infty }{\frac {dx}{x\times \ln x\times \ln \ln x\cdots }}\leq O(1)$ Si el denominador termina en algún punto $\ln ^{k}x$ , entonces la integral diverge como $\ln ^{k+1}\infty$ Sin embargo, si el denominador termina en algún punto $(\ln ^{k}x)^{1+\epsilon }$ , entonces la integral converge como ${\frac {1}{(\ln ^{k}\infty )^{\epsilon }}}$ El código omega de Elias se encuentra en el límite entre la divergencia y la convergencia.

Código de ejemplo

Codificación

// elias_omega_encode está escrita como una función plantilla que recibe un número entero.// parámetro de tipo, porque Integer puede ser una clase de entero grande, y Elias omega// la codificación seguirá codificándolo de manera extremadamente eficiente (10^10000 solo usa 23// bits más que la representación binaria de 10^10000)#include <vector>plantilla < clase Entero >constexpr std :: vector < bool > little_endian_binary ( Integer num ){std :: vector <bool> bits { } ;mientras ( num != 0 ){bits . push_back ( num & 0b1u );num >>= 1 ;}devolver bits ;}constexpr std :: vector < bool > concat ( std :: vector < bool > l , std :: vector < bool > r ){para ( bool const i : r ){l . push_back ( i );}devolver l ;}////////////////////////////////////////////////////////////////////////////////// PARÁMETROS DE LA PLANTILLA //// Entero: Tipo de número //////////////////////////////////////////////////////////////////////////////////// PARÁMETROS //// num: Entero que almacena un entero positivo para convertir a la codificación omega de Elias //////////////////////////////////////////////////////////////////////////////////// DEVUELVE //// std::vector<bool> que almacena la codificación omega de Elias de num //////////////////////////////////////////////////////////////////////////////////// EXCEPCIONES //// std::range_error si num es <= 0, ya que num debe ser >= 1 //// std::bad_alloc si se agota la memoria //// Cualquier excepción lanzada por operadores de conversión o de bits de enteros //////////////////////////////////////////////////////////////////////////////////plantilla < clase Entero >constexpr std :: vector < bool > elias_omega_encode ( Integer num ){si ( num <= 0 ){throw std :: range_error ( "elias_omega_encode espera un valor >= 1" );}std :: vector <bool> bits = { false } ;mientras ( num != 1 ){std :: vector <bool> le_binary = little_endian_binary ( std :: move ( num ) ) ;auto const sizem1 = le_binary . size () - 1 ;bits = concat ( std :: move ( le_binary ), std :: move ( bits ));num = static_cast < Integer > ( sizem1 );}devolver bits ;}

Descodificación

// elias_omega_decode está escrita como una función plantilla que recibe un número entero.// parámetro de tipo, porque Integer puede ser una clase de entero grande, y Elias omega// la codificación seguirá codificándolo de manera extremadamente eficiente (10^10000 solo usa 23// bits más que la representación binaria de 10^10000)#include <type_traits>#include <vector>////////////////////////////////////////////////////////////////////////////////// PARÁMETROS DE LA PLANTILLA //// Entero: Tipo de entero a convertir desde la codificación omega de Elias //// GetNextBit: Tipo de get_next_bit //////////////////////////////////////////////////////////////////////////////////// PARÁMETROS //// get_next_bit: Función que devuelve un valor booleano de alguna fuente si no se le proporciona ningún valor //// argumentos, debería lanzar una excepción si esto no se puede hacer //////////////////////////////////////////////////////////////////////////////////// DEVUELVE //// Entero decodificado a partir del flujo de valores de retorno proporcionado por get_next_bit //////////////////////////////////////////////////////////////////////////////////// EXCEPCIONES //// std::bad_alloc si se agota la memoria //// Cualquier excepción lanzada por el operador() de GetNextBit //// Cualquier excepción lanzada por operadores de conversión o de bits de enteros //////////////////////////////////////////////////////////////////////////////////plantilla < clase Entero , clase ObtenerSiguienteBit >requiere std :: is_invocable_r_v < bool , GetNextBit &>constexpr Integer elias_omega_decode ( GetNextBit get_next_bit ){Resultado entero = static_cast <Entero> ( 1 ) ;mientras ( std :: invoke_r < bool > ( get_next_bit )){Integer new_result = static_cast < Integer > ( 1 );mientras ( resultado != 0 ) {nuevo_resultado <<= 1 ;if ( std :: invoke_r < bool > ( get_next_bit )){nuevo_resultado |= 0b1u ;}-- resultado ;}resultado = std :: move ( nuevo_resultado );}devolver resultado ;}

Generalizaciones

La codificación omega de Elias no codifica números enteros negativos ni cero. Una forma de codificar todos los enteros no negativos es sumar 1 antes de la codificación y luego restar 1 después de la decodificación, o usar la codificación de Levenshtein, que es muy similar . Otra forma de codificar todos los enteros es establecer una biyección , mapeando todos los enteros (0, 1, -1, 2, -2, 3, -3, ...) a enteros estrictamente positivos (1, 2, 3, 4, 5, 6, 7, ...) antes de la codificación.

Véase también

Referencias

↑ Elias, P. (marzo de 1975). "Conjuntos de palabras clave universales y representaciones de los enteros". IEEE Transactions on Information Theory . 21 (2): 194– 203. doi : 10.1109/TIT.1975.1055349 . ISSN 0018-9448 .

Lecturas adicionales

Elias, Peter (marzo de 1975). "Conjuntos de palabras clave universales y representaciones de los enteros". IEEE Transactions on Information Theory . 21 (2): 194– 203. doi : 10.1109/tit.1975.1055349 .
Fenwick, Peter (2003). «Códigos universales». En Sayood, Khalid (ed.). Manual de compresión sin pérdidas . Nueva York, NY, EE. UU.: Academic Press . págs. 55–78 . doi : 10.1016/B978-012620861-0/50004-8 . ISBN 978-0123907547.

Enlaces externos

Implementación en Python

[1] Elias, P. (marzo de 1975). "Conjuntos de palabras clave universales y representaciones de los enteros". IEEE Transactions on Information Theory . 21 (2): 194– 203. doi : 10.1109/TIT.1975.1055349 . ISSN 0018-9448 .

[ 1 ]