Sequential prediction and ranking in universal context modeling and data compression

Most state-of-the-art lossless image compression schemes use prediction followed by some form of context modeling. This might seem redundant at first, as the contextual information used for prediction is also available for building the compression model, and a universal coder will eventually learn the “predictive” patterns of the data. In this correspondence, we provide a format justification to the combination of these two modeling tools, by showing that a combined scheme may result in faster convergence rate to the source entropy. This is achieved via a reduction in the model cost of universal coding. 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