Generalized Context Trees and their FSM Closure

摘要

We investigate models and supporting data structures for finite-memory processes. First, we generalize the class of tree models, letting the model structure take the form of a compact digital tree. In the extended model, the trees need not be full and the edges may be compacted. This richer model class offers potentially significant improvements in model fitting capability relative to the usual full-tree models. We prove necessary and sufficient conditions for a generalized tree model to be minimal. Second, we define and study the properties of the finite state machine (FSM) closure of a tree, which is the smallest FSM refinement of the tree. This investigation is instrumental in showing that a two-pass version of Context, a twice-universal lossless coding scheme for tree models, can be implemented in linear encoding/decoding time.