An algorithm for universal lossless compression with side information

Haixiao Cai; Sanjeev R. Kulkarni; Sergio Verdú

doi:10.1109/TIT.2006.880020

An algorithm for universal lossless compression with side information

Haixiao Cai, Sanjeev R. Kulkarni, Sergio Verdú

Research output: Contribution to journal › Article › peer-review

20 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 χ₁ⁿ 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)
Pages (from-to)	4008-4016
Number of pages	9
Journal	IEEE Transactions on Information Theory
Volume	52
Issue number	9
DOIs	https://doi.org/10.1109/TIT.2006.880020
State	Published - Sep 2006

All Science Journal Classification (ASJC) codes

Information Systems
Computer Science Applications
Library and Information Sciences

Keywords

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

Access to Document

10.1109/TIT.2006.880020

Cite this

@article{ebb5762ab408421e9b8588fbb3f2bfc9,

title = "An algorithm for universal lossless compression with side information",

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

keywords = "Arithmetic coding, Conditional entropy, Context tree weighting method, Hidden Markov process, Source coding, Universal lossless data compression",

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

note = "Funding Information: Manuscript received May 10, 2005; revised May 9, 2006. This work was supported in part by ARL MURI under Grant DAAD19-00-1-0466, Draper Laboratory under IR&D 6002 Grant DL-H-546263, and the National Science Foundation under Grant CCR-0312413. The authors are with the Department of Electrical Engineering, Princeton University, Princeton, NJ 08544 USA (e-mail: hcai@princeton.edu; kulkarni@ princeton.edu; verdu@princeton.edu). Communicated by S. A. Savari, Associate Editor for Source Coding. Digital Object Identifier 10.1109/TIT.2006.880020",

year = "2006",

month = sep,

doi = "10.1109/TIT.2006.880020",

language = "English (US)",

volume = "52",

pages = "4008--4016",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "9",

}

TY - JOUR

T1 - An algorithm for universal lossless compression with side information

AU - Cai, Haixiao

AU - Kulkarni, Sanjeev R.

AU - Verdú, Sergio

N1 - Funding Information: Manuscript received May 10, 2005; revised May 9, 2006. This work was supported in part by ARL MURI under Grant DAAD19-00-1-0466, Draper Laboratory under IR&D 6002 Grant DL-H-546263, and the National Science Foundation under Grant CCR-0312413. The authors are with the Department of Electrical Engineering, Princeton University, Princeton, NJ 08544 USA (e-mail: hcai@princeton.edu; kulkarni@ princeton.edu; verdu@princeton.edu). Communicated by S. A. Savari, Associate Editor for Source Coding. Digital Object Identifier 10.1109/TIT.2006.880020

PY - 2006/9

Y1 - 2006/9

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

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

KW - Arithmetic coding

KW - Conditional entropy

KW - Context tree weighting method

KW - Hidden Markov process

KW - Source coding

KW - Universal lossless data compression

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

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

U2 - 10.1109/TIT.2006.880020

DO - 10.1109/TIT.2006.880020

M3 - Article

AN - SCOPUS:33748573657

SN - 0018-9448

VL - 52

SP - 4008

EP - 4016

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 9

ER -

An algorithm for universal lossless compression with side information

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this