La codificación de Elias ω o la codificación omega de Elias es un código universal que codifica los enteros positivos desarrollado por Peter Elias . Al igual que la codificación gamma de Elias y la codificación delta de Elias , funciona prefijando el número entero con una representación de su orden de magnitud en un código universal. Sin embargo, a diferencia de esos otros dos códigos, Elias omega codifica recursivamente ese prefijo; por lo tanto, a veces se les conoce como códigos recursivos de Elias .
La codificación Omega se utiliza en aplicaciones donde el valor codificado más grande no se conoce de antemano, 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 N :
- Coloque un "0" al final del código.
- Si N = 1, deténgase; la codificación está completa.
- Anteponga la representación binaria de N al principio del código. Estos serán al menos dos bits, el primer bit de los cuales es un 1.
- Sea N igual al número de bits que acaba de agregar, menos uno.
- Volver al paso 2 para anteponer la codificación de la nueva N .
Para decodificar un entero codificado en omega de Elias:
- Comience con una variable N , establecida en un valor de 1.
- Si el siguiente bit es un "0", deténgase. El número decodificado es N .
- Si el siguiente bit es un "1", luego leerlo plus N más bits, y el uso de ese número binario como el nuevo valor de N . Regrese al paso 2.
Ejemplos de
Los códigos Omega se pueden considerar como una serie de "grupos". Un grupo es un solo bit 0, que termina el código, o dos o más bits que comienzan con 1, seguido de otro grupo.
Los primeros códigos se muestran a continuación. 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 Relación de los códigos universales con la compresión práctica para obtener más detalles.
Valor | Código | Probabilidad implícita |
---|---|---|
1 | 0 | 1/2 |
2 | 10 0 | 1/8 |
3 | 11 0 | 1/8 |
4 | 10100 0 | 1/64 |
5 | 10 101 0 | 1/64 |
6 | 10 110 0 | 1/64 |
7 | 10 111 0 | 1/64 |
8 | 11 1000 0 | 1/128 |
9 | 11 1001 0 | 1/128 |
10 | 11 1010 0 | 1/128 |
11 | 11 1011 0 | 1/128 |
12 | 11 1100 0 | 1/128 |
13 | 11 1101 0 | 1/128 |
14 | 11 1110 0 | 1/128 |
15 | 11 1111 0 | 1/128 |
dieciséis | 10100 10000 0 | 1/2048 |
17 | 10100 10001 0 | 1/2048 |
... | ||
100 | 10110 1100100 0 | 1/8192 |
1000 | 11 1001 1111101000 0 | 1 / 131.072 |
10,000 | 11 1101 10011100010000 0 | 1 / 2,097,152 |
100.000 | 10100 10000 11000011010100000 0 | 1 / 268,435,456 |
1,000,000 | 10100 10011 11110100001001000000 0 | 1 / 2,147,483,648 |
La codificación de 1 googol , 10 100 , es 11 1000 101 001 100 (15 bits de cabecera de longitud), seguido de la representación binaria 333 bits de 1 googol, que es 10 010 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 y un 0 al final, para un total de 349000000 bits.
Un googol elevado a la centésima potencia (10 10000 ) es un número binario de 33220 bits. Su codificación omega tiene 33,243 bits de longitud: 11 1111 1000000111000100 (22 bits), seguido de 33,220 bits del valor y un 0 final. Bajo la codificación delta de Elias , el mismo número tiene 33,250 bits de longitud: 000000000000000 1000000111000100 (31 bits) seguido de 33,219 bits del valor. Como log 2 (10 10000 ) = 33219.28, en este caso, la codificación omega y delta son, respectivamente, solo un 0.07% y un 0.09% más largos de lo óptimo.
Código de ejemplo
Codificación
void eliasOmegaEncode ( char * fuente , char * dest ) { IntReader intreader ( fuente ); BitWriter bitwriter ( dest ); while ( intreader . hasLeft ()) { int num = intreader . getInt (); Bits BitStack ; while ( num > 1 ) { int len = 0 ; for ( int temp = num ; temp > 0 ; temp >> = 1 ) // calcular 1 + floor (log2 (num)) len ++ ; para ( int i = 0 ; i < len ; i ++ ) bits . pushBit (( num >> i ) & 1 ); num = len - 1 ; } while ( bits . longitud () > 0 ) bitwriter . putBit ( bits . popBit ()); bitwriter . putBit ( falso ); // escribe un cero } bitwriter . cerrar (); intreader . cerrar (); }
Descodificación
void eliasOmegaDecode ( char * fuente , char * dest ) { BitReader bitreader ( fuente ); IntWriter intwriter ( dest ); while ( lector de bits . hasLeft ()) { int num = 1 ; while ( bitreader . inputBit ()) // potencialmente peligroso con archivos mal formados. { int len = num ; num = 1 ; para ( int i = 0 ; i < len ; ++ i ) { num << = 1 ; if ( lector de bits . inputBit ()) num | = 1 ; } } escritora . putInt ( num ); // escribe el valor } bitreader . cerrar (); intérprete . cerrar (); }
Generalizaciones
La codificación omega de Elias no codifica números enteros cero o negativos. Una forma de codificar todos los enteros no negativos es sumar 1 antes de codificar y luego restar 1 después de decodificar. Una forma de codificar todos los enteros es configurar 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 codificar.
Ver también
Referencias
Otras lecturas
- Elias, Peter (marzo de 1975). "Conjuntos de palabras de código universales y representaciones de los números enteros". Transacciones IEEE sobre teoría de la información . 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.