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)
“If one could be friendly with women, what a pleasure—the relationship so secret and private compared with relations with men. Why not write about it truthfully?”
—Virginia Woolf (1882–1941)
“Juggling produces both practical and psychological benefits.... A woman’s involvement in one role can enhance her functioning in another. Being a wife can make it easier to work outside the home. Being a mother can facilitate the activities and foster the skills of the efficient wife or of the effective worker. And employment outside the home can contribute in substantial, practical ways to how one works within the home, as a spouse and as a parent.”
—Faye J. Crosby (20th century)
“Do they [the publishers of Murphy] not understand that if the book is slightly obscure it is because it is a compression and that to compress it further can only make it more obscure?”
—Samuel Beckett (1906–1989)