Williams R.N. Adaptive Data Compression

Kluwer, 1991. — 403 p.The class of Markov data compression algorithms provides the best known compression for ordinary symbol data. Of these, the PPM (Prediction by Partial Matching) algorithm by Cleary and Witten (1984) is the most successful. This thesis reviews the class of Markov algorithms and introduces algorithms similar to PPM which are used as a vehicle for examining adaptivity in data compression algorithms in general.
Despite the amount of research into adaptive data compression algorithms, the term "adaptive" is not well defined. The term can be clarified by viewing the problem of adapting as that of tracking a source through a source space using the data the source is generating as a trail. Adaptive algorithms achieve this by making assumptions about source trajectories. These assumptions can be used to classify data compression algorithms into four groups with respect to adaptivity: not adaptive, initially adaptive, asymptotically adaptive and locally adaptive. These groups correspond roughly to classes of source trajectory. A new class of source called multimodal sources is introduced, members of which jump among a finite number of distinct points in the source space.
After common source trajectories have been identified, modifications to Markov algorithms are described that enable them to track each kind of source. Some of the modifications involve complex algorithms which are discussed in detail. Experimental results show that these modifications can substantially improve compression performance.
Of particular interest are sources with a multimodal trajectory. Such sources can be compressed well using a combination of locally adaptive and asymptotically adaptive models. The result is a multimodal algorithm which is independent of any particular sub-model. Experimental results support this approach.
Finally, there is a discussion of the possible applications of data compression techniques in the field of user interfaces. By predicting the user's behavior and presenting the predictions to the user in an invokable form, it is possible to eliminate redundancy in the user interface just as it can be eliminated in data streams.Introductory Survey
The DHPC Algorithm
A Classification of Adaptivity
An Experimental Adaptive Algorithm
A Multimodal Algorithm
Applications to User InterfacesA: Estimation Formula Calculation
B: The Word "Adapt" And Its Forms
C: User Input Experiments
D: Further Research
E: Summary of Notation