Lecture 12 min.
PPM (Prediction by Partial Matching) is an adaptive statistical lossless data compression algorithm based on context modeling and prediction. The PPM model uses a context, that is, the set of symbols in the uncompressed stream that precede the current one, to predict the value of a symbol from statistical data. The PPM model itself only predicts the symbol value; the actual compression is performed by entropy coding algorithms such as Huffman coding or arithmetic coding.
The length of the context used for prediction is usually strictly limited. This length is denoted n and determines the order of the PPM model, written PPM(n). Unbounded models also exist and are denoted simply PPM*. If a symbol cannot be predicted from a context of n symbols, an attempt is made to predict it using n-1 symbols. The recursive descent to models of lower order continues until the prediction succeeds in one of the models or until the context has zero length (n=0). The models of order 0 and −1 deserve special description. The order-0 model is equivalent to context-free modeling, in which the probability of a symbol is determined solely from its frequency of occurrence in the data stream being compressed. Such a model is usually used together with Huffman coding. The order −1 model is a static model that assigns a certain fixed value to the probability of a symbol; usually all symbols that may occur in the data stream being compressed are considered equally probable. To obtain a good estimate of a symbol's probability, contexts of different lengths must be taken into account. PPM is a variant of the blending strategy, in which probability estimates made from contexts of different lengths are combined into one overall probability. The resulting estimate is encoded by any entropy coder (EC), usually some kind of arithmetic coder. The compression itself takes place at the entropy coding stage.
| Definition: |
| Adaptive modeling (adaptive context modeling) is a modeling method in which the model changes during encoding according to a specified algorithm. |
| Definition: |
| Entropy coding (entropy coding) is the encoding of a sequence of values so that it can be uniquely restored, with the aim of reducing the amount of data by averaging the probabilities of occurrence of elements in the encoded sequence. |
The term PPMPPM is usually used to refer to context methods in general, so what follows considers a generalized PPMPPM algorithm.
PPMPPM (Prediction by partial matching) is an adaptive lossless data compression algorithm based on context modeling and prediction. Initially, the encoder and decoder are assigned an initial model of the data source. We will assume that it consists of CM(−1), which assigns the same probability to all symbols of the input sequence's alphabet. After processing the current symbol, the encoder and decoder modify their models in the same way, in particular increasing the probability estimate of the symbol in question. The next symbol is encoded (decoded) on the basis of the new, modified model, after which the model is modified again, and so on. At every step the identity of the encoder's and decoder's models is ensured by applying the same update mechanism.
If the symbol “s ” is processed with PPMPPM, then first CM(N) is considered. If it estimates the probability of “s ” with a nonzero number, it is used to encode “s ”. Otherwise a signal in the form of an escape symbol is emitted, and on the basis of the lower-order CM(N−1) another attempt is made to estimate the probability of “s ”. Encoding proceeds by escaping to CMCMs of lower orders until “s ” is estimated. CM(−1)CM(−1) guarantees that this will eventually happen. Thus, each symbol is encoded by a series of escape symbol codes followed by the code of the symbol itself. It follows that the escape probability can also be regarded as the probability of moving to a lower-order context model.
PPM only predicts the symbol value; the actual compression is performed by entropy coding algorithms such as Huffman coding or arithmetic coding.
The problem of handling new symbols that have not yet occurred in the input stream is of great importance for the PPM algorithm. This problem is called the zero-frequency problem. Some implementations of PPM set the count of a new symbol to a fixed value, for example one. Other implementations, such as PPM-D, increase the pseudo-count of the new symbol each time a new symbol actually appears in the stream (in other words, PPM-D estimates the probability of a new symbol appearing as the ratio of the number of unique symbols to the total number of symbols used).
Published research on the PPM family of algorithms appeared in the mid-1980s. Software implementations were not popular until the 1990s, because PPM models require a considerable amount of RAM. Modern PPM implementations are among the best lossless compression algorithms for natural-language text.
Research on this family of algorithms has been published since the mid-1980s. However, software implementations were not popular until the mid-1990s because of their high demand for volatile memory resources. The most recent PPM implementations are among the best lossless compression systems for natural-language text.
Suppose we have the symbol sequence “abcacabccbbbc” over the alphabet {a,b,c,d}, which has already been encoded.
Let the escape symbol count be one for all CMs, let symbol counts be incremented by one in all active CMs when the model is updated, let the exclusion method be applied, and let the maximum context length be three, i.e. N=3. Initially the model consists of CM(−1), in which the counts of all four symbols of the alphabet have the value 1. The state of the model after processing the sequence “abcacabccbbbc” is shown in Fig. 3, where rectangles denote context models; for each CM the context is given in italics, along with the symbols that have occurred in that context and their frequencies.
Let the current symbol be “d”, i.e. “?” = “d”; then its encoding proceeds as follows. First, the 3rd-order context “bbc” is examined. It has not occurred before, so the encoder, emitting nothing, moves on to analyze the statistics for the 2nd-order context. In this context (“bc”) the symbol “a” and the symbol “c” have occurred, with counts of 1 each in the corresponding CM, so the escape symbol is encoded with probability 1/(2+1), where 2 in the denominator is the observed frequency of the context “bc” and 1 is the value of the escape symbol count. In the 1st-order context “c”, the symbol “a” occurred twice and is excluded (masked), the symbol “c” occurred once and is also excluded, and “b” occurred once, so the estimate of the escape probability will be 1+1. In CM(0) the symbol “d” also cannot be estimated, and all the symbols “a”, “b”, “c” present in this CM are excluded, since they were already encountered in a higher-order CMCM. The escape probability therefore turns out to be one. The estimation cycle ends at the level of CM(−1), where “dd” is by now the only symbol not yet encountered, so it receives probability 1 and is encoded with 00 bits. Thus, with a good statistical encoder, representing “d” will require about 2.6 bits in total. Before the next symbol is processed, a CM is created for the string “bbc”, and the counts of the symbol “dd” are updated in the newly created CM and in all the CMs that were examined. In this case, CMs of all orders from 0 to N have to be changed
The decoding algorithm is completely symmetric to the encoding algorithm. After a symbol is decoded in the current CM, it is checked whether it is an escape symbol; if so, the decoder moves to the CMCM one order lower. Otherwise the original symbol is considered recovered, it is written to the decoded stream, and the decoder moves on to the next step. The content of the procedures for updating counts, creating new context models and other auxiliary actions, and the order in which they are applied, must be strictly identical in encoding and decoding. Otherwise the copies of the encoder's and decoder's models may become desynchronized, which sooner or later will lead to the erroneous decoding of some symbol. From that position on, the whole remaining part of the compressed sequence will be decompressed incorrectly. The difference between the codes of symbols whose probability estimates are equal is achieved by having the PPM predictor pass to the encoder the so-called cumulative frequencies (or cumulative probabilities) of the symbol being estimated and its neighbors, or the code spaces of the symbols. For example, for the context “bc”“bc” the following table can be compiled:
A good encoder should map the symbol “s” with probability estimate p(s) to a code of length log2p(s), which will ensure the compression of the whole sequence being processed.
| Definition: |
| The zero-frequency problem (zero frequency problem) is the problem of handling new symbols that have not yet occurred in the input stream. |
Today, two approaches to this problem can be distinguished: a priori methods, based on assumptions about the nature of the data being compressed, and adaptive methods, which try to adapt to the data being compressed.
Let us introduce the following notation:
The inventors of the PPM algorithm proposed two EPEEPE methods: the so-called method A and method B. The special cases of the PPMPPM algorithm that use these methods are called PPMA and PPMB respectively.
PPMA: EscA=1/(C+1)
PPMB: EscB=(Q−Q1)/C
Method C was developed later, followed by method D:
PPMC: EscC=Q/(C+Q)
PPMD: EscD=Q/(2⋅C)
| Definition: |
| SEE (Secondary Escape Estimation) is an estimation model that adapts to the data being processed. |
To find the EPEEPE, escape contextsescape contexts (Escape Context) are built, formed from various fields. A total of 44 fields are used, which contain information about:
The EPEEPE for the current context is found by weighting the estimates given by the three escape contexts (order−2 EC , order−1 EC, order−0 EC, corresponding to the current PPM context. Order−2 EC corresponds most precisely to the current context; the lower-order escape contexts are formed by discarding part of the information in the fields of order−2 EC.
When weighting the escape contexts, the following weights w are used:
, where p−EPE is the estimate given by the context being weighted.
The quantity formed from the actual number of successful encodings and the number of escapes in the PPM-contexts corresponding to this EC we denote as pi.
Variants of the PPM algorithm are currently widely used, mainly for compressing redundant information and text data. The following archivers use PPM :
Comments