Lossless Compression for Text and Images

Alistair Moffat
Department of Computer Science, The University of Melbourne, Parkville 3052, Australia.

Timothy C. Bell
Department of Computer Science, University of Canterbury, New Zealand.

Ian H. Witten
Department of Computer Science, University of Waikato, New Zealand.

Status

International Journal of High Speed Electronics and Systems, 8(1):179-231, March 1997.

Abstract

Most data that is inherently discrete needs to be compressed in such a way that it can be recovered exactly, without any loss. Examples include text of all kinds, experimental results, and statistical databases. Other forms of data may need to be stored exactly, such as images---particularly bilevel ones, or ones arising in medical and remote-sensing applications, or ones that may be required to be certified true for legal reasons. Moreover, during the process of lossy compression, many occasions for lossless compression of coefficients or other information arise.

This paper surveys techniques for lossless compression. The process of compression can be broken down into modeling and coding. We provide an extensive discussion of coding techniques, and then introduce methods of modeling that are appropriate for text and images. Standard methods used in popular utilities (in the case of text) and international standards (in the case of images) are described.