Hausdorff dimension as a new dimension in source coding andpredicting

摘要

It is generally accepted that investigations in universal codingand predicting are based on the model of stationary ergodic sources. Inthis report we show that this model does not give possibilities toinvestigate large important classes of source codes and to distinguishasymptotic performances of popular universal codes. A new approachsuggested here is to consider a set of all infinite sequences (over agiven alphabet) and estimate the size of sets of compressible sequenceswith the help of Hausdorff dimension. This approach enables us, first,to show that there exist large sets of well compressible (andpredictable) sequences which have got zero measure for every stationaryand ergodic measure, and second, to distinguish an asymptotic efficiencyof LZ codes and codes that are based on the technique of model weighting