HP Labs Technical Reports

Sequential Prediction and Ranking in Universal Context Modeling and Data Compression

Weinberger, Marcelo J.; Seroussi, Gadiel

HPL-94-111 (R.1)

Keyword(s): universal coding, Context algorithm, prediction, ranking, image compression

Abstract: Prediction is one of the oldest and most successful tools in practical data compression. It is particularly useful in applications like image compression, where the data samples represent a continuously varying physical process. The usual explanation for the beneficial effect of prediction is that it decorrelates the data, allowing the use of simple encoders for the sequence of prediction errors. It has been noted, though, both in theory and in practice, that prediction alone cannot achieve total decorrelation in general, even in the case of universal prediction. In fact, most state-of-the-art image compression schemes use prediction followed by some form of context modeling. This, however, might seem redundant at first, as the context information used for prediction is also available for building the compression model, and a universal modeler will eventually learn the "predictive" patterns of the source. Thus, the following questions arise: Why use two different modeling tools based on the same contextual information, and how do these tools interact? In this paper, we provide answers to these questions, and we investigate the use of prediction as a means of reducing the model cost in universal lossless data compression. We provide a formal justification to the combination of this tool with a universal code based on context modeling, by showing that a combined scheme may result in faster convergence rate to the source entropy. In deriving the main result, we develop the concept of sequential ranking, which can be seen as a generalization of sequential prediction, and we study its combinatorial and probabilistic properties.

Back to Index