Data compression

Reviewer: Ian Hugh Witten

This paper reviews the techniques of data compression that have been developed since Shannon's and Fano's pioneering work in the late 1940s. It deals exclusively with reversible (sometimes called noiseless) compression, where the decoder can recover exactly what the transmitter sent (barring transmission errors). Nonreversible methods are normally used for coding speech, gray-scale or color pictures, and telemetry data, where significantly increased compression can be obtained if one is satisfied with a high-fidelity approximation to the original signal rather than bit-for-bit reproduction. Reversible methods are used for text, program, and database compression, where errors cannot generally be tolerated. The authors have compiled an impressive variety of approaches to coding for data compression, including Shannon-Fano coding, Huffman coding and numerous elaborations such as efficient methods for adaptive Huffman coding, Elias's variable-length representation of the integers, Fibonacci codes, arithmetic coding, Ziv-Lempel methods, and an adaptive move-to-front word code. They quote a number of empirical results on coding efficiency from other papers. Several coding schemes that depend on the semantics of particular domains are mentioned, although the authors correctly point out that general-purpose methods can perform just as well and are less sensitive to the type of data being encoded. A number of applications are mentioned to motivate the survey, including commonly used file archival programs such as ARC, file compression systems such as UNIX compress, and even some work that apparently uses Huffman coding to find leaks in a pipeline. The past 40 years have been dominated by Huffman's algorithm, published in 1952; so is the paper, which devotes a large proportion of its length to this method. By choosing to cover the history of compression fairly evenly, the authors have given Huffman coding undue prominence, and consequently the primary methods currently used—arithmetic coding and Ziv-Lempel coding—receive short shrift. For this reason, while the paper may be excellent as historical background for new researchers, it is of limited value to the practitioner seeking to understand state-of-the-art compression methods. One of the reviewers has argued the benefits of arithmetic over Huffman coding elsewhere [1], and this is not the place to repeat those arguments. Suffice it to say that arithmetic coding gives greater compression, can be faster for adaptive methods, and clearly separates the model from the channel encoding. In this survey, however, aritmetic coding is tucked at the end of the section on nonadaptive methods (although the fact that it can be used adaptively is mentioned), while a substantial section is devoted to adaptive Huffman coding in its own right, quite apart from the material on nonadaptive Huffman coding. One of the most important advances in the theory of data compression over the last decade is the insight that data compression can be split into two parts: an encoder and a separate modeler that feeds information to it [2]. This survey is principally devoted to the study of coding, where a probability distribution (model) is assumed and particular messages are represented as compactly as possible based on these probabilities. The authors do not sufficiently stress this model-dependence, however. For example, they often speak of “the” entropy of a message as though it imposes a lower bound on the number of bits required for coding; this is of course only true with respect to a particular model of the source that generated the message. It is quite easy to represent text with fewer bits than its entropy calculated from letter frequencies would imply (for example, by using a model based on words). While this is obvious enough, it deserves to be emphasized. Indeed, although a wide range of coding algorithms are surveyed, only the simplest of models—those based on single-character frequencies—are considered. These are capable of only mediocre compression. More sophisticated models (for example, ones based on characters in context) are required to achieve better compression, but these are only touched on in the “New directions” section. The section on Ziv-Lempel coding is confused and confusing. The main algorithm described is Welch's version [3], but parts of the description pertain to other versions. The trouble is that these versions are moderately different from each other. For example, Welch's uses a fixed code length of 12 bits, which performs poorly on large files. The UNIX compress utility uses an increasing code length, and so it is not stuck with the behavior it learns initially. Also, the complexity of LZ coding is given as O( n 2), or O( n) with a complex data structure. This is true only of the version given by Even et al. [4]; others (including Welch's) can quite easily be implemented in O( n) time using a trie—indeed, some are O( n) with a linear search (see Ziv and Lempel [5]). Much of this confusion stems from the fact that Ziv and Lempel published two papers [5,6] that describe rather different methods for data compression, yet one invariably reads in the literature about “the” Ziv-Lempel method (and, to make matters worse, it is abbreviated with the initials reversed, as “LZ coding”). Most coding methods are optimal in one sense or another, and the authors mention many important optimality results. For example, Huffman's algorithm generates an optimal “defined-word” code (i.e., one with integer-length codes), Ziv and Lempel's 1978 method approaches the source entropy as the size of the input increases, and arithmetic coding represents the input in a number of bits that is arbitrarily close to its entropy with respect to the model used for coding. Unfortunately, the authors fail to point out the practical relevances of these. One is that arithmetic coding is guaranteed to give superior compression to Huffman coding, assuming that both are based on the same model. Another is that while Ziv-Lempel methods yield asymptotically optimal compression, they are exceedingly slow to approach the asymptote (and do so at the expense of unbounded memory requirements); in consequence, they are invariably outperformed by probability-based methods. The section on empirical results is disappointing because there is no comparison between the performance of the methods on the same test files. Instead, unrelated results from research papers are quoted, and in some cases these are not even converted to a common unit for comparison. The crucial influence of the underlying models on compression performance is hardly acknowledged. Also, there is little mention of the relative speeds of the methods, which is often an important factor in practice. A final section about errors considers in detail how each coding method performs when the encoded data are transmitted on a noisy channel. The authors might have pointed out that a code can only be robust if it contains redundancy, and that robustness is thus directly opposed to compression. It is far better to separate the two processes, making use of the wealth of error-correcting techniques available in the literature after the message has been compressed. The survey covers a wide range of coding methods in a fair amount of detail. It is particularly useful as a historical record of implementation techniques for the now-superseded method of Huffman coding. The main disappointment is that the reader may find it difficult to distinguish the relative merits of the bewildering battery of methods available.