Variations on a theme by Ziv and Lempel.

Abstract

The data compression methods of J. Ziv and A. Lempel (1976) are modified and augmented in three ways in order to improve the compression ratio and hold the size of the encoding tables to a fixed size. The improvements are 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. It is shown how these improvements also provide an adaptive probabilistic model for the input data. The issue of data structures for efficient implementation is also addressed.