PPM (for Prediction by Partial Matching or Prediction by partial recognition ) is a algorithm of Data compression without loss, statistics and adaptive.
Principle
The prediction by partial recognition bases a modeling of context to evaluate the probability of the various symbols.
Usually, the context is a whole of symbols already met in the data source (file, flow). The length of the context used for the prediction confers its order on the PPM. One notes PPM (NR) a PPM of order NR. For example, a PPM (1) is a PPM of order 1; i.e. that he predicts the following reason according to the only preceding symbol. One notes PPM* a PPM of an infinite nature; i.e. that he predicts the following reason according to the entirety of the data source already analyzed.
The context makes it possible to determine the probability of the various symbols thanks to a history of the entries: with each context the frequencies with appearance of the various symbols are associated.
In general , more the context used is long, better is the prediction.
A problem arising from the use of long contexts is the case of the empty history: when a given context is met for the first time. The two solutions most frequently brought are the use of probabilities fixed in advance and the dynamic change about the predictor. For example, if a PPM (8) does not have history for a context length 8, he seeks a history for a context length 7, then 6… until finding a history or to fall to order -1, in which case from the probabilities fixed in advance are used.
The prediction obtained is used as entry of another algorithm, generally of a arithmetic Codage or a Pondération of contexts.
Properties
PPM is a symmetrical algorithm. That means that it makes the same thing with compression and decompression. That also means that its speed is the same one in both cases (if one does not take account of subtleties of the input-outputs), and that the quantity of memory necessary (to store the history and the contexts) is identical.
Performances
The compression ratios obtained by PPMs among the best are obtained today, in particular on the text.The quantity of memory necessary varies very little with enormously. A PPM (0) requires very little memory, whereas a PPM* can exploit an infinite quantity of memory.
Speed, in particular of decompression, is the weak point of PPMs. Indeed, contrary to asymmetrical algorithms (like the family of the Lempel-Ziv), for which decompression comprises much less stages than compression, PPMs have a decompression strictly identical to compression.
| Random links: | Immigrant | Katherine Dunham | Jonas Lenn | Group nilpotent | Daniel Goleman |