| Universal Code (data Compression) |
Article Index for Universal Code |
Website Links For Universal |
Information AboutUniversal Code (data Compression) |
|
In general, most prefix-free codes for integers assign longer codewords to larger integers. Such a code can be used to efficiently communicate a message drawn from a set of possible messages, by simply ordering the set of messages by decreasing probability and then sending the index of the intended message. These are some universal codes for integers:
These are non-universal ones:
RELATIONSHIP TO PRACTICAL COMPRESSION Huffman Coding , Range Encoding , 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-free) binary code, has its own "implied probability distribution". If a set of messages happens to have a probability distribution similar enough to that implied by some universal code, then the ideal Huffman code or arithmetic code for that set of messages will be equivalent to that universal code. Since universal codes are simpler and faster to encode and decode than Huffman codes (which is, in turn, simpler and faster than Range Encoding and Arithmetic Encoding ), the universal code would be preferable in cases where the codes are equivalent. {Link without Title} For Rice codes and other Golomb codes, the implicit probability distribution is a Geometric Distribution (an exponential distribution on integers) with mean . For universal codes, the implicit distribution is approximately a Power Law such as . For the Fibonacci Code , the implicit distribution is , 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 . The figures below compare Elias Gamma, Elias Delta, Fibonacci, and various Rice codings for bits used to encode integer values. A baseline, "direct binary", for binary encoding where the size is already known is also included. REFERENCES
EXTERNAL LINKS
|
|
|