Adaptive coding and prediction of sources with large and infinite alphabets

The problem of predicting a sequence generated by a discrete source with unknown statistics is considered. This problem is of great importance for data compression, because of its use to estimate probability distributions for PPM algorithms and other adaptive codes. This paper suggested a scheme of adaptive coding (and prediction) for a case where a source generates letters from an alphabet with unknown or infinite size. This scheme can be applied along with Laplace, Krichevsky and any other predictors. The general case of the prediction, which is based on such a grouping, is considered and the estimates of the redundancy are given.