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: [email protected]; kulkarni@ princeton.edu; [email protected]). 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 -