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

Haixiao Cai; Sanjeev R. Kulkarni; Sergio Verdú

doi:10.1109/ISIT.2005.1523766

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 proceeding › Conference contribution

6 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 ₁ⁿ with side information y₁ⁿ 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 language	English (US)
Title of host publication	Proceedings of the 2005 IEEE International Symposium on Information Theory, ISIT 05
Pages	2340-2344
Number of pages	5
DOIs	https://doi.org/10.1109/ISIT.2005.1523766
State	Published - 2005
Event	2005 IEEE International Symposium on Information Theory, ISIT 05 - Adelaide, Australia Duration: Sep 4 2005 → Sep 9 2005

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2005
ISSN (Print)	2157-8099

Other

Other	2005 IEEE International Symposium on Information Theory, ISIT 05
Country/Territory	Australia
City	Adelaide
Period	9/4/05 → 9/9/05

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2005.1523766

Cite this

Cai, H., Kulkarni, S. R., & Verdú, S. (2005). A universal lossless compressor with side information based on context tree weighting. In Proceedings of the 2005 IEEE International Symposium on Information Theory, ISIT 05 (pp. 2340-2344). Article 1523766 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2005). https://doi.org/10.1109/ISIT.2005.1523766

@inproceedings{ca4b3b9aed7d4ec49345324560a1daf4,

title = "A universal lossless compressor with side information based on context tree weighting",

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.",

author = "Haixiao Cai and Kulkarni, {Sanjeev R.} and Sergio Verd{\'u}",

year = "2005",

doi = "10.1109/ISIT.2005.1523766",

language = "English (US)",

isbn = "0780391519",

series = "IEEE International Symposium on Information Theory - Proceedings",

pages = "2340--2344",

booktitle = "Proceedings of the 2005 IEEE International Symposium on Information Theory, ISIT 05",

note = "2005 IEEE International Symposium on Information Theory, ISIT 05 ; Conference date: 04-09-2005 Through 09-09-2005",

}

Cai, H, Kulkarni, SR & Verdú, S 2005, A universal lossless compressor with side information based on context tree weighting. in Proceedings of the 2005 IEEE International Symposium on Information Theory, ISIT 05., 1523766, IEEE International Symposium on Information Theory - Proceedings, vol. 2005, pp. 2340-2344, 2005 IEEE International Symposium on Information Theory, ISIT 05, Adelaide, Australia, 9/4/05. https://doi.org/10.1109/ISIT.2005.1523766

A universal lossless compressor with side information based on context tree weighting. / Cai, Haixiao; Kulkarni, Sanjeev R.; Verdú, Sergio.
Proceedings of the 2005 IEEE International Symposium on Information Theory, ISIT 05. 2005. p. 2340-2344 1523766 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2005).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Cai, Haixiao

AU - Kulkarni, Sanjeev R.

AU - Verdú, Sergio

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33749427178&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33749427178&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2005.1523766

DO - 10.1109/ISIT.2005.1523766

M3 - Conference contribution

AN - SCOPUS:33749427178

SN - 0780391519

SN - 9780780391512

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2340

EP - 2344

BT - Proceedings of the 2005 IEEE International Symposium on Information Theory, ISIT 05

T2 - 2005 IEEE International Symposium on Information Theory, ISIT 05

Y2 - 4 September 2005 through 9 September 2005

ER -

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

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this