An algorithm for universal lossless compression with side information

Haixiao Cai, Sanjeev R. Kulkarni, Sergio Verdú

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)4008-4016
Number of pages9
JournalIEEE Transactions on Information Theory
Issue number9
StatePublished - Sep 2006

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • Arithmetic coding
  • Conditional entropy
  • Context tree weighting method
  • Hidden Markov process
  • Source coding
  • Universal lossless data compression


Dive into the research topics of 'An algorithm for universal lossless compression with side information'. Together they form a unique fingerprint.

Cite this