A UNIVERSAL DATABASE FOR DATA-COMPRESSION

A data-base for data compression is universal if in its construction n o prior knowledge of the source distribution is assumed and is optimal if, when we encode the reference index of the data-base, its encoding rate achieves the optimal encoding rate for any given source: in the noiseless case the entropy rate and in the semifaithful case the rate- distortion function of the source. In the present paper, we construct a universal data-base for all stationary ergodic sources, and prove th e optimality of the thus constructed data-base for two typical methods of referring to the data-base: one is a block-shift type reference an d the other is a single-shift type referrence.