A universal finite memory source

Author

Weinberger, Marcelo J. ; Rissanen, Jorma J. ; Feder, Meir

Author_Institution

Hewlett-Packard Labs., Palo Alto, CA, USA

Volume

41

Issue

3

fYear

1995

fDate

5/1/1995 12:00:00 AM

Firstpage

643

Lastpage

652

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;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/18.382011

Filename

382011