A universal lossless compressor with side information based on context tree weighting
Haixiao Cai, Sanjeev R. Kulkarni, Sergio Verdú · 2005
This paper proposes a new algorithm based on the context-tree weighting method for universal compression of a finite-alphabet sequence x/sub 1//sup n/ with side information y/sub 1//sup n/ available to both the encoder and decoder. We prove that with probability one the compression ratio converges to the conditional entropy rate for jointly stationary ergodic sources. Experimental results with Markov chains and English texts show the effectiveness of the algorithm.