Handbook of Data Compression

5th Edition

By David Salomon and Giovanni Motta (with a contribution by David Bryant). Published by Springer (Nov 2009). ISBN 978-1-84882-902-2. LCCN unknown. 510 Figures. xxii+1359 pages.

A BibTeX style file and an Errata list are available.

This volume extends the 4th edition of "Data Compression: The Complete Reference". It features a different chapter structure, much new material, and many small improvements. The following new topics were added:

• The topic of compression benchmarks has been added to the Introduction.

• The paragraphs titled "How to Hide Data" in the Introduction show how data compression can be utilized to quickly and efficiently hide data in plain sight in our computers.

• Several paragraphs on compression curiosities have also been added to the Introduction.

• The new Section 1.1.2 shows why irreversible compression may be useful in certain situations.

• Chapters 2 through 4 discuss the all-important topic of variable-length codes. These chapters discuss basic, advanced, and robust variable-length codes. Many types of VL codes are known, they are used by many compression algorithms, have different properties, and are based on different principles. The most-important types of VL codes are prefix codes and codes that include their own length.

• Section 2.9 on phased-in codes was wrong and has been completely rewritten. An example of the start-step-stop code (2, 2,\infty) has been added to Section 3.2.

• Section 3.5 is a description of two interesting variable-length codes dubbed recursive bottom-up coding (RBUC) and binary adaptive sequential coding (BASC). These codes represent compromises between the standard binary (beta) code and the Elias gamma codes.

• Section 3.28 discusses the original method of interpolative coding whereby dynamic variable-length codes are assigned to a strictly monotonically increasing sequence of integers.

• Section 5.8 is devoted to the compression of PK (packed) fonts. These are older bitmaps fonts that were developed as part of the huge TeX project. The compression algorithm is not especially efficient, but it provides a rare example of run-length encoding (RLE) without the use of Huffman codes.

• Section 5.13 is about the Hutter prize for text compression.

• PAQ (Section 5.15) is an open-source, high-performance compression algorithm and free software that features sophisticated prediction combined with adaptive arithmetic encoding. This free algorithm is especially interesting because of the great interest it has generated and because of the many versions, subversions, and derivatives that have been spun off it.

• Section 6.3.2 discusses LZR, a variant of the basic LZ77 method, where the lengths of both the search and look-ahead buffers are unbounded.

• Section 6.4.1 is a description of LZB, an extension of LZSS. It is the result of evaluating and comparing several data structures and variable-length codes with an eye to improving the performance of LZSS.

• SLH, the topic of Section 6.4.2, is another variant of LZSS. It is a two-pass algorithm where the first pass employs a hash table to locate the best match and to count frequencies, and the second pass encodes the offsets and the raw symbols with Huffman codes prepared from the frequencies counted by the first pass.

• Most LZ algorithms were developed during the 1980s, but LZPP, the topic of Section 6.5, is an exception. LZPP is a modern, sophisticated algorithm that extends LZSS in several directions and has been inspired by research done and experience gained by many workers in the 1990s. LZPP identifies several sources of redundancy in the various quantities generated and manipulated by LZSS and exploits these sources to obtain better overall compression.

• Section 6.14.1 is devoted to LZT, an extension of UNIX compress/LZC. The major innovation of LZT is the way it handles a full dictionary.

• LZJ (Section 6.17) is an interesting LZ variant. It stores in its dictionary, which can be viewed either as a multiway tree or as a forest, every phrase found in the input. If a phrase is found n times in the input, only one copy is stored in the dictionary. Such behavior tends to fill the dictionary up very quickly, so LZJ limits the length of phrases to a preset parameter h.

• The interesting, original concept of antidictionary is the topic of Section 6.31. A dictionary-based encoder maintains a list of bits and pieces of the data and employs this list to compress the data. An antidictionary method, on the other hand, maintains a list of strings that do not appear in the data. This generates negative knowledge that allows the encoder to predict with certainty the values of many bits and thus to drop those bits from the output, thereby achieving compression.

• The important term "pixel" is discussed in Section 7.1, where the reader will discover that a pixel is not a small square, as is commonly assumed, but a mathematical point.

• Section 7.10.8 discusses the new HD photo (also known as JPEG XR) compression method for continuous-tone still images.

• ALPC (adaptive linear prediction and classification), is a lossless image compression algorithm described in Section 7.12. ALPC is based on a linear predictor whose coefficients are computed for each pixel individually in a way that can be mimiced by the decoder.

• Grayscale Two-Dimensional Lempel-Ziv Encoding (GS-2D-LZ, Section 7.18) is an innovative dictionary-based method for the lossless compression of grayscale images.

• Section 7.19 has been partially rewritten.

• Section 7.40 is devoted to spatial prediction, a combination of JPEG and fractal-based image compression.

• A short historical overview of video compression is provided in Section 9.4.

• The all-important H.264/AVC video compression standard has been extended to allow for a compressed stream that supports temporal, spatial, and quality scalable video coding, while retaining a base layer that is still backward compatible with the original H.264/AVC. This extension is the topic of Section 9.10.

• The complex and promising VC-1 video codec is the topic of the new, long Section 9.11.

• The new Section 11.6.4 treats the topic of syllable-based compression, an approach to compression where the basic data symbols are syllables, a syntactic form between characters and words.

• The commercial compression software known as stuffit has been around since 1987. The methods and algorithms it employs are proprietary, but some information exists in various patents. The new Section 11.16 is an attempt to describe what is publicly known about this software and how it works.

• There is a short appendix that presents and explains the basic concepts and terms of information theory.

Thanks to...

We would like to acknowledge the help, encouragement, and cooperation provided by Yuriy Reznik, Matt Mahoney, Mahmoud El-Sakka, Pawel Pylak, Darryl Lovato, Raymond Lau, Derong Bao, and Honggang Qi. They sent information, reviewed certain sections, made useful comments and suggestions, and corrected numerous errors.

A special mention goes to David Bryant who wrote Section 10.11.

Book Cover

Table of Contents

Preface to the New Handbook vii

Preface to the Fourth Edition xiii

Introduction 1

1 Basic Techniques 25

1.1 Intuitive Compression 25

1.2 Run-Length Encoding 31

1.3 RLE Text Compression 31

1.4 RLE Image Compression 36

1.5 Move-to-Front Coding 45

1.6 Scalar Quantization 49

1.7 Recursive Range Reduction 51

2 Basic VL Codes 55

2.1 Codes, Fixed- and Variable-Length 60

2.2 Pre�x Codes 62

2.3 VLCs, Entropy, and Redundancy 63

2.4 Universal Codes 68

2.5 The Kraft-McMillan Inequality 69

2.6 Tunstall Code 72

2.7 Schalkwijk's Coding 74

2.8 Tjalkens-Willems V-to-B Coding 79

2.9 Phased-In Codes 81

2.10 Redundancy Feedback (RF) Coding 85

2.11 Recursive Phased-In Codes 89

2.12 Self-Delimiting Codes 92

3 Advanced VL Codes 95

3.1 VLCs for Integers 95

3.2 Start-Step-Stop Codes 97

3.3 Start/Stop Codes 99

3.4 Elias Codes 101

3.5 RBUC, Recursive Bottom-Up Coding 107

3.6 Levenstein Code 110

3.7 Even-Rodeh Code 111

3.8 Punctured Elias Codes 112

3.9 Other Prefix Codes 113

3.10 Ternary Comma Code 116

3.11 Location Based Encoding (LBE) 117

3.12 Stout Codes 119

3.13 Boldi-Vigna (zeta) Codes 122

3.14 Yamamoto's Recursive Code 125

3.15 VLCs and Search Trees 128

3.16 Taboo Codes 131

3.17 Wang's Flag Code 135

3.18 Yamamoto Flag Code 137

3.19 Number Bases 141

3.20 Fibonacci Code 143

3.21 Generalized Fibonacci Codes 147

3.22 Goldbach Codes 151

3.23 Additive Codes 157

3.24 Golomb Code 160

3.25 Rice Codes 166

3.26 Subexponential Code 170

3.27 Codes Ending with "1" 171

3.28 Interpolative Coding 172

4 Robust VL Codes 177

4.1 Codes For Error Control 177

4.2 The Free Distance 183

4.3 Synchronous Prefix Codes 184

4.4 Resynchronizing Hu?man Codes 190

4.5 Bidirectional Codes 193

4.6 Symmetric Codes 202

4.7 VLEC Codes 204

5 Statistical Methods 211

5.1 Shannon-Fano Coding 211

5.2 Huffman Coding 214

5.3 Adaptive Huffman Coding 234

5.4 MNP5 240

5.5 MNP7 245

5.6 Reliability 247

5.7 Facsimile Compression 248

5.8 PK Font Compression 258

5.9 Arithmetic Coding 264

5.10 Adaptive Arithmetic Coding 276

5.11 The QM Coder 280

5.12 Text Compression 290

5.13 The Hutter Prize 290

5.14 PPM 292

5.15 PAQ 314

5.16 Context-Tree Weighting 320

6 Dictionary Methods 329

6.1 String Compression 331

6.2 Simple Dictionary Compression 333

6.3 LZ77 (Sliding Window) 334

6.4 LZSS 339

6.5 LZPP 344

6.6 Repetition Times 348

6.7 QIC-122 350

6.8 LZX 352

6.9 LZ78 354

6.10 LZFG 358

6.11 LZRW1 361

6.12 LZRW4 364

6.13 LZW 365

6.14 UNIX Compression (LZC) 375

6.15 LZMW 377

6.16 LZAP 378

6.17 LZJ 380

6.18 LZY 383

6.19 LZP 384

6.20 Repetition Finder 391

6.21 GIF Images 394

6.22 RAR and WinRAR 395

6.23 The V.42bis Protocol 398

6.24 Various LZ Applications 399

6.25 De�ate: Zip and Gzip 399

6.26 LZMA and 7-Zip 411

6.27 PNG 416

6.28 XML Compression: XMill 421

6.29 EXE Compressors 423

6.30 Off-Line Dictionary-Based Compression 424

6.31 DCA, Compression with Antidictionaries 430

6.32 CRC 434

6.33 Summary 437

6.34 Data Compression Patents 437

6.35 A Unification 439

7 Image Compression 443

7.1 Pixels 444

7.2 Image Types 446

7.3 Introduction 447

7.4 Approaches to Image Compression 453

7.5 Intuitive Methods 466

7.6 Image Transforms 467

7.7 Orthogonal Transforms 472

7.8 The Discrete Cosine Transform 480

7.9 Test Images 517

7.10 JPEG 520

7.11 JPEG-LS 541

7.12 Adaptive Linear Prediction and Classification 547

7.13 Progressive Image Compression 549

7.14 JBIG 557

7.15 JBIG2 567

7.16 Simple Images: EIDAC 577

7.17 Block Matching 579

7.18 Grayscale LZ Image Compression 582

7.19 Vector Quantization 588

7.20 Adaptive Vector Quantization 598

7.21 Block Truncation Coding 603

7.22 Context-Based Methods 609

7.23 FELICS 612

7.24 Progressive FELICS 615

7.25 MLP 619

7.26 Adaptive Golomb 633

7.27 PPPM 635

7.28 CALIC 636

7.29 Differential Lossless Compression 640

7.30 DPCM 641

7.31 Context-Tree Weighting 646

7.32 Block Decomposition 647

7.33 Binary Tree Predictive Coding 652

7.34 Quadtrees 658

7.35 Quadrisection 676

7.36 Space-Filling Curves 683

7.37 Hilbert Scan and VQ 684

7.38 Finite Automata Methods 695

7.39 Iterated Function Systems 711

7.40 Spatial Prediction 725

7.41 Cell Encoding 729

8 Wavelet Methods 731

8.1 Fourier Transform 732

8.2 The Frequency Domain 734

8.3 The Uncertainty Principle 737

8.4 Fourier Image Compression 740

8.5 The CWT and Its Inverse 743

8.6 The Haar Transform 749

8.7 Filter Banks 767

8.8 The DWT 777

8.9 Multiresolution Decomposition 790

8.10 Various Image Decompositions 791

8.11 The Lifting Scheme 798

8.12 The IWT 809

8.13 The Laplacian Pyramid 811

8.14 SPIHT 815

8.15 CREW 827

8.16 EZW 827

8.17 DjVu 831

8.18 WSQ, Fingerprint Compression 834

8.19 JPEG 2000 840

9 Video Compression 855

9.1 Analog Video 855

9.2 Composite and Components Video 861

9.3 Digital Video 863

9.4 History of Video Compression 867

9.5 Video Compression 869

9.6 MPEG 880

9.7 MPEG-4 902

9.8 H.261 907

9.9 H.264 910

9.10 H.264/AVC Scalable Video Coding 922

9.11 VC-1 927

10 Audio Compression 953

10.1 Sound 954

10.2 Digital Audio 958

10.3 The Human Auditory System 961

10.4 WAVE Audio Format 969

10.5 Mu-Law and A-Law Companding 971

10.6 ADPCM Audio Compression 977

10.7 MLP Audio 979

10.8 Speech Compression 984

10.9 Shorten 992

10.10 FLAC 996

10.11 WavPack 1007

10.12 Monkey's Audio 1017

10.13 MPEG-4 Audio Lossless Coding (ALS) 1018

10.14 MPEG-1/2 Audio Layers 1030

10.15 Advanced Audio Coding (AAC) 1055

10.16 Dolby AC-3 1082

11 Other Methods 1087

11.1 The Burrows-Wheeler Method 1089

11.2 Symbol Ranking 1094

11.3 ACB 1098

11.4 Sort-Based Context Similarity 1105

11.5 Sparse Strings 1110

11.6 Word-Based Text Compression 1121

11.7 Textual Image Compression 1128

11.8 Dynamic Markov Coding 1134

11.9 FHM Curve Compression 1142

11.10 Sequitur 1145

11.11 Triangle Mesh Compression: Edgebreaker 1150

11.12 SCSU: Unicode Compression 1161

11.13 Portable Document Format (PDF) 1167

11.14 File Differencing 1169

11.15 Hyperspectral Data Compression 1180

11.16 Stuffit 1191

A Information Theory 1199

A.1 Information Theory Concepts 1199

Answers to Exercises 1207

Bibliography 1271

Glossary 1303

Joining the Data Compression Community 1329

Index 1331

 

Auxiliary and Extra Material

• (Nov 13, 2009). Audio file a8.wav is mentioned on pages 960 and 962. It is available here (16 KB) for those who want to experiment.

• (Dec 29, 2009). Section 1.1.13 discusses irreversible compression. The short document found here (PDF, 1 page, 32 KB) describes another example of this weird topic.

Quotation

"You can't just start a new project in Visual Studio /Delphi/whatever, then add in an ADPCM encoder, the best psychoacoustic model, some DSP stuff, Levinson Durbin, subband decomposition, MDCT, a Blum-Blum-Shub random number generator, a wavelet-based brownian movement simulator and a Feistel network cipher using a cryptographic hash of the Matrix series, and expect it to blow everything out of the water, now can you?"

(Anonymous)

Last Updated 29 December, 2009