Prediction and adaptive coding of sources with large or infinite alphabet

This paper suggests a scheme of adaptive coding and prediction for a case where a source generates letters from an alphabet with unknown (and even infinite) size. This scheme can be applied along with any predictor; here we use the Laplace predictor as the main example. We consider a case of prediction for i.i.d. sources, but all results can be easily extended to Markov sources. The suggested scheme is described using the tree notation.