Universal code (data compression)

<h2 id="universal-and-non-universal-codes">Universal and non-universal codes</h2>
These are some universal codes for integers; an asterisk (<a href="/facts/Asterisk/qwmtPW5V">*</a>) indicates a code that can be trivially restated in <a href="/facts/Lexicographical_order/xQANy8Br">lexicographical order</a>, while a double dagger (<a href="/facts/%25E2%2580%25A1/lDNNgbgr">‡</a>) indicates a code that is asymptotically optimal:

<ul><li><a href="/facts/Elias_gamma_coding/kcNSUnBg">Elias gamma coding</a> *</li>
<li><a href="/facts/Elias_delta_coding/LoDaPWqx">Elias delta coding</a> * ‡</li>
<li><a href="/facts/Elias_omega_coding/uxHF9zyx">Elias omega coding</a> * ‡</li>
<li><a href="/facts/Exponential-Golomb_coding/gGrYPQCw">Exp-Golomb coding</a> *, which has Elias gamma coding as a special case. (Used in <a href="/facts/H.264%2fMPEG-4_AVC/soCzKcmJ">H.264/MPEG-4 AVC</a>)</li>
<li><a href="/facts/Fibonacci_coding/GXCLAf7t">Fibonacci coding</a></li>
<li><a href="/facts/Levenshtein_coding/ACQLnfgw">Levenshtein coding</a> * ‡, the original universal coding technique <a href="http://www.compression.ru/download/articles/int/levenstein_1968_on_the_redundancy_and_delay.pdf">[1]</a></li>
<li>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 <a href="/facts/Nibble/PUaqCEVw">nibbles</a> representing digits in <a href="/facts/Base_15/RgfoI90F">base 15</a> instead of the more natural <a href="/facts/Base_16/02ohQW22">base 16</a>, then the highest nibble value (i.e., a sequence of four ones in binary) can be used to indicate the end of the integer.</li>
<li><a href="/facts/Variable-length_quantity/403RnSeL">Variable-length quantity</a></li></ul>
These are non-universal ones:

<ul><li><a href="/facts/Unary_coding/yHF7r7pE">Unary coding</a>, which is used in Elias codes</li>
<li><a href="/facts/Golomb_coding/bUyW4uLN">Rice coding</a>, which is used in the <a href="/facts/FLAC/TbqpHlWy">FLAC</a> <a href="/facts/Audio_codec/DkXoa6YP">audio codec</a> and which has unary coding as a special case</li>
<li><a href="/facts/Golomb_coding/bUyW4uLN">Golomb coding</a>, which has Rice coding and unary coding as special cases.</li></ul>
Their nonuniversality can be observed by noticing that, if any of these are used to code the <a href="/facts/Gauss%25E2%2580%2593Kuzmin_distribution/z9aK3LRl">Gauss–Kuzmin distribution</a> or the <a href="/facts/Zeta_distribution/nWlnRng7">Zeta distribution</a> 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
        )
        =
        
          
            6
            
              π
              
                2
              
            
          
        
        
          ∑
          
            l
            =
            1
          
          
            ∞
          
        
        
          
            1
            l
          
        
        =
        ∞
        .
        
      
    
    {\displaystyle 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)<a href="https://web.archive.org/web/20150606201418/http://scholar.google.com/scholar?cluster=13442560459874106744">- Академия Google</a>.

<h2 id="relationship-to-practical-compression">Relationship to practical compression</h2>
<a href="/facts/Huffman_coding/dBgMBz48">Huffman coding</a> and <a href="/facts/Arithmetic_coding/WU0H4oNu">arithmetic coding</a> (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 <a href="/facts/Kullback%25E2%2580%2593Leibler_divergence/nh7SjlPE">Kullback–Leibler divergence</a> 
 
 
 
 
 D
 
 KL
 
 
 (
 Q
 ‖
 P
 )
 
 
 {\displaystyle D_{\text{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 <a href="/facts/Arithmetic_encoding/WU0H4oNu">arithmetic encoding</a>), the universal code would be preferable in cases where 
 
 
 
 
 D
 
 KL
 
 
 (
 Q
 ‖
 P
 )
 
 
 {\displaystyle D_{\text{KL}}(Q\|P)}
 
 is sufficiently small.
<a href="https://web.archive.org/web/20080807041150/http://www.cs.tut.fi/~albert/Dev/pucrunch/">Lossless Data Compression Program: Hybrid LZ77 RLE</a>
For any <a href="/facts/Geometric_distribution/c8wjfaoV">geometric distribution</a> (an exponential distribution on integers), a Golomb code is optimal. With universal codes, the implicit distribution is approximately a <a href="/facts/Power_law/DhAjYwwz">power law</a> such as 
 
 
 
 1
 
 /
 
 
 n
 
 2
 
 
 
 
 {\displaystyle 1/n^{2}}
 
 (more precisely, a <a href="/facts/Zipf_distribution/bspk1du8">Zipf distribution</a>).
For the <a href="/facts/Fibonacci_code/GXCLAf7t">Fibonacci code</a>, the implicit distribution is approximately 
 
 
 
 1
 
 /
 
 
 n
 
 q
 
 
 
 
 {\displaystyle 1/n^{q}}
 
, with

q
        =
        1
        
          /
        
        
          log
          
            2
          
        
        ⁡
        (
        φ
        )
        ≃
        1.44
        ,
      
    
    {\displaystyle q=1/\log _{2}(\varphi )\simeq 1.44,}

where 
 
 
 
 φ
 
 
 {\displaystyle \varphi }
 
 is the <a href="/facts/Golden_ratio/anloSRmD">golden ratio</a>. For the ternary <a href="/facts/Comma_code/rJIvE2IS">comma code</a> (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
 )
 ≃
 1.26
 
 
 {\displaystyle q=1+\log _{3}(4/3)\simeq 1.26}
 
. These distributions thus have near-optimal codes with their respective power laws.

<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.ics.uci.edu/~dan/pubs/DC-Sec3.html">Data Compression</a>, by Debra A. Lelewer and Daniel S. Hirschberg (<a href="/facts/University_of_California%2c_Irvine/gS3nEt3V">University of California, Irvine</a>)</li>
<li><a href="http://www.inference.phy.cam.ac.uk/mackay/itila/">Information Theory, Inference, and Learning Algorithms</a>, by <a href="/facts/David_MacKay_(scientist)/NK3D8JME">David MacKay</a>, has a chapter on codes for integers, including an introduction to Elias codes.</li>
<li><a href="https://web.archive.org/web/20070214150309/http://www-lat.compression.ru/download/integers.html">Кодирование целых чисел</a> has mostly English-language papers on universal and other integer codes.</li></ul>

Universal code (data compression) open-in-new

Universal code (data compression)