A Universal Data-Base for Data Compression


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E78-A   No.9   pp.1057-1062
Publication Date: 1995/09/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
data compression,  universal code,  data-base,  index function,  complexity,  distortion-complexity,  

Full Text: PDF>>
Buy this Article

A data-base for data compression is universal if in its construction no 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 the optimality of the thus constructed data-base for two typical methods of referring to the data-base: one is a block-shift type reference and the other is a single-shift type reference.