In data compression, a universal code for integers is a prefix code that maps the positive integers onto binary codewords, with the additional property that whatever the true probability distribution on integers, as long as the distribution is monotonic , the expected lengths of the codewords are...
encoding the positive integers developed by Peter Elias
Peter Elias
Peter Elias was a pioneer in the field of information theory. Born in New Brunswick, New Jersey, he was a member of the Massachusetts Institute of Technology faculty from 1953 to 1991....
Elias gamma code is a universal code encoding positive integers developed by Peter Elias. It is used most commonly when coding integers whose upper-bound cannot be determined beforehand.-Encoding:To code a number:#Write it in binary....
Elias delta code is a universal code encoding the positive integers developed by Peter Elias. To code a number:#Write it in binary.#Count the bits and write down that number of bits in binary ....
, it works by prefixing the integer with a representation of its order of magnitude
Order of magnitude
An order of magnitude is the class of scale or magnitude of any amount, where each class contains values of a fixed ratio to the class preceding it. In its most common usage, the amount being scaled is 10 and the scale is the exponent being applied to this amount...
in a universal code. Unlike those other two codes, however, Elias omega recursively encodes that prefix; thus, they are sometimes known as recursive Elias codes.
Omega coding is used in applications where the largest encoded value is not known ahead of time, or to compress
Data compression
In computer science and information theory, data compression, source coding or bit-rate reduction is the process of encoding information using fewer bits than the original representation would use....
data in which small values are much more frequent than large values.
A number is a mathematical object used to count and measure. In mathematics, the definition of number has been extended over the years to include such numbers as zero, negative numbers, rational numbers, irrational numbers, and complex numbers....
:
Put a "0" at the end of the representation.
If the number to be encoded is 1, stop; if not, add the binary
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
representation of the number as a 'group' to the beginning of the representation.
Repeat the previous step, with the number of digits just written, minus 1, as the new number to be encoded.
To decode an Elias omega-coded integer:
Start with a variable N, set to a value of 1.
Read the first 'group', which will either be a single "0", or a "1" followed by N more digits. If it is a "0", it means the value of the integer is 1; if it starts with a "1", then N becomes the value of the group interpreted as a binary number.
Read each successive group; it will either be a single "0", or a "1" followed by N more digits. If it is a "0", it means the value of the integer is N; if it starts with a "1", then N becomes the value of the group interpreted as a binary number.
Examples
The first few codes are shown below. Included is the so-called implied distribution, describing the distribution of values for which this coding yields a minimum-size code; see Relationship of universal codes to practical compression for details.
A googol is the large number 10100, that is, the digit 1 followed by 100 zeros:The term was coined in 1938 by 9-year-old Milton Sirotta , nephew of American mathematician Edward Kasner...
, 10100, is 11 1000 101001100 followed by the binary representation of 1 googol, which is 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 and a trailing 0, for a total of 349 bits.
The encoding for a googol to the hundredth power, 1010000, is 33243 bits long; under Elias delta coding
Elias delta coding
Elias delta code is a universal code encoding the positive integers developed by Peter Elias. To code a number:#Write it in binary.#Count the bits and write down that number of bits in binary ....
, the same number is 33250 bits long. Interestingly, log2(1010000) is about 33219 bits, making Elias omega coding in this instance being only 0.07% short of being optimal.
Encoding
void eliasOmegaEncode(char* source, char* dest)
{
IntReader intreader(source);
BitWriter bitwriter(dest);
while (intreader.hasLeft)
{
int num = intreader.getInt;
BitStack bits;
while (num > 1) {
int len = 0;
for (int temp = num; temp > 0; temp >>= 1) // calculate 1+floor(log2(num))
len++;
for (int i = 0; i < len; i++)
bits.pushBit((num >> i) & 1);
num = len - 1;
}
while (bits.length > 0)
bitWriter.putBit(bits.popBit);
bitWriter.putBit(false); // write one zero
}
bitwriter.close;
intreader.close;
}
Decoding
void eliasOmegaDecode(char* source, char* dest) {
BitReader bitreader(source);
IntWriter intwriter(dest);
while (bitreader.hasLeft)
{
int num = 1;
while (bitReader.inputBit) // potentially dangerous with malformed files.
{
int len = num;
num = 1;
for (int i = 0; i < len; ++i)
{
num <<= 1;
if (bitReader.inputBit)
num |= 1;
}
}
intwriter.putInt(num); // write out the value
}
bitreader.close;
intwriter.close;
}
External references
Peter Elias, "Universal codeword sets and representations of the integers", IEEE Trans. Information Theory 21(2):194-203, Mar 1975.
Elias delta code is a universal code encoding the positive integers developed by Peter Elias. To code a number:#Write it in binary.#Count the bits and write down that number of bits in binary ....
Elias gamma code is a universal code encoding positive integers developed by Peter Elias. It is used most commonly when coding integers whose upper-bound cannot be determined beforehand.-Encoding:To code a number:#Write it in binary....
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
