Handbook of Data Compression (eBook)

Preface to the New Handbook 6
Preface to the Fourth Edition 11
Contents 15
Introduction 21
1 Basic Techniques 44
1.1 Intuitive Compression 44
1.2 Run-Length Encoding 50
1.3 RLE Text Compression 50
1.4 RLE Image Compression 55
1.5 Move-to-Front Coding 64
1.6 Scalar Quantization 68
1.7 Recursive Range Reduction 70
2 Basic VL Codes 74
2.1 Codes, Fixed- and Variable-Length 79
2.2 Prefix Codes 81
2.3 VLCs, Entropy, and Redundancy 82
2.4 Universal Codes 87
2.5 The Kraft–McMillan Inequality 88
2.6 Tunstall Code 91
2.7 Schalkwijk’s Coding 93
2.8 Tjalkens–Willems V-to-B Coding 98
2.9 Phased-In Codes 100
2.10 Redundancy Feedback (RF) Coding 104
2.11 Recursive Phased-In Codes 108
2.12 Self-Delimiting Codes 111
3 Advanced VL Codes 114
3.1 VLCs for Integers 114
3.2 Start-Step-Stop Codes 116
3.3 Start/Stop Codes 118
3.4 Elias Codes 120
3.5 RBUC, Recursive Bottom-Up Coding 126
3.6 Levenstein Code 129
3.7 Even–Rodeh Code 130
3.8 Punctured Elias Codes 131
3.9 Other Prefix Codes 132
3.10 Ternary Comma Code 135
3.11 Location Based Encoding (LBE) 136
3.12 Stout Codes 138
3.13 Boldi–Vigna (.) Codes 141
3.14 Yamamoto’s Recursive Code 144
3.15 VLCs and Search Trees 147
3.16 Taboo Codes 150
3.17Wang’s Flag Code 154
3.18 Yamamoto Flag Code 156
3.19 Number Bases 160
3.20 Fibonacci Code 162
3.21 Generalized Fibonacci Codes 166
3.22 Goldbach Codes 170
3.23 Additive Codes 176
3.24 Golomb Code 179
3.25 Rice Codes 185
3.26 Subexponential Code 189
3.27 Codes Ending with "1" 190
3.28 Interpolative Coding 191
4 Robust VL Codes 196
4.1 Codes For Error Control 196
4.2 The Free Distance 202
4.3 Synchronous Prefix Codes 203
4.4 Resynchronizing Huffman Codes 209
4.5 Bidirectional Codes 212
4.6 Symmetric Codes 221
4.7 VLEC Codes 223
5 Statistical Methods 229
5.1 Shannon-Fano Coding 229
5.2 Huffman Coding 232
5.3 Adaptive Huffman Coding 252
5.4 MNP5 258
5.5 MNP7 263
5.6 Reliability 265
5.7 Facsimile Compression 266
5.8 PK Font Compression 276
5.9 Arithmetic Coding 282
5.10 Adaptive Arithmetic Coding 294
5.11 The QM Coder 298
5.12 Text Compression 308
5.13 The Hutter Prize 308
5.14 PPM 310
5.15 PAQ 332
5.16 Context-Tree Weighting 338
6 Dictionary Methods 346
6.1 String Compression 348
6.2 Simple Dictionary Compression 350
6.3 LZ77 (Sliding Window) 351
6.4 LZSS 356
6.5 LZPP 361
6.6 Repetition Times 365
6.7 QIC-122 367
6.8 LZX 369
6.9 LZ78 371
6.10 LZFG 375
6.11 LZRW1 378
6.12 LZRW4 381
6.13 LZW 382
6.14 UNIX Compression (LZC) 392
6.15 LZMW 394
6.16 LZAP 395
6.17 LZJ 397
6.18 LZY 400
6.19 LZP 401
6.20 Repetition Finder 408
6.21 GIF Images 411
6.22 RAR and WinRAR 412
6.23 The V.42bis Protocol 415
6.24 Various LZ Applications 416
6.25 Deflate: Zip and Gzip 416
6.26 LZMA and 7-Zip 428
6.27 PNG 433
6.28 XML Compression: XMill 438
6.29 EXE Compressors 440
6.30 Off-Line Dictionary-Based Compression 441
6.31 DCA, Compression with Antidictionaries 447
6.32 CRC 451
6.33 Summary 454
6.34 Data Compression Patents 454
6.35 A Unification 456
7 Image Compression 459
7.1 Pixels 460
7.2 Image Types 462
7.3 Introduction 463
7.4 Approaches to Image Compression 469
7.5 Intuitive Methods 482
7.6 Image Transforms 483
7.7 Orthogonal Transforms 488
7.8 The Discrete Cosine Transform 496
7.9 Test Images 533
7.10 JPEG 536
7.11 JPEG-LS 557
7.12 Adaptive Linear Prediction and Classification 563
7.13 Progressive Image Compression 565
7.14 JBIG 573
7.15 JBIG2 583
7.16 Simple Images: EIDAC 593
7.17 Block Matching 595
7.18 Grayscale LZ Image Compression 598
7.19 Vector Quantization 604
7.20 Adaptive Vector Quantization 614
7.21 Block Truncation Coding 619
7.22 Context-Based Methods 625
7.23 FELICS 628
7.24 Progressive FELICS 631
7.25 MLP 635
7.26 Adaptive Golomb 649
7.27 PPPM 651
7.28 CALIC 652
7.29 Differential Lossless Compression 656
7.30 DPCM 657
7.31 Context-Tree Weighting 662
7.32 Block Decomposition 663
7.33 Binary Tree Predictive Coding 668
7.34 Quadtrees 674
7.35 Quadrisection 692
7.36 Space-Filling Curves 699
7.37 Hilbert Scan and VQ 700
7.38 Finite Automata Methods 711
7.39 Iterated Function Systems 727
7.40 Spatial Prediction 741
7.41 Cell Encoding 745
8 Wavelet Methods 747
8.1 Fourier Transform 748
8.2 The Frequency Domain 750
8.3 The Uncertainty Principle 753
8.4 Fourier Image Compression 756
8.5 The CWT and Its Inverse 759
8.6 The Haar Transform 765
8.7 Filter Banks 783
8.8 The DWT 793
8.9 Multiresolution Decomposition 806
8.10 Various Image Decompositions 807
8.11 The Lifting Scheme 814
8.12 The IWT 825
8.13 The Laplacian Pyramid 827
8.14 SPIHT 831
8.15 CREW 843
8.16 EZW 843
8.17 DjVu 847
8.18 WSQ, Fingerprint Compression 850
8.19 JPEG 2000 856
9 Video Compression 870
9.1 Analog Video 870
9.2 Composite and Components Video 876
9.3 Digital Video 878
9.4 History of Video Compression 882
9.5 Video Compression 884
9.6 MPEG 895
9.7 MPEG-4 917
9.8 H.261 922
9.9 H.264 925
9.10 H.264/AVC Scalable Video Coding 937
9.11 VC-1 942
10 Audio Compression 968
10.1 Sound 969
10.2 Digital Audio 973
10.3 The Human Auditory System 976
10.4WAVE Audio Format 984
10.5 µ-Law and A-Law Companding 986
10.6 ADPCM Audio Compression 992
10.7 MLP Audio 994
10.8 Speech Compression 999
10.9 Shorten 1007
10.10 FLAC 1011
10.11WavPack 1022
10.12 Monkey’s Audio 1032
10.13 MPEG-4 Audio Lossless Coding (ALS) 1033
10.14 MPEG-1/2 Audio Layers 1045
10.15 Advanced Audio Coding (AAC) 1070
10.16 Dolby AC-3 1097
11 Other Methods 1101
11.1 The Burrows-Wheeler Method 1103
11.2 Symbol Ranking 1108
11.3 ACB 1112
11.4 Sort-Based Context Similarity 1119
11.5 Sparse Strings 1124
11.6Word-Based Text Compression 1135
11.7 Textual Image Compression 1142
11.8 Dynamic Markov Coding 1148
11.9 FHM Curve Compression 1156
11.10 Sequitur 1159
11.11 Triangle Mesh Compression: Edgebreaker 1164
11.12 SCSU: Unicode Compression 1175
11.13 Portable Document Format (PDF) 1181
11.14 File Differencing 1183
11.15 Hyperspectral Data Compression 1194
11.16 Stuffit 1205
Appendix A Information Theory 1213
A.1 Information Theory Concepts 1213
Answers to Exercises 1220
Bibliography 1283
Glossary 1314
Joining the Data Compression Community 1340
Index 1341
Colophon 1370