An adaptive algorithm for the compression of computer data

A scheme for compressing computer data by treating them as sequences of bytes is described. For each individual sequence to be compressed, a source model of predetermined complexity is built adaptively starting from a memoryless model. An alphabet reduction technique which permits handling of each bit within a byte separately is introduced. Variable-order Markov contexts are generated for each bit within a byte by a process of selective context splitting. The selection of a context for splitting is based on the context's probability as well as the bit entropy under the context. Estimation of bit statistics under the different contexts is made adaptively and encoding is accomplished by an arithmetic code. The scheme allows the complexity of the source model, and thereby the compression performance, to be altered easily. Experiments on typical computer files show that the present scheme, at a moderate complexity level, often outperforms some of the existing schemes.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>