| |
Click here for full text:
Linear Time Universal Coding and Time Reversal of Tree Sources via FSM Closure
Martin, Alvaro; Seroussi, Gadiel; Weinberger, Marcelo J.
HPL-2003-87R2
Keyword(s): tree sources; finite state machines; finite memory; Context algorithm; universal coding; suffix trees
Abstract: Tree models are efficient parametrizations of finite- memory processes, offering potentially significant model cost savings. The information theory literature has focused mostly on redundancy aspects of the universal estimation and coding of these models. In this paper, we investigate representations and supporting data structures for finite-memory processes, as well as the major impact these structures have on the computational complexity of the universal algorithms in which they are used. We first generalize the class of tree models, and then define and investigate the properties of the finite state machine (FSM) closure of a tree, which is the smallest FSM that generates all the processes generated by the tree. The interaction between FSM closures, generalized context trees, and classical data structures such as compact suffix trees brings together the information-theoretic and the computational aspects, leading to an implementation in linear encoding/ decoding time of the semi-predictive approach to the Context algorithm, a lossless universal coding scheme in the class of tree models. An optimal context selection rule and the corresponding context transitions are computationally not more expensive than the various steps involved in the implementation of the Burrows-Wheeler transform (BWT) and use, in fact, similar tools. We also present a reversible transform that displays the same "context deinterleaving" feature as the BWT but is naturally based on an optimal context tree. FSM closures are also applied to an investigation of the effect of time reversal on tree models, motivated in part by the following question: When compressing a data sequence using a universal scheme in the class of tree models, can it make a difference whether we read the sequence from left to right or from right to left? Given a tree model of a process, we show constructively that the number of states in the tree model corresponding to the reversed process might be, in the extreme case, quadratic in the number of states of the original tree. This result answers the above motivating question in the affirmative. Notes: Copyright IEEE. To be published in the IEEE Transactions on Information Theory
50 Pages
Back to Index
|
Printable version
