Title :
A universal finite memory source
Author :
Weinberger, Marcelo J. ; Rissanen, Jorma J. ; Feder, Meir
Author_Institution :
Hewlett-Packard Labs., Palo Alto, CA, USA
fDate :
5/1/1995 12:00:00 AM
Abstract :
An irreducible parameterization for a finite memory source is constructed in the form of a tree machine. A universal information source for the set of finite memory sources is constructed by a predictive modification of an earlier studied algorithm-Context. It is shown that this universal source incorporates any minimal data-generating tree machine in an asymptotically optimal manner in the following sense: the negative logarithm of the probability it assigns to any long typical sequence, generated by any tree machine, approaches that assigned by the tree machine at the best possible rate
Keywords :
encoding; information theory; prediction theory; probability; sequences; tree data structures; Context; irreducible parameterization; minimal data-generating tree machine; negative logarithm; predictive modification; probability; sequence; tree machine; universal finite memory source; universal information source; Automata; Context modeling; Data compression; Explosives; Information theory; Predictive models; Senior members; State estimation; Statistics; Stochastic processes;
Journal_Title :
Information Theory, IEEE Transactions on
