Definition
The PPMIICoder is based on the compression scheme
``Prediction by Partial Matching with Information Inheritance''
by D. Shkarin [81].
This coder works as follows: Suppose we have processed the first n - 1 symbols x1...xn-1 of the stream. Before reading the next symbol xn we try to guess it, i.e. for every symbol s we estimate the probability p(s) for the event ``xn = s''. This probability distribution determines how the next symbol is encoded: The higher p(s), the fewer bits are used for encoding s. If our estimation is good, which means that p(xn) is high, then we obtain a good compression rate.
In order to predict the probality distribution for the nth symbol the PPM approach considers the preceding k symbols xn-k...xn-1. We call these symbols the context of xn and k the order of the model. (For k = 0 we obtain the order-0 model from the previous section.) E.g., if the current context is ``req'', then we should predict the letter ``u'' as next symbol with high probability.
PPMII is a variant of PPM which usually achieves very accurate estimations.
The PPMIICoder combines very good compression rates with acceptable speed. (Shkarin [81] reports that his coder outperforms ZIP and BZIP2 with respect to compression rates and speed.) The only disadvantage of this coder is that it needs a fair amount of main memory to store the model. However, the user can set an upper bound on the memory usage. And he can specify which model restoration method the coder shall apply when it runs out of memory:
#include < LEDA/coding/PPMII.h >
Types
Creation
Operations
Standard Operations
Additional Operations
Implementation
Our implementation encapsulates the code by D. Shkarin (the implementation of the PPMII model) and by D. Subbotin (the implementation of the range coder).