By David Salomon. Published by Springer (2004). ISBN 0-387-40697-2. LCCN QA76.9 D33S25 2004. xx+899 pages.
A BibTeX style file and an Errata list are available.
Written December 2002 through April 2003. Produced September 2003 through January 2004. This book is an extension of the second edition. All errors found in the 2nd edition have been corrected, several sections with old material have been deleted, three sections have been extended or completely rewritten, and 15 sections with new material have been added. The book is hardbound with a colorful cover identical to that of the 2nd edition. Following are the preface to this edition and the table of contents.
I was pleasantly surprised when in December 2002 a message arrived from the editor asking me to produce the third edition of the book and proposing a deadline of late April 2003. I was hoping for a third edition mainly because the field of data compression has made great strides since the publication of the second edition, but also for the following reasons:
Reason 1: The many favorable readers' comments, of which the following are typical examples:
First I want to thank you for writing "Data Compression: The Complete Reference." It is a wonderful book and I use it as a primary reference. I wish to add something to the errata list of the 2nd edition, and, if I am allowed, I would like to make a few comments and suggestions....
Cosmin Truta, 2002
i am ismail from india. i am an computer science engineer. i did project in data compression on that i open the text file. get the keyword (symbols,alphabets,numbers once contained word). Then sorted the keyword by each characters occurrences in the text file. Then store the keyword in a file. then following the keyword store the 000 indicator.Then the original text file is read. take the first character of the file.get the positional value of the character in the keyword. then store the position in binary. if that binary contains single digit, the triple bit 000 is assigned. the binary con two digit, the triple bit 001 is assigned. so for 256 ascii need max of 8 digit binary.plus triple bit .so max needed for the 256th char in keyword is 11 bits. but min need for the first char in keyworkd is one bit+three bit , four bit. so writing continuously o's and 1's in a file. and then took the 8 by 8 bits and convert to equal ascii character and store in the file. thus storing keyword + indicator + converted ascii char can give the compressed file.
then reverse the process we can get the original file.
These ideas are fully mine.
(See description in Section 3.2).
Reason 2: The errors found by me and by readers in the second edition. They are listed in the second edition's Web site and they have been corrected in the third edition.
Reason 3: The title of the book (originally chosen by the publisher). This title had to be justified by making the book a complete reference. As a result, new compression methods and background material have been added to the book in this edition, while the descriptions of some of the older, obsolete methods have been deleted or "compressed." The most important additions and changes are the following:
The BMP image file format is native to the Microsoft Windows operating system.
The new Section 1.4.4 describes the simple version of RLE used to compress these files.
Section 2.4 on the Golomb code has been completely rewritten to correct mistakes in the original text. These codes are used in a new, adaptive image compression method discussed in Section 4.22.
Section 2.9.6 has been added to briefly mention an improved algorithm for adaptive Huffman compression.
The PPM lossless compression method of Section 2.18 produces impressive results, but is not used much in practice because it is slow. Much effort has been spent exploring ways to speed up PPM or make it more efficient. This edition presents three such efforts, the PPM* method of Section 2.18.6, PPMZ (Section 2.18.7), and the fast PPM method of Section 2.18.8. The first two try to explore the effect of unbounded-length contexts and add various other improvements to the basic PPM algorithm. The third attempts to speed up PPM by eliminating the use of escape symbols and introducing several approximations. In addition, Section 2.18.4 has been extended and now contains some information on two more variants of PPM, namely PPMP and PPMX.
The new Section 3.2 describes a simple, dictionary-based compression method. LZX, an LZ77 variant for the compression of cabinet files, is the topic of Section 3.7.
Section 3.8 is a short introduction to the interesting concept of file differencing, where a file is updated and the differences between the file before and after the update are encoded.
The popular Deflate method is now discussed in much detail in Section 3.23.
The popular PNG graphics file format is described in the new Section 3.24.
Section 3.25 is a short description of XMill, a special-purpose compressor for XML files.
Section 4.6 on the DCT has been completely rewritten. It now describes the DCT, shows two ways to interpret it, shows how the required computations can be simplified, lists four different discrete cosine transforms, and includes much background material. As a result, Section 4.8.2 was considerably cut.
An N-tree is an interesting data structure (an extension of quadtrees) whose compression is discussed in the new Section 4.30.4.
Section 5.19, on JPEG 2000, has been brought up to date.
MPEG-4 is an emerging international standard for audiovisual applications. It specifies procedures, formats, and tools for authoring multimedia content, delivering it, and consuming (playing and displaying) it. Thus, MPEG-4 is much more than a compression method. Section 6.6 is s short description of the main features of and tools included in MPEG-4.
The new lossless compression standard approved for DVD-A (audio) is called MLP. It is the topic of Section 7.6. This MLP should not be confused with the MLP image compression method of Section 4.21.
Shorten, a simple compression algorithm for waveform data in general and for speech in particular, is a new addition (Section 7.8).
SCSU is a new compression algorithm, designed specifically for compressing text files in Unicode. This is the topic of Section 8.12. The short Section 8.12.1 is devoted to BOCU-1, a simpler algorithm for Unicode compression. Several sections dealing with old algorithms have either been trimmed or completely removed due to space considerations. Most of this material is available in the book's Web site.
All the appendixes have been removed because of space considerations. They are freely available, in PDF format, at the book's Web site. The appendixes are (1) the ASCII code (including control characters); (2) space-filling curves; (3) data structures (including hashing); (4) error-correcting codes; (5) finite-state automata (this topic is needed for several compression methods, such as WFA, IFS, and dynamic Markov coding); (6) elements of probability; and (7) interpolating polynomials.
Many exercises from the 2nd edition have been deleted. The answers to the remaining exercises are available here in PDF.
I would like to thank Cosmin Truta for his interest, help, and encouragement. Because of him, this edition is better than it otherwise would have been. Thanks also go to Martin Cohn and Giovanni Motta for their excellent prereview of the book. Quite a few other readers have also helped by pointing out errors and omissions in the second edition.
The author's email address is firstname.lastname@example.org.
Those interested in data compression in general should consult the short section titled "Joining the Data Compression Community," at the end of the book, as well as the following resources
http://compression.ca/, http://www-isl.stanford.edu/~gray/iii.html, http://www.hn.is.uec.ac.jp/~arimura/compression_links.html, and http://datacompression.info/. (URLs are notoriously short lived, so search the Internet).
One consequence of the decision to take this course is that I am, as I set down these sentences, in the unusual position of writing my preface before the rest of my narrative. We are all familiar with the after-the-fact tone-weary, self-justificatory, aggrieved, apologetic, shared by ship captains appearing before boards of inquiry to explain how they came to run their vessels aground, and by authors composing forewords.
-John Lanchester, The Debt to Pleasure (1996)
The remainder of this web page is devoted to the table of contents and auxiliary material that can be freely downloaded in PDF format.
Preface to the Third Edition vii Preface to the Second Edition xi Preface to the First Edition xv Introduction 1 1 Basic Techniques 15 1.1 Intuitive Compression 15 1.2 Run-Length Encoding 20 1.3 RLE Text Compression 21 1.4 RLE Image Compression 25 1.5 Move-to-Front Coding 35 1.6 Scalar Quantization 39 2 Statistical Methods 43 2.1 Information Theory Concepts 44 2.2 Variable-Size Codes 50 2.3 Prefix Codes 51 2.4 The Golomb Code 57 2.5 The Kraft-MacMillan Inequality 65 2.6 The Counting Argument 66 2.7 Shannon-Fano Coding 66 2.8 Huffman Coding 68 2.9 Adaptive Huffman Coding 84 2.10 MNP5 90 2.11 MNP7 95 2.12 Reliability 96 2.13 Facsimile Compression 99 2.14 Arithmetic Coding 106 2.15 Adaptive Arithmetic Coding 120 2.16 The QM Coder 124 2.17 Text Compression 133 2.18 PPM 134 2.19 Context-Tree Weighting 156 3 Dictionary Methods 165 3.1 String Compression 167 3.2 Simple Dictionary Compression 168 3.3 LZ77 (Sliding Window) 169 3.4 LZSS 173 3.5 Repetition Times 176 3.6 QIC-122 178 3.7 LZX 180 3.8 File Differencing: VCDIFF 183 3.9 LZ78 185 3.10 LZFG 188 3.11 LZRW1 191 3.12 LZRW4 194 3.13 LZW 195 3.14 LZMW 206 3.15 LZAP 208 3.16 LZY 209 3.17 LZP 211 3.18 Repetition Finder 218 3.19 UNIX Compression 221 3.20 GIF Images 222 3.21 The V.42bis Protocol 223 3.22 Various LZ Applications 223 3.23 Deflate: Zip and Gzip 224 3.24 PNG 236 3.25 XML Compression: XMill 240 3.26 EXE Compressors 242 3.27 CRC 243 3.28 Summary 246 3.29 Data Compression Patents 246 3.30 A Unification 248 4 Image Compression 251 4.1 Introduction 253 4.2 Approaches to Image Compression 259 4.3 Intuitive Methods 273 4.4 Image Transforms 274 4.5 Orthogonal Transforms 279 4.6 The Discrete Cosine Transform 289 4.7 Test Images 325 4.8 JPEG 329 4.9 JPEG-LS 346 4.10 Progressive Image Compression 352 4.11 JBIG 360 4.12 JBIG2 369 4.13 Simple Images: EIDAC 380 4.14 Vector Quantization 382 4.15 Adaptive Vector Quantization 390 4.16 Block Matching 395 4.17 Block Truncation Coding 399 4.18 Context-Based Methods 405 4.19 FELICS 408 4.20 Progressive FELICS 411 4.21 MLP 415 4.22 Adaptive Golomb 423 4.23 PPPM 424 4.24 CALIC 426 4.25 Differential Lossless Compression 429 4.26 DPCM 431 4.27 Context-Tree Weighting 436 4.28 Block Decomposition 437 4.29 Binary Tree Predictive Coding 441 4.30 Quadtrees 448 4.31 Quadrisection 465 4.32 Space-Filling Curves 473 4.33 Hilbert Scan and VQ 474 4.34 Finite Automata Methods 477 4.35 Iterated Function Systems 494 4.36 Cell Encoding 511 5 Wavelet Methods 513 5.1 Fourier Transform 513 5.2 The Frequency Domain 514 5.3 The Uncertainty Principle 518 5.4 Fourier Image Compression 521 5.5 The CWT and Its Inverse 524 5.6 The Haar Transform 530 5.7 Filter Banks 549 5.8 The DWT 559 5.9 Multiresolution Decomposition 572 5.10 Various Image Decompositions 573 5.11 The Lifting Scheme 580 5.12 The IWT 591 5.13 The Laplacian Pyramid 593 5.14 SPIHT 597 5.15 CREW 609 5.16 EZW 609 5.17 DjVu 613 5.18 WSQ, Fingerprint Compression 616 5.19 JPEG 2000 622 6 Video Compression 637 6.1 Analog Video 637 6.2 Composite and Components Video 643 6.3 Digital Video 645 6.4 Video Compression 649 6.5 MPEG 661 6.6 MPEG-4 683 6.7 H.261 688 7 Audio Compression 691 7.1 Sound 692 7.2 Digital Audio 695 7.3 The Human Auditory System 698 7.4 µ-Law and A-Law Companding 704 7.5 ADPCM Audio Compression 710 7.6 MLP Audio 712 7.7 Speech Compression 717 7.8 Shorten 725 7.9 MPEG-1 Audio Layers 729 8 Other Methods 755 8.1 The Burrows-Wheeler Method 756 8.2 Symbol Ranking 761 8.3 ACB 765 8.4 Sort-Based Context Similarity 772 8.5 Sparse Strings 777 8.6 Word-Based Text Compression 789 8.7 Textual Image Compression 793 8.8 Dynamic Markov Coding 799 8.9 FHM Curve Compression 808 8.10 Sequitur 811 8.11 Triangle Mesh Compression: Edgebreaker 816 8.12 SCSU: Unicode Compression 827 Bibliography 835 Glossary 855 Joining the Data Compression Community 877 Index 879 Colophon 899
This section contains extra material added by the author from time to time. These documents are intended to to add new material, and to shed new light on material already included in the book.
1. The concept of correlation is basic to image and audio compression. This concept is easy to grasp intuitively, but this document (PDF, 8 pages, 323K) treats it quantitatively.
2. Image compression is achieved by decorrelating the pixels of an image. In statistics, one is normally concerned with calculating the correlation between random variables, but rarely with decorrelations. However, there is a little-known technique, the Mahalanobis transformation, that is used to decorrelate random variables. It is described here (PDF, 6 pages, 332K).
3. The simple method of section 3.2 has generated a lot of interest. I received an error correction and 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).
4. 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.
Final quote. Every reader finds himself. The writer's work is merely a kind of optical instrument that makes it possible for the reader to discern what, without this book, he would perhaps never have seen in himself.
Last Updated 3 November 2008.