An algorithm for universal lossless compression with side information

Haixiao Cai, Sanjeev R. Kulkarni, Sergio Verdú

Research output: Contribution to journalArticle

17 Scopus citations

Abstract

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
Volume52
Issue number9
DOIs
StatePublished - Sep 1 2006

All Science Journal Classification (ASJC) codes

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

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

  • Cite this