Context-Based Compression - Introduction to Data Compression - page 164

T A B L E 6 . 5 Updated count array for

zero-order context.

Letter Count Cum _ Count

t 1 1

h 1 2

i 2 4

s 2 6

b 2 8

Esc 1 9

Total_Count 9

As the MSBs of l and u are the same, we shift the MSB out and shift 0 into the LSB of l and 1
into the LSB of u . The transmitted sequence is now 011. Having escaped out of the first-order
contexts, we examine Table 6.5 , the updated version of Table 6.2 , to see if we can encode t
using a zero-order context. Indeed we can, and using the Cum _ Count array, we can update l
and u :

0
9

l = 0 + ( 63 − 0 + 1 ) × = 0 = 000000

1
9

u = 0 + ( 63 − 0 + 1 ) × − 1 = 6 = 000110

The three most significant bits of both l and u are the same, so we shift them out. After the
update we get

Transmitted sequence: 011000

:

l 000000

u : 110111

bt has not occurred previously,
so we move directly to the first-order context t . The letter h has occurred previously in this
context, so we update l and u and obtain

The next letter to be encoded is h . The second-order context /

Transmitted sequence : 0110000

l : 000000

u : 110101

The method of encoding should now be clear. At this point the various counts are as shown
in Tables 6.6 - 6.8 .

Now that we have an idea of how the ppm algorithm works, let's examine some of the
variations.