Towards understanding and improving escape probabilities in PPM

The choice of expressions for the coding probabilities in general, and the escape probability in particular, is of great importance in the family of prediction by partial matching (PPM) algorithms. We present a parameterized version of the escape probability estimator which, together with a “compactness” criterion, provides guidelines for the estimator design given a “representative” set of files. This parameterization also makes it possible to adapt the expression of the escape probability during one-pass coding. Finally, we present results for one such compression scheme that illustrates the usefulness of our approach