A universal lossless compressor with side information based on context tree weighting

Haixiao Cai, Sanjeev R. Kulkarni, Sergio Verdú

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

This paper proposes a new algorithm based on the Context-Tree Weighting method for universal compression of a finite-alphabet sequence x 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)
Title of host publicationProceedings of the 2005 IEEE International Symposium on Information Theory, ISIT 05
Pages2340-2344
Number of pages5
DOIs
StatePublished - Dec 1 2005
Event2005 IEEE International Symposium on Information Theory, ISIT 05 - Adelaide, Australia
Duration: Sep 4 2005Sep 9 2005

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2005
ISSN (Print)2157-8099

Other

Other2005 IEEE International Symposium on Information Theory, ISIT 05
CountryAustralia
CityAdelaide
Period9/4/059/9/05

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A universal lossless compressor with side information based on context tree weighting'. Together they form a unique fingerprint.

Cite this