next up previous
Next: CTW algorithm Up: Unknown model Previous: Unknown model

Context tree

If the actual model of our tree source is not known, we can use a context tree to compute an appropriate coding distribution. A context tree (see figure 4) consists of nodes that correspond to contexts s up to a certain depth D. The root tex2html_wrap_inline3053 of the context tree corresponds to the empty context. Each node s in the context tree is associated with the subsequence of source symbols that occurred after context s.

Example:

   figure1140
Figure 4: The context tree splits up the source sequence.

Suppose that the source generated the sequence 0100110 while the past symbols were tex2html_wrap_inline2965 . Then the source symbols are partitioned by the context tree, see figure 4.



Ramesh Rao
Fri May 2 08:36:00 PDT 1997