This paper proposes a new algorithm based on the Context-Tree Weighting (CTW) method for universal compression of a finite-alphabet sequence χ1n with side information y1n 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.
All Science Journal Classification (ASJC) codes
- Information Systems
- Computer Science Applications
- Library and Information Sciences