Toward an abstract theory of data compression

AbstractThis paper extends the usual notion of abstract program size complexity, studied by Kolmogorov, Chaitin and others, to a theory that can better model the concept of a ‘practical’ compression method. The contraction of a string is defined, as in standard program size complexity, to be the shortest program which produces that string. However, this is in general an undecidable problem. Here, a model for an abstract compression ‘scheme’ is proposed. An abstract compression scheme not only allows the programming language and cost function to be specified, but also a restricted domain of programs that may be used as compressed forms. Limitations and inherent trade-offs are discussed and a class of ‘good’ schemes is considered