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)
“Henry David Thoreau, who never earned much of a living or sustained a relationship with any woman that wasn’t brotherly—who lived mostly under his parents’ roof ... who advocated one day’s work and six days “off” as the weekly round and was considered a bit of a fool in his hometown ... is probably the American writer who tells us best how to live comfortably with our most constant companion, ourselves.”
—Edward Hoagland (b. 1932)
“I favor the policy of economy, not because I wish to save money, but because I wish to save people. The men and women of this country who toil are the ones who bear the cost of the Government. Every dollar that we carelessly waste means that their life will be so much the more meager. Every dollar that we prudently save means that their life will be so much the more abundant. Economy is idealism in its most practical terms.”
—Calvin Coolidge (1872–1933)
“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)