Note on the DMC data compression scheme

Abstract

Until recently, the best schemes for text compression have used variable-order Markov models, i.e. each symbol is predicted using some finite number of directly preceding symbols as a context. The recent Dynamic Markov Compression (DMC) scheme models data with finite state automata, which are capable of representing more complex contexts than simple Markov models. The DMC scheme builds models by 'cloning' states which are visited often. Because patterns can occur in English which can be recognized by a finite state automation, but not by a variable-order Markov model, the use of FSA model is potentially more powerful.