An Algorithm for Universal Lossless Compression With Side Information

Author

Cai, Haixiao ; Kulkarni, Sanjeev R. ; Verdú, Sergio

Author_Institution

Dept. of Electr. Eng., Princeton Univ., NJ

Volume

52

Issue

9

fYear

2006

Firstpage

4008

Lastpage

4016

Abstract

This paper proposes a new algorithm based on the Context-Tree Weighting (CTW) 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

Keywords

Markov processes; data compression; decoding; entropy codes; probability; sequences; tree codes; CTW method; English text; Markov chain; context-tree weighting; decoder; encoder; entropy rate; finite-alphabet sequence; probability; side information; stationary ergodic source; universal lossless compression; Compression algorithms; Data compression; Decoding; Entropy; Hidden Markov models; Image coding; Image resolution; Protocols; Source coding; Video compression; Arithmetic coding; conditional entropy; context tree weighting method; hidden Markov process; source coding; universal lossless data compression;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2006.880020

Filename

1683922