Towards Understanding and Probabilities in
J. Aberg, M. Shtarkov · 1997
The choice of expressions for the coding probabilities in general, and the escape probability in particular, is of great importance in the family of 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. Most noiseless data compression algorithms (coding methods) are based directly or indirectly on a statistical source model with (usually) unknown parameters. Thus any coding method requires to some degree a universal behavior with respect to the parameter values of this model. Simultaneously, the coding method must use as much as possible the specific properties of the model and any a priori knowledge of the range of values of its parameters. The theory of asymptotically universal source coding for different models and different sets of models is rather well developed. Nevertheless, attempts to implement its results directly in practical algorithms were, and are, not entirely successful. Thus the problem of the optimal combination of theoretical results and practical problems is important.