Relationship To Practical Compression
Huffman coding and arithmetic encoding (when they can be used) give at least as good, and often better compression than any universal code.
However, universal codes are useful when Huffman coding cannot be used — for example, when one does not know the exact probability of each message, but only knows the rankings of their probabilities.
Universal codes are also useful when Huffman codes are inconvenient. For example, when the transmitter but not the receiver knows the probabilities of the messages, Huffman coding requires an overhead of transmitting those probabilities to the receiver. Using a universal code does not have that overhead.
Each universal code, like each other self-delimiting (prefix) binary code, has its own "implied probability distribution" given by p(i)=2-l(i) where l(i) is the length of the ith codeword and p(i) is the corresponding symbol's probability. If the actual message probabilities are q(i) and Kullback–Leibler divergence DKL(q||p) is minimized by the code with l(i), then the optimal Huffman code for that set of messages will be equivalent to that code. Likewise, how close a code is to optimal can be measured by this divergence. Since universal codes are simpler and faster to encode and decode than Huffman codes (which is, in turn, simpler and faster than arithmetic encoding), the universal code would be preferable in cases where DKL(q||p) is sufficiently small.
For any geometric distribution (an exponential distribution on integers), a Golomb code is optimal. With universal codes, the implicit distribution is approximately a power law such as (more precisely, a Zipf distribution). For the Fibonacci code, the implicit distribution is approximately, with
where is the golden ratio. For the ternary comma code (i.e., encoding in base 3, represented with 2 bits per symbol), the implicit distribution is a power law with . These distributions thus have near-optimal codes with their respective power laws.
Read more about this topic: Universal Code (data Compression)
Famous quotes containing the words relationship to, relationship, practical and/or compression:
“Film music should have the same relationship to the film drama that somebody’s piano playing in my living room has to the book I am reading.”
—Igor Stravinsky (1882–1971)
“Strange and predatory and truly dangerous, car thieves and muggers—they seem to jeopardize all our cherished concepts, even our self-esteem, our property rights, our powers of love, our laws and pleasures. The only relationship we seem to have with them is scorn or bewilderment, but they belong somewhere on the dark prairies of a country that is in the throes of self-discovery.”
—John Cheever (1912–1982)
“Missionaries, whether of philosophy or religion, rarely make rapid way, unless their preachings fall in with the prepossessions of the multitude of shallow thinkers, or can be made to serve as a stalking-horse for the promotion of the practical aims of the still larger multitude, who do not profess to think much, but are quite certain they want a great deal.”
—Thomas Henry Huxley (1825–95)
“The triumphs of peace have been in some proximity to war. Whilst the hand was still familiar with the sword-hilt, whilst the habits of the camp were still visible in the port and complexion of the gentleman, his intellectual power culminated; the compression and tension of these stern conditions is a training for the finest and softest arts, and can rarely be compensated in tranquil times, except by some analogous vigor drawn from occupations as hardy as war.”
—Ralph Waldo Emerson (1803–1882)