User:HTinC23/通用編碼

Fibonacci, Elias Gamma, and Elias Delta vs binary coding

Rice with k = 2, 3, 4, 5, 8, 16 versus binary

数据压缩理論中，通用編碼是正整數的某種前綴編碼。這樣的編碼是將正整數映成二進位串的映射，並要滿足額外的條件：不論正整數訊號源具有怎樣的概率分布 p, 只要其單調遞減（即 p(i ) ≥ p(i + 1) 對任意的 i 成立），則碼詞（編碼所得的二進位串）的期望長度與 p 的最優編碼相比至多差常數倍。若一種通用編碼的碼詞期望長度與最優期望長度之比為熵 H 的有界函數 f(H), 且在 H 趨向正無窮時，f(H) 趨向於 1, 則稱該通用編碼為漸近最優。

一般而言，正整數的前綴編碼會把較長的碼詞賦予較大的正整數。假如已知可能要發送的訊息的列表，則可利用此種編碼有效地溝通，因為可以先將該列表內的訊息按概率遞減排序，然後僅發送相應的正整數序號。倘已確切知道訊號源的概率分布，則可考慮不採用通用編碼，而視具體情況採用更合適的編碼。

通用與非通用編碼例子

下列為正整數的通用編碼：（星號 (*) 表示可以These are some universal codes for integers; an asterisk (*) indicates a code that can be trivially restated in lexicographical order, while a double dagger (‡) indicates a code that is asymptotically optimal:

• 以利亞加瑪碼 *
• 以利亞戴爾達碼 * ‡
• Elias omega coding * ‡
• 指数哥伦布码 *, 非負整數 n 的 0 階指數哥倫布碼就是 n+1 的以利亞加瑪碼。（在 H.264/MPEG-4 AVC 用到）
• 斐波那契编码
• 萊文斯坦編碼 * ‡, 原來的 [1]
• Byte coding where a special bit pattern (with at least two bits) is used to mark the end of the code — for example, if an integer is encoded as a sequence of nibbles representing digits in base 15 instead of the more natural base 16, then the highest nibble value (i.e., a sequence of four ones in binary) can be used to indicate the end of the integer.
• Variable-length quantity

亦有下列非通用編碼：

• 一元編碼，用於多種的以利亞編碼中
• 萊斯編碼，用於 FLAC 音频编解码器中，且一元編碼為其特例
• 格倫布編碼，萊斯編碼和一元編碼皆為其特例。

Their nonuniversality can be observed by noticing that, if any of these are used to code the Gauss–Kuzmin distribution or the Zeta distribution with parameter s=2, expected codeword length is infinite. For example, using unary coding on the Zeta distribution yields an expected length of

$E(l)={\frac {6}{\pi ^{2}}}\sum _{l=1}^{\infty }{\frac {1}{l}}=\infty .\,$

On the other hand, using the universal Elias gamma coding for the Gauss–Kuzmin distribution results in an expected codeword length (about 3.51 bits) near entropy (about 3.43 bits)[2].

Relationship to practical compression

Huffman coding and arithmetic coding (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 D_KL(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 D_KL(q||p) is sufficiently small. [3]

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 $1/n^{2}$ (more precisely, a Zipf distribution). For the Fibonacci code, the implicit distribution is approximately $1/n^{q}$, with

$q=1/\log _{2}(\varphi )\simeq 1.44,$

where $\varphi$ 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 $q=1+\log _{3}(4/3)\simeq 1.26$. These distributions thus have near-optimal codes with their respective power laws.

External links

• Data Compression, by Debra A. Lelewer and Daniel S. Hirschberg (University of California, Irvine)
• Information Theory, Inference, and Learning Algorithms, by David MacKay, has a chapter on codes for integers, including an introduction to Elias codes.
• Кодирование целых чисел has mostly English-language papers on universal and other integer codes.

{{Compression Methods}} [[Category:Data compression]] [[Category:Lossless compression algorithms]]