Arithmetic coding with dual symbol sets and its performance analysis

In this paper, we propose a novel adaptive arithmetic coding method that us es dual symbol sets: A primary symbol set that contains all the symbols tha t are likely to occur in the near future and a secondary symbol set that co ntains all other symbols. The simplest implementation of our method assumes that symbols that have appeared in the recent past are highly likely to ap pear in the near future. It therefore fills the primary set with symbols th at have occurred in the recent past. Symbols move dynamically between the t wo symbol sets to adapt to the local statistics of the symbol source. The p roposed method works well for sources, such as images, that are characteriz ed by large alphabets and alphabet distributions that are skewed and highly nonstationary, We analyze the performance of the proposed method and compa re it to other arithmetic coding methods, both theoretically and experiment ally, We show experimentally that in certain contexts, e.g,, with a wavelet -based image coding scheme that has recently appeared in the literature, th e compression performance of the proposed method is better than that of the conventional arithmetic coding method and the zero-frequency escape arithm etic coding method.