0=5):
Given this set of differences and the initial value (107), we can reconstruct the original sequence. Delta coding is the compression strategy where we store these differences instead of the original values. Some people like to think of delta coding as a predictive scheme: you constantly predict that the next value will be like the previous one, and you just code the difference between your prediction and the observed value.
In binary, the values 1,2,5,7 and 4 can be written as 001, 010, 101, 111, 100. If we did not have a negative value (-1), we could store these differences using only 3 bits per value. The negative value comes from the fact that our values are not entirely sorted (just locally so). However, as we shall see, this single negative value will cause us some trouble. How do we code the -1?
- The original values are 8-bit values. This means that -1 and 256-1 are the same numbers (modulo 256). That is 25+255 modulo 256 is 24. In effect, we compute differences in an integer ring. The differences become
1,2,5,5,5,7,0,255,4.Computing the modulo with a power of two is fast because computers use the binary format natively.
- If you know the value that was predicted (25 in our case). You know that the range of differences goes from -25 to 230. Thus for differences x between -25 and 25, we store them as 2x if it is positive and as -2x-1 if it is negative. Otherwise, we store it as x+25. One problem with this approach is that it may require much branching: the processor has to constantly check conditions before proceeding further. There may be a substantial penalty to pay when using modern superscalar processors.
Thankfully, you can use a trick called zig-zag encoding to avoid the branching. In effect, you map x to (x << 1) ^ (x >> 31) (in C or Java). This transformation can then be reversed by
mapping the result y to ((y >>> 1) ^ ((y << 31) >> 31) where >>> is the unsigned right shift.
- We can replace subtractions by bitwise exclusive or (xor) operations. It bypasses the issue entirely because xoring integers never generates negative values. The successive xor values are
7,2,29,11,5,249,0,7,4.A benefit of the xor operation is that it is symmetric: x xor y is y xor x. This means that inverting the order of the original list, we would simply invert the order of the list of differences. Obviously, computing the xor is quite fast.
Once we have the list of differences as non-negative numbers, we can then try to store them by using as few bits as possible. Unfortunately, in our case, we could to the conclusion that we need 8 bits to store the differences. We remarked however that for all but one value, 3 bits per difference would suffice.
So a sensible solution is to code the first 3 bits of each differences:
001, 010, 101, 101, 101, 111, 000, 111, 100. And then we add a pointer to the second last difference to indicate that we are missing 5 bits (11111). The cost of coding this exception is about 13 bits. So the total storage cost would be (8+3+9*3+13=51). In this case, frame-of-reference is preferable to delta coding, but both are preferable to the original 8-bit coding which used 80 bits.
There are many possible variations. For example, you can also use exception technique with the frame-of-reference approach when almost all values fit in a range of values, except for a few.
Further reading: the document SZIP Compression in HDF Products and the corresponding CCSDS 120.0-G-2 data compression standard describe the application of delta coding for scientific data. Michael Dipperstein’s page provides a nice overview of generic compression techniques. The specific exception technique I described is from the NewPFD scheme first described in:
H. Yan, S. Ding, T. Suel, Inverted index compression and query processing with optimized document ordering, in: WWW ’09, 2009.
See also my blog post How fast is bit packing?