Data Compression: The Complete Reference

3rd Edition

By David Salomon. Published by Springer (2004). ISBN 0-387-40697-2. LCCN QA76.9 D33S25 2004. xx+899 pages.

cover3rd.jpg

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.

Preface to the Third Edition

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

sir,

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 dsalomon@csun.edu.

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.

Table of Contents

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

Auxiliary Material

Because of cost considerations, more than 200 pages of auxiliary material did not go into the book. This material consists of nine appendixes and an index (just for the auxiliary material). This material is available here and can be downloaded in PDF format (1.7Mb). Accidentally, the answers to the exercises from the 2nd edition are also included here but should be ignored.

Extra Material

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.

Marcel Proust

Last Updated 3 November 2008.