Implementing the PPM data compression scheme

IEEE Transactions on CommunicationsPublished 1 January 1990

Alistair Moffat

DOI10.1109/26.61469

Source URL

Citations420

SJR quartileQ1

SJR score3.49

SNIP2.62

TL;DR

It is shown that the estimates made by Cleary and Witten of the resources required to implement the PPM scheme can be revised to allow for a tractable and useful implementation.

Abstract

The prediction by partial matching (PPM) data compression algorithm developed by J. Cleary and I. Witten (1984) is capable of very high compression rates, encoding English text in as little as 2.2 b/character. It is shown that the estimates made by Cleary and Witten of the resources required to implement the scheme can be revised to allow for a tractable and useful implementation. In particular, a variant is described that encodes and decodes at over 4 kB/s on a small workstation and operates within a few hundred kilobytes of data space, but still obtains compression of about 2.4 b/character for English text.>

Keywords

Computer Science

IEEE Transactions on Information TheoryCompression of individual sequences via variable-rate coding

3,452 Citations1978J. Ziv, A. Lempel

The proposed concept of compressibility is shown to play a role analogous to that of entropy in classical information theory where one deals with probabilistic ensembles of sequences rather than with individual sequences.

Communications of the ACMArithmetic coding for data compression

2,861 Citations1987Ian H. Witten, Radford M. Neal +1 more

The state of the art in data compression is arithmetic coding, not the better-known Huffman method, which gives greater compression, is faster for adaptive models, and clearly separates the model from the channel encoding.

View PDF

IEEE Transactions on CommunicationsData Compression Using Adaptive Coding and Partial String Matching

1,250 Citations1984John J. Cleary, Ian H. Witten

This paper describes how the conflict can be resolved with partial string matching, and reports experimental results which show that mixed-case English text can be coded in as little as 2.2 bits/ character with no prior knowledge of the source.

Communications of the ACMA locally adaptive data compression scheme

530 Citations1986Jon Bentley, Daniel D. Sleator +2 more

It is proved that this data compression scheme never performs much worse than Huffman coding and can perform substantially better; experiments on real files show that its performance is usually quite close to that of Huffman coding.

View PDF

Journal of AlgorithmsDynamic huffman coding

445 Citations1985Donald E. Knuth

This note shows how to maintain a prefix code that remains optimum as the weights change, preserving minimality of the weighted path length in a Huffman tree.

The Computer JournalData Compression Using Dynamic Markov Modelling

212 Citations1987Gordon V. Cormack, R. Nigel Horspool

Experimental results reported here indicate that the Markov modelling approach generally achieves much better data compression than that observed with competing methods on typical computer data.

View PDF

Software Practice and ExperienceWord‐based text compression

174 Citations1989Alistair Moffat

The development of efficient algorithms to support arithmetic coding has meant that powerful models of text can now be used for data compression, and here the implementation of models based on recognizing and recording words is considered.

IEEE Transactions on Information TheoryInterval and recency rank source coding: Two on-line adaptive variable-length schemes

116 Citations1987Peter Eliaš

Both schemes can do much better than Huffman coding when successive selections of each message type cluster much more than in the independent case.

Variations on a theme by Ziv and Lempel

85 Citations1985Victor S. Miller, Mark N. Wegman

It is shown how these improvements in the area of dispensing with any uncompressed output, ability to use fixed size encoding tables by using a replacement strategy, and more rapid adaptation by widening the class of strings which may be added to the dictionary provide an adaptive probabilistic model for the input data.