An adaptive dependency source model for data compression

Reviewer: Timothy C. Bell

This paper describes a novel method for data compression that was inspired by a recent description of arithmetic coding [1]. The method is relatively simple to implement, although its compression and speed characteristics are not competitive with currently popular techniques such as Ziv-Lempel coding. Like Huffman coding, arithmetic coding achieves compression by representing high probability symbols with a small number of bits and vice versa. Arithmetic coding performs near optimally for a given probability distribution; the real challenge is to determine the probabilities as accurately as possible, a task known as modeling. Witten, Neal, and Cleary demonstrate arithmetic coding with a simple model that uses a character's relative frequency as an estimate of its probability [1]. Abrahamson observes that considering a character's context will result in a more accurate estimate. For example, while the relative frequency of a u in English text is normally low, after the letter q it is high. Although Abrahamson does not use the term, such a model is often called a first-order context model. Witten, Neal, and Cleary mention context models in passing and refer to a method that uses contexts to achieve a particularly good compression rate (they quote a compression of 2.2 bits/character on English text) [2]. Abrahamson's proposed scheme is not a full first-order model. It maintains the rank of the characters for each first-order context (where frequency determines rank). To code a character, the scheme determines its rank for the current context and codes this rank via an adaptive zero-order model. This approach works best when the probability distribution of ranks is independent of the context, but such a situation is unlikely to occur in practice. Abrahamson empirically compares the compression of his scheme to that of a straight zero-order model and finds that his method performs a little better, with a compression of 3.9 bits/character for a file of English text. He pays considerable attention to the periodic halving of frequency counts in order to achieve a recency effect, including two rather unconventional graphs that show the relationship between halving frequency, speed, and compression. Although the proposed compression method compares favorably with some simple methods, it offers little advantage over Ziv-Lempel methods (which are fast and give at least as good compression) or high-order context models like those of Cleary and Witten [2] (which achieve vastly superior compression rates).