Title :
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
Abstract :
This paper proposes a new algorithm based on the Context-Tree Weighting (CTW) method for universal compression of a finite-alphabet sequence x1 n with side information y1 n 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;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.2006.880020
