A universal code for integers in data compression is a prefix code that converts positive integers to binary words, with the additional property that for any true probability distribution on integers, while the distribution is monotonous (i.e. for anyone ), the expected lengths of binary words are within the constant factor of the expected lengths that the optimal code would assign for this probability distribution.
A universal code is asymptotically optimal if the coefficient between the actual and optimal expected lengths is related by a function of information information entropy of the code, which approaches 1, since the entropy approaches infinity.
Most prefix codes for integers assign longer keywords to large integers. Such code can be used to efficiently encode a message that extends from a set of possible messages, simply arranging the set of messages to reduce the probability and then sending the index of the intended message. Universal codes are generally not used for well-known probability distributions.
Universal codes include:
- Unary coding
- Elias Gamma Code
- Elias Delta Code
- Elias Omega Code
- Delta code
- Fibonacci coding
- Exponential Golomb code
Some non-universal codes:
- single coding used in Elias codes
- Rice Coding
- Golomb coding
Their non-universality is manifested in the fact that if any of them are used to encode the Gauss-Kuzmin distribution or the zeta distribution with the parameter s = 2, then the expected length of the keyword is infinite. For example, using a single encoding for zeta distribution, we have the following expected length:
Interconnection and practical use
Using Huffman code and arithmetic coding (when they can be used together) give a better result than any other universal code.
However, universal codes are useful when the Huffman code cannot be used — for example, when it is impossible to determine the exact probability of each message, but the ranking of their probabilities is known.
Universal codes are also useful when the Huffman code does not work out correctly. For example, when the sender knows the probabilities of the message, but the receiver does not, the Huffman code requires transmitting the probabilities to the receiver. Using universal code eliminates such inconvenience.
Each universal code gives its own “implied distribution” of probabilities p ( i ) = 2 - l ( i ) , where l (i) is the length of the ith keyword and p (i) is the probability of the transmission symbol. If the actual message probabilities are q (i) and the Kullback - Leibler distance DKL (q || p) minimizes the code with l (i), then the optimal Huffman code for this set of messages will be equivalent to this code. Since universal codes began to work faster to encode and decode than a Huffman code, a universal code would be preferred in cases where DKL (q || p) is small enough.
For any geometric distribution , Golomb coding is optimal. With universal codes, implied distribution is roughly an energy law such as 1 / n2. For the Fibonacci code , the implied distribution is approximately 1 / nq.