Contents
Preface vii
Part I: Basic Concepts 1
Introduction 5
1 Approaches to Compression 21
1.1 Variable-Length Codes 25
1.2 Run-Length Encoding 41
Intermezzo: Space-Filling Curves 46
1.3 Dictionary-Based Methods 47
1.4 Transforms 50
1.5 Quantization 51
Chapter Summary 58
2 Huffman Coding 61
2.1 Huffman Encoding 63
2.2 Huffman Decoding 67
2.3 Adaptive Huffman Coding 76
Intermezzo: History of Fax 83
2.4 Facsimile Compression 85
Chapter Summary 90
3 Dictionary Methods 93
3.1 LZ78 95
Intermezzo: The LZW Trio 98
3.2 LZW 98
3.3 Deflate: Zip and Gzip 108
Chapter Summary 119
Part II: Advanced Techniques 121
4 Arithmetic Coding 123
4.1 The Basic Idea 124
4.2 Implementation Details 130
4.3 Underflow 133
4.4 Final Remarks 134
Intermezzo: The Real Numbers 135
4.5 Adaptive Arithmetic Coding 137
4.6 Range Encoding 140
Chapter Summary 141
5 Image Compression 143
5.1 Introduction 144
5.2 Approaches to Image Compression 146
Intermezzo: History of Gray Codes 151
5.3 Image Transforms 152
5.4 Orthogonal Transforms 156
5.5 The Discrete Cosine Transform 160
Intermezzo: Statistical Distributions 178
5.6 JPEG 179
Intermezzo: Human Vision and Color 184
5.7 The Wavelet Transform 198
5.8 Filter Banks 216
5.9 WSQ, Fingerprint Compression 218
Chapter Summary 225
6 Audio Compression 227
6.1 Companding 230
6.2 The Human Auditory System 231
Intermezzo: Heinrich Georg Barkhausen 234
6.3 Linear Prediction 235
6.4 µ -Law and A-Law Companding 238
6.5 Shorten 244
Chapter Summary 245
7 Other Methods 247
7.1 The Burrows–Wheeler Method 248
Intermezzo: Fibonacci Codes 253
7.2 Symbol Ranking 254
7.3 SCSU: Unicode Compression 258
Chapter Summary 263
Bibliography 265
Glossary 271
Solutions to Puzzles 281
Answers to Exercises 283
Index 305
Another Algorithm Books
Download
No comments:
Post a Comment