Hausdorff dimension as a new dimension in source coding and predicting
Boris Ya. Ryabko, Joe Suzuki, Flemming Topsøe · 2003
It is generally accepted that investigations in universal coding and predicting are based on the model of stationary ergodic sources. In this report we show that this model does not give possibilities to investigate large important classes of source codes and to distinguish asymptotic performances of popular universal codes. A new approach suggested here is to consider a set of all infinite sequences (over a given alphabet) and estimate the size of sets of compressible sequences with the help of Hausdorff dimension. This approach enables us, first, to show that there exist large sets of well compressible (and predictable) sequences which have got zero measure for every stationary and ergodic measure, and second, to distinguish an asymptotic efficiency of LZ codes and codes that are based on the technique of model weighting.