The context-tree weighting method: extensions


First we modify the basic (binary) context-tree weighting method such that the past symbols x/sub 1-D/, x/sub 2-D/, ..., x/sub 0/ are not needed by the encoder and the decoder. Then we describe how to make the context-tree depth D infinite, which results in optimal redundancy behavior for all tree sources, while the number of records in the context tree is not larger than 2T-1. Here T is the length of the source sequence. For this extended context-tree weighting algorithm we show that with probability one the compression ratio is not larger than the source entropy for source sequence length T/spl rarr//spl infin/ for stationary and ergodic sources.

IEEE Transactions on Information Theory