|
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 |
|