By David Salomon (with contributions by Giovanni Motta and David Bryant). Published by Springer (Dec 2006). ISBN 1-84628-602-5. LCCN QA76.9.D33 S25 2006. xxvii+1092 pages.
A BibTeX style file and an Errata list are available.
This edition of the book has the same chapters as the 3rd edition, with the following new topics added:
1. RAR. This proprietary algorithm employs a checksum for increased reliability. It has recently become popular, and its main features (provided by its originator, Eugene Roshal) are described.
2. FLAC (free, lossless audio compression). This is relatively new, free, not as good as mp3, but offers higher quality. Some documentation is available at "http://flac.sourceforge.net/documentation.html" and more was obtained from Josh Coalson, FLAC's developer.
3. Advanced Audio Coding, AAC. This is an extension of mp3 and is also referred to as mp4. Contrary to popular belief, AAC does not stand for Apple Audio Compression.
4. Tunstall code. This is a variation on variable-size, prefix codes.
5. Differential compression (written by Giovanni Motta). Given a file before and after editing, encode just the differences between the files. This boils down to the principle of editing. Editing data is done by inserting, deleting, or modifying items. Thus, encoding the differences between files amounts to creating a sequence of symbols C, I, and D (for copy, insert, delete). A given string can be changed to another string by a sequence of C, I, and D commands. This is referred to as Edit Distance.
6. WavPack, by David Bryant (who also wrote this section in the book). This is a complex, lossy/lossless audio compression algorithm and software that features several modes and a novel entropy encoder.
7. LZMA, see http://www.7-zip.org/7z.html. This is a sophisticated dictionary compression method developed by Igor Pavlov, who provided me with much information.
8. ALS. This is the audio lossless coding algorithm used in MPEG-4.
9. H.264 is an advanced video codec, part of the huge MPEG-4 project.
10. Dolby AC3. AC-3, also known as Dolby Digital, stands for Dolby's third-generation audio coder. AC-3 is a perceptual audio codec based on the same principles as the three MPEG-1/2 layers and AAC.
11. Hyperspectral compression (partially written by Giovanni Motta). Each data item is an array. Examples are (1) a hyperspectral image. Each pixel consists of hundreds of numbers, each the intensity of the pixel at a given frequency. (2) weather data from many stations. Each station has two coordinates (longitude, latitude) and the data is an array of temperatures, air pressure, or precipitation).
12. Monkey's audio. Monkey's audio is a fast, efficient, free, lossless audio compression algorithm and implementation that offers error detection, tagging, and external support.
13. Recursive range reduction (3R). This is a simple coding algorithm due to Yann Guidon that offers decent compression, is easy to program, and its performance is independent of the amount of data to be compressed (see the auxiliary material at the end of this page).
14. PDF. This is a common file format that uses both text and image compression. The compression algorithms used by PDF are not proprietary and most are already described in the book.
A pleasant change from the past is the great help I received from Giovanni Motta, David Bryant, and Cosmin Truta. Each proposed topics for this edition, went over some of the new material, and came up with constructive criticism. In addition, David and Giovanni wrote several sections of new material.
I would like to thank the following individuals for information about certain topics and for clearing up certain points. Igor Pavlov for help with 7z and LZMA, Stephan Wolf for his contribution, Matt Ashland for help with Monkey's audio, Yann Guidon for his help with recursive range reduction (3R), Josh Coalson for help with FLAC, and Eugene Roshal for help with RAR.
Preface to the Fourth Edition vii Preface to the Third Edition xi Preface to the Second Edition xv Preface to the First Edition xix Introduction 1 1 Basic Techniques 17 1.1 Intuitive Compression 17 1.2 Run-Length Encoding 22 1.3 RLE Text Compression 23 1.4 RLE Image Compression 27 1.5 Move-to-Front Coding 37 1.6 Scalar Quantization 40 1.7 Recursive Range Reduction 42 2 Statistical Methods 47 2.1 Information Theory Concepts 48 2.2 Variable-Size Codes 54 2.3 Prefix Codes 55 2.4 Tunstall Code 61 2.5 The Golomb Code 63 2.6 The Kraft-MacMillan Inequality 71 2.7 Shannon-Fano Coding 72 2.8 Huffman Coding 74 2.9 Adaptive Huffman Coding 89 2.10 MNP5 95 2.11 MNP7 100 2.12 Reliability 101 2.13 Facsimile Compression 104 2.14 Arithmetic Coding 112 2.15 Adaptive Arithmetic Coding 125 2.16 The QM Coder 129 2.17 Text Compression 139 2.18 PPM 139 2.19 Context-Tree Weighting 161 3 Dictionary Methods 171 3.1 String Compression 173 3.2 Simple Dictionary Compression 174 3.3 LZ77 (Sliding Window) 176 3.4 LZSS 179 3.5 Repetition Times 182 3.6 QIC-122 184 3.7 LZX 187 3.8 LZ78 189 3.9 LZFG 192 3.10 LZRW1 195 3.11 LZRW4 198 3.12 LZW 199 3.13 LZMW 209 3.14 LZAP 212 3.15 LZY 213 3.16 LZP 214 3.17 Repetition Finder 221 3.18 UNIX Compression 224 3.19 GIF Images 225 3.20 RAR and WinRAR 226 3.21 The V.42bis Protocol 228 3.22 Various LZ Applications 229 3.23 Deflate: Zip and Gzip 230 3.24 LZMA and 7-Zip 241 3.25 PNG 246 3.26 XML Compression: XMill 251 3.27 EXE Compressors 253 3.28 CRC 254 3.29 Summary 256 3.30 Data Compression Patents 256 3.31 A Unification 259 4 Image Compression 263 4.1 Introduction 265 4.2 Approaches to Image Compression 270 4.3 Intuitive Methods 283 4.4 Image Transforms 284 4.5 Orthogonal Transforms 289 4.6 The Discrete Cosine Transform 298 4.7 Test Images 333 4.8 JPEG 337 4.9 JPEG-LS 354 4.10 Progressive Image Compression 360 4.11 JBIG 369 4.12 JBIG2 378 4.13 Simple Images: EIDAC 389 4.14 Vector Quantization 390 4.15 Adaptive Vector Quantization 398 4.16 Block Matching 403 4.17 Block Truncation Coding 406 4.18 Context-Based Methods 412 4.19 FELICS 415 4.20 Progressive FELICS 417 4.21 MLP 422 4.22 Adaptive Golomb 436 4.23 PPPM 438 4.24 CALIC 439 4.25 Differential Lossless Compression 442 4.26 DPCM 444 4.27 Context-Tree Weighting 449 4.28 Block Decomposition 450 4.29 Binary Tree Predictive Coding 454 4.30 Quadtrees 461 4.31 Quadrisection 478 4.32 Space-Filling Curves 485 4.33 Hilbert Scan and VQ 487 4.34 Finite Automata Methods 497 4.35 Iterated Function Systems 513 4.36 Cell Encoding 529 5 Wavelet Methods 531 5.1 Fourier Transform 532 5.2 The Frequency Domain 534 5.3 The Uncertainty Principle 538 5.4 Fourier Image Compression 540 5.5 The CWT and Its Inverse 543 5.6 The Haar Transform 549 5.7 Filter Banks 566 5.8 The DWT 576 5.9 Multiresolution Decomposition 589 5.10 Various Image Decompositions 589 5.11 The Lifting Scheme 596 5.12 The IWT 608 5.13 The Laplacian Pyramid 610 5.14 SPIHT 614 5.15 CREW 626 5.16 EZW 626 5.17 DjVu 630 5.18 WSQ, Fingerprint Compression 633 5.19 JPEG 2000 639 6 Video Compression 653 6.1 Analog Video 653 6.2 Composite and Components Video 658 6.3 Digital Video 660 6.4 Video Compression 664 6.5 MPEG 676 6.6 MPEG-4 698 6.7 H.261 703 6.8 H.264 706 7 Audio Compression 719 7.1 Sound 720 7.2 Digital Audio 724 7.3 The Human Auditory System 727 7.4 WAVE Audio Format 734 7.5 Mu-Law and A-Law Companding 737 7.6 ADPCM Audio Compression 742 7.7 MLP Audio 744 7.8 Speech Compression 750 7.9 Shorten 757 7.10 FLAC 762 7.11 WavPack 772 7.12 Monkey's Audio 783 7.13 MPEG-4 Audio Lossless Coding (ALS) 784 7.14 MPEG-1/2 Audio Layers 795 7.15 Advanced Audio Coding (AAC) 821 7.16 Dolby AC-3 847 8 Other Methods 851 8.1 The Burrows-Wheeler Method 853 8.2 Symbol Ranking 858 8.3 ACB 862 8.4 Sort-Based Context Similarity 868 8.5 Sparse Strings 874 8.6 Word-Based Text Compression 885 8.7 Textual Image Compression 888 8.8 Dynamic Markov Coding 895 8.9 FHM Curve Compression 903 8.10 Sequitur 906 8.11 Triangle Mesh Compression: Edgebreaker 911 8.12 SCSU: Unicode Compression 922 8.13 Portable Document Format (PDF) 928 8.14 File Differencing 930 8.15 Hyperspectral Data Compression 941 Answers to Exercises 953 Bibliography 1019 Glossary 1041 Joining the Data Compression Community 1067 Index 1069
• Audio file a8.wav is mentioned on pages 726 and 728. It is available here (16Kb) for those who want to experiment.
• Section 1.7 describes the Recursive Range Reduction (3R) compression method, developed by Yann Guidon. A detailed, more recent description of this method, has been prepared by its developer and is available here.
• The simple method of section 3.2 has generated quite an interest. I received several comments about it, as well as ideas on how to extend and improve it. The best of these, due to Robert Jaskuła, can be found here (PDF, 2 pages, 52Kb).
• The dictionary-based compression methods described in Chapter 3 are based on different ideas and approaches, but have one thing in common; they generate the dictionary as they go along, reading data and compressing it. The dictionary is not included in the compressed file and is generated by the decoder in lockstep with the encoder. Thus, such methods can be termed "online." In contrast, the methods described here are also dictionary based, but can be considered "offline" because they include the dictionary in the compressed file. This document is based on several references, two of which are hard to obtain and are made available here:
1. Nakamura, Hirofumi and Sadayuki Murashima (1991) ``The Data Compression Based on Concatenation of Frequentative Code Neighbor,'' Proceedings of the 14th Symposium on Information Theory and its Applications (SITA '91), (Ibusuki, Japan), pp. 701--704, December 11--14 (in Japanese).
2. Nakamura, Hirofumi and Sadayuki Murashima (1996) ``Data Compression by Concatenations of Symbol Pairs,'' Proceedings of the IEEE International Symposium on Information Theory and its Applications, (Victoria, BC, Canada), pp. 496--499, September.
• Run-length encoding (RLE) is a simple approach to compression, but it is not very efficient and is consequently rarely use. Section 2.13 shows how RLE combined with variable-length codes is used in facsimile compression. The document found here (PDF, 7 pages, 9Mb) describes another application of RLE, to the compression of PK fonts. This method exploits the special features of font bitmaps and makes only a minimal use of variable-length codes.
• A few years ago I was pleasantly surprised to receive a message from David Herrera Pérez of Alba de Tormes (in the province of Salamanca, western Spain), informing me that he had decided to translate the book to Castilian Spanish. As of August 2013, this vast project is complete. The current version (PDF, 1220 pages, 14.1 MB) is available here. This file may be updated in the future, as errors and misprints are discovered. For questions and comments, please write directly to David Herrera Pérez.
IEEE Signal Processing Magazine, March 2008, page 147.
(Anonymous)
Last Updated 29 August 2013.