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