ZPCodec Examples

Suggestions for efficiently using the ZP-Coder.
Binary adaptive coders are efficient and very flexible. Unfortunate intellectual property issues however have limited their popularity. As a consequence, few programmers have a direct experience of using such a coding device. The few examples provided in this section demonstrate how we think the ZP-Coder should be used.

Encoding Multivalued Symbols --- Since the ZP-Coder is a strictly binary coder, every message must be reduced to a sequence of bits (0s or 1s). It is often convenient to consider that a message is a sequence of symbols taking more than two values. For instance, a character string may be a sequence of bytes, and each byte can take 256 values. Each byte of course is composed of eight bits that we can encode in sequence. The real issue however consists of deciding how we will use context variables in order to let the ZP-Coder learn the probability distribution of the byte values.

The most significant bit b0 decides whether the byte is in range 0..127 or in range 128..255. We let the ZP-Coder learn how to predict this bit by allocating one context variable for it. The second most significant byte b1 has two distinct meanings depending of bit b0. If bit b0 is 0, bit b1 decides whether the byte is in range 0..63 or 64..127. If bit b0 is 1, bit b1 decides whether the byte is in range 128..191 or 192..255. The prediction for bit b1 must therefore depend on the value of b0. This is why we will allocate two context variables for this bit. If bit b0 is 0, we will use the first variable; if bit b0 is 1, we will use the second variable. The next bit b2 has four meanings and therefore we will use four context variables, etc. This analysis leads to a total of 1+2+4+...+128 = 255 context variables for encoding one byte. This encoding procedure can be understood as a binary decision tree with a dedicated context variable for predicting each decision.

    [>=128]----n---[>=64?]----n----[>31?]  ... 
           \              `---y----[>95?]  ...
            \
             `--y---[>=192?]----n---[>=160?] ...
                            `---y---[>=224?] ...
    
The following decoding function illustrates a very compact way to implement such a decision tree. Argument ctx points to an array of 255 BitContext variables. Macro REPEAT8 is a shorthand notation for eight repetitions of its argument.
    int decode_8_bits(ZPCodec &zp, BitContext *ctx )
    {
      int n = 1;
      REPEAT8( { n = (n<<1) | (zp.decoder(ctx[n-1])); } );
      return n & 0xff;
    }
    
The binary representation of variable n is always composed of a 1 followed by whichever bits have been decoded so far. This extra bit 1 in fact is a nice trick to flatten out the tree structure and directly address the array of context variables. Bit b0 is decoded using the first context variable since n is initially 1. Bit b1 is decoded using one of the next two variables in the array, since n is either 2 (10 in binary) or 3 (11 in binary). Bit b2 will be decoded using one of the next four variables, since n ranges from 4 (100 in binary) to 7 (111 in binary). The final result is given by removing the extra 1 in variable n.

The corresponding encoding function is almost as compact. Argument ctx again is an array of 255 BitContext variables. Each bit of byte x is encoded and shifted into variable n as in the decoding function. Variable x in fact contains the bits to be encoded. Variable n contains a 1 followed by the already encoded bits.

    void encode_8_bits(ZPCodec &zp, int x, BitContext *ctx )
    {
      int n = 1;
      REPEAT8( { int b=((x&0x80)?1:0);  x=(x<<1);
                 zp.encoder(b,ctx[n-1]);  n=(n<<1)|(b); } );
    }
    
The ZP-Coder automatically adjusts the content of the context variables while coding (recall the context variable argument is passed to functions

variables can be understood as a "byte context variable". The estimated probability of each byte value is indeed the product of the estimated probabilities of the eight binary decisions that lead to that value in the decision tree. All these probabilities are adapted by the underlying adaptation algorithm of the ZP-Coder.

Application --- We consider now a simple applications consisting of encoding the horizontal and vertical coordinates of a cloud of points. Each coordinate requires one byte. The following function illustrates a possible implementation:

    void encode_points(const char *filename, int n, int *x, int *y)
    {
       StdioByteStream bs(filename, "wb");
       bs.write32(n);             // Write number of points.
       ZPCodec zp(bs, 1);         // Construct encoder and context vars.
       BitContext ctxX[255], ctxY[255];
       memset(ctxX, 0, sizeof(ctxX));
       memset(ctxY, 0, sizeof(ctxY));
       for (int i=0; i<n; i++) {  // Encode coordinates.
          encode_8_bits(zp, x[i], ctxX);
          encode_8_bits(zp, y[i], ctxY);
       }
    }
    
The decoding function is very similar to the encoding function:
    int decode_points(const char *filename, int *x, int *y)
    {
       StdioByteStream bs(filename,"rb");
       int n = bs.read32();      // Read number of points.
       ZPCodec zp(bs, 0);        // Construct decoder and context vars.
       BitContext ctxX[255], ctxY[255];
       memset(ctxX, 0, sizeof(ctxX));
       memset(ctxY, 0, sizeof(ctxY));
       for (int i=0; i<n; i++) { // Decode coordinates.
         x[i] = decode_8_bits(zp, ctxX);
         y[i] = decode_8_bits(zp, ctxY);
       }
       return n;                 // Return number of points.
    }
    
The ZP-Coder automatically estimates the probability distributions of both the horizontal and vertical coordinates. These estimates are used to efficiently encode the point coordinates. This particular implementation is a good option if we assume that the order of the points is significant and that successive points are independent. It would be much smarter otherwise to sort the points and encode relative displacements between successive points.

Huffman Coding Tricks --- Programmers with experience in Huffman codes can see the similarity in the ZP-Coder. Huffman codes also organize the symbol values as a decision tree. The tree is balanced in such a way that each decision is as unpredictable as possible (i.e. both branches must be equally probable). This is very close to the ZP-Coder technique described above. Since we allocate one context variable for each decision, our tree need not be balanced: the context variable will track the decision statistics and the ZP-Coder will compensate optimally.

There are good reasons however to avoid unbalanced trees with the ZP-Coder. Frequent symbol values may be located quite deep in a poorly balanced tree. This increases the average number of message bits (the number of decisions) required to code a symbol. The ZP-Coder will be called more often, making the coding program slower. Furthermore, each message bit is encoded using an estimated distribution. All these useless message bits mean that the ZP-Coder has more distributions to adapt. This extra adaptation work will probably increase the file size.

Huffman codes are very fast when the tree structure is fixed beforehand. Such static Huffman codes are unfortunately not very efficient because the tree never matches the actual data distribution. This is why such programs almost always define a data dependent tree structure. This structure must then be encoded in the file since the decoder must know it before decoding the symbols. Static Huffman codes however become very efficient when decisions are encoded with the ZP-Coder. The tree structure represents a priori knowledge about the distribution of the symbol values. Small data discrepancies will be addressed transparently by the ZP-Coder.

Encoding Numbers --- This technique is illustrated with the following number encoding example. The multivalued technique described above is not practical with large numbers because the decision tree has too many nodes and requires too many context variables. This problem can be solved by using a priori knowledge about the probability distribution of our numbers.

Assume for instance that the distribution is symmetrical and that small numbers are much more probable than large numbers. We will first group our numbers into several sets. Each number is coded by first coding which set contains the number and then coding a position within the set. Each set contains 2^n numbers that we consider roughly equiprobable. Since the most probable values occur much more often, we want to model their probability more precisely. Therefore we use small sets for the most probable values and large sets for the least probable values, as demonstrated below.

 
    A---------------- {0}                                 (size=1)
     `------B---C---- {1}            or {-1}              (size=1)
             \   `--- {2,3}          or {-2,-3}           (size=2)
              D------ {4...131}      or {-4...-131}       (size=128)
               `----- {132...32899}  or {-132...-32899}   (size=32768)
    
We then organize a decision tree for coding the set identifier. This decision tree is balanced using whatever a priori knowledge we have about the probability distribution of the number values, just like a static Huffman tree. Each decision (except the sign decision) is then coded using a dedicated context variable.
        if (! zp.decoder(ctx_A)) {             // decision A
           return 0;
        } else {
           if (! zp.decoder(ctx_B)) {          // + decision B
             if (! zp.decoder(ctx_C)) {        // ++ decision C
               if (! zp.decoder())             // +++ sign decision
                 return +1;
               else
                 return -1;
             } else {
               if (! zp.decoder())             // +++ sign decision
                 return + 2 + zp.decoder();
               else
                 return - 2 - zp.decoder();
             }
           } else {
             if (! zp.decoder(ctx_D)) {        // ++ decision D
               if (! zp.decoder())             // +++ sign decision
                 return + 4 + decode_7_bits(zp);
               else
                 return - 4 - decode_7_bits(zp);
             } else {
               if (! zp.decoder())             // +++ sign decision
                 return + 132 + decode_15_bits(zp);
               else
                 return - 132 - decode_15_bits(zp);
             }
           }
        } 
   
Note that the call zp.decoder() for coding the sign decision does not use a context variable. This is a "pass-thru" variant of decoder which bypasses the ZP-Coder and just reads a bit from the code sequence. There is a corresponding "pass-thru" version of encoder for encoding such bits. Similarly, functions decode_7_bits and decode_15_bits do not take an array of context variables because, unlike function decode_8_bits listed above, they are based on the pass-thru decoder instead of the regular decoder.

The ZP-Coder will not learn the probabilities of the numbers within a set since no context variables have been allocated for that purpose. This could be improved by allocating additional context variables for encoding the position within the smaller sets and using the regular decoding functions instead of the pass-thru variants. Only experimentation can tell what works best for your particular encoding problem.

Understanding Adaptation --- We have so far explained that the ZP-Coder adaptation algorithm is able to quickly estimate of the probability distribution of the message bits coded using a particular context variable. It is also able to track slow variations when the actual probabilities change while coding.

Let us consider the ``cloud of points'' application presented above. Suppose that we first code points located towards the left side and then slowly move towards points located on the right side. The ZP-Coder will first estimate that the X coordinates are rather on the left side. This estimation will be progressively revised after seeing more points on the right side. Such an ordering of the points obviously violates the point independence assumption on which our code is based. Despite our inexact assumptions, the tracking mechanism allows for better prediction of the X coordinates and therefore better compression.

However, this is not a perfect solution. The ZP-Coder tracks the changes because every point seems to be a little bit more on the right side than suggested by the previous points. The ZP-Coder coding algorithm is always slightly misadjusted and we always lose a little on possible compression ratio. This is not much of a problem when the probabilities drift slowly. On the other hand, this can be very significant if the probabilities change drastically.

Adaptation is always associated with a small loss of efficiency. The ZP-Coder updates the probability model whenever it suspects, after coding, that the current settings were not optimal. The model will be better next time, but a slight loss in compression has occurred. The design of ZP-Coder of course minimizes this effect as much as possible. Yet you will pay a price if you ask too much to the adaptation algorithm. If you have millions of context variables, it will be difficult to train them all. If the probability distributions change drastically while coding, it will be difficult to track the changes fast enough.

Adaptation on the other hand is a great simplification. A good data compression program must (a) represent the data in order to make its predictability apparent, and (b) perform the predictions and generate the code bits. The ZP-Coder is an efficient and effortless solution for implementing task (b).

Practical Debugging Tricks --- Sometimes you write an encoding program and a decoding program. Unfortunately there is a bug: the decoding program decodes half the file and then just outputs garbage. There is a simple way to locate the problem. In the encoding program, after each call to encoded bit and the value of the context variable. In the decoding program, after each call to decoder, print the decoded bit and the value of the context variable. Both program should print exactly the same thing. When you find the difference, you find the bug.

Alphabetic index Hierarchy of classes


DjVu is a trademark of LizardTech, Inc.
All other products mentioned are registered trademarks or trademarks of their respective companies.