Compression Systems

This chapter resumes the discussion of compression systems that was started in Chapters 1 and 2, but then deferred while we focussed on coding. Three state-of-the-art compression systems are described in detail, and the modeling and coding mechanisms they incorporate examined. Unfortunately, one chapter is not enough space to do justice to the wide range of compression models and applications that have been developed over the last twenty-five years, and our coverage is, of necessity, rather limited. For example, we have chosen as our main examples three mechanisms that are rather more appropriate for text than for, say, image or sound data. Nevertheless, the three mechanisms chosen — sliding window compression, the PPM method, and the Burrows-Wheeler transform — represent a broad cross section of current methods, and each provides interesting trade-offs between implementation complexity, execution-time resource cost, and compression effectiveness. And because they are general methods, they can still be used for non-text data, even if they do not perform as well as methods that are expressly designed for particular types of other data. Lossy modeling techniques for non-text data, such as gray-scale images, are touched upon briefly in Section 8.4; Pennebaker and Mitchell [1993], Salomon [2000], and Sayood [2000] give further details of such compression methods.