Lossless Compression Handbook (eBook)

Cover 1
Contents 8
List of Contributors 18
Preface 20
Part I: Theory 22
Chapter 1. Information Theory behind Source Coding 24
1.1 Introduction 24
1.2 Sequences and Information Sources 30
1.3 Variable-Length Codes for Memoryless Sources 32
1.4 Variable-Length Codes for Sources with Memory 39
1.5 Fixed-Length Codes for Memoryless Sources, the AEP 47
1.6 References 55
Chapter 2. Complexity Measures 56
2.1 Introduction 56
2.2 Concerns with Shannon Information Theory 58
2.3 Kolmogorov Complexity 59
2.4 Computational Issues of Kolmogorov Complexity 65
2.5 Relation to Shannon Information Theory 68
2.6 Historical Notes 72
2.7 Further Reading 72
2.8 References 72
Part II: Compression Techniques 74
Chapter 3. Universal Codes 76
3.1 Compact Integer Representations 76
3.2 Characteristics of Universal Codes 76
3.3 Polynomial Representations 77
3.4 Unary Codes 78
3.5 Levenstein and Elias Gamma Codes 79
3.6 Elias Omega and Even–Rodeh Codes 80
3.7 Rice Codes 81
3.8 Golomb Codes 83
3.9 Start–Step–Stop Codes 85
3.10 Fibonacci Codes 86
3.11 Ternary Comma Codes 91
3.12 Summation Codes 92
3.13 Wheeler 1/2 Code and Run-Lengths 94
3.14 Comparison of Representations 96
3.15 Final Remarks 98
3.16 References 99
Chapter 4. Huffman Coding 100
4.1 Introduction 100
4.2 Huffman Codes 101
4.3 Variations on a Theme 107
4.4 Adaptive Huffman Coding 110
4.5 Efficient Implementations 115
4.6 Conclusion and Further Reading 118
4.7 References 118
Chapter 5. Arithmetic Coding 122
5.1 Introduction 122
5.2 Basic Principles 124
5.3 Implementation 141
5.4 References 171
Chapter 6. Dictionary-Based Data Compression: An Algorithmic Perspective 174
6.1 Introduction 174
6.2 Dictionary Construction: Static versus Dynamic 175
6.3 Extensions of Dictionary Methods for Compressing Biomolecular Sequences 183
6.4 Data Structures in Dictionary Compression 184
6.5 Benchmark Programs and Standards 186
6.6 References 187
Chapter 7. Burrows–Wheeler Compression 190
7.1 Introduction 190
7.2 The Burrows–Wheeler Algorithm 191
7.3 The Burrows–Wheeler Transform 191
7.4 Basic Implementations 194
7.5 Relation to Other Compression Algorithms 201
7.6 Improvements to Burrows–Wheeler Compression 201
7.7 Preprocessing 202
7.8 The Permutation 202
7.9 Move-To-Front 204
7.10 Statistical Compressor 206
7.11 Eliminating Move-To-Front 208
7.12 Using the Burrows–Wheeler Transform in File Synchronization 210
7.13 Final Comments 211
7.14 Recent Developments 211
7.15 References 212
Chapter 8. Symbol-Ranking and ACB Compression 216
8.1 Introduction 216
8.2 Symbol-Ranking Compression 216
8.3 Buynovsky's ACB Compressor 222
8.4 References 225
Part III: Applications 226
Chapter 9. Lossless Image Compression 228
9.1 Introduction 228
9.2 Preliminaries 229
9.3 Prediction for Lossless Image Compression 235
9.4 Hierarchical Lossless Image Coding 241
9.5 Conclusions 243
9.6 References 244
Chapter 10. Text Compression 248
10.1 Introduction 248
10.2 Information Theory Background 249
10.3 Classification of Lossless Compression Algorithms 250
10.4 Transform-Based Methods: Star (*) Transform and Length-Index Preserving Transform 255
10.5 Three New Transforms„ILPT, NIT, and LIT 262
10.6 Conclusions 264
10.7 References 264
Chapter 11. Compression of Telemetry 268
11.1 What is Telemetry? 268
11.2 Issues Involved in Compression of Telemetry 271
11.3 Existing Telemetry Compression 273
11.4 Future of Telemetry Compression 274
11.5 References 274
Chapter 12. Lossless Compression of Audio Data 276
12.1 Introduction 276
12.2 Principles of Lossless Data Compression 278
12.3 Examples of Lossless Audio Data Compression Software Systems 286
12.4 Conclusion 288
12.5 References 288
Chapter 13. Algorithms for Delta Compression and Remote File Synchronization 290
13.1 Introduction 290
13.2 Delta Compression 292
13.3 Remote File Synchronization 300
13.4 Conclusions and Open Problems 308
13.5 References 308
Chapter 14. Compression of Unicode Files 312
14.1 Introduction 312
14.2 Unicode Character Codings 312
14.3 Compression of Unicode 314
14.4 Test Compressors 315
14.5 Comparisons 316
14.6 UTF-8 Compression 317
14.7 Conclusions 317
14.8 References 318
Part IV: Standards 320
Chapter 15. JPEG-LS Lossless and Near Lossless Image Compression 322
15.1 Lossless Image Compression and JPEG-LS 322
15.2 JPEG-LS 322
15 Summary 330
15.4 References 331
Chapter 16. The CCSDS Lossless Data Compression Recommendation for Space Applications 332
16.1 Introduction 332
16.2 The e_Rice Algorithm 333
16.3 The Adaptive Entropy Coder 334
16.4 Preprocessor 339
16.5 Coded Data Format 342
16.6 Decoding 342
16.7 Testing 345
16.8 Implementation Issues and Applications 345
16.9 Additional Information 347
16.10 References 347
Chapter 17. Lossless Bilevel Image Compression 348
17.1 Bilevel Image Compression 348
17.2 JBIG 348
17.3 JBIG2 360
17.4 Summary 369
17.5 References 370
Chapter 18. JPEG2000: Highly Scalable Image Compression 372
18.1 Introduction 372
18.2 JPEG2000 Features 373
18.3 The JPEG2000 Algorithm 375
18.4 Performance 387
18.5 References 390
Chapter 19. PNG Lossless Image Compression 392
19.1 Historical Background 392
19.2 Design Decisions 393
19.3 Compression Engine 395
19.4 zlib Format 397
19.5 zlib Library 397
19.6 Filters 399
19.7 Practical Compression Tips 404
19.8 Compression Tests and Comparisons 406
19.9 MNG 409
19.10 Further Reading 411
19.11 References 411
Chapter 20. Facsimile Compression 412
20.1 A Brief History 412
20.2 The Compression Algorithms 414
20.3 The Standards 419
20.4 Further Reading 423
20.5 References 423
Part V: Hardware 424
Chapter 21. Hardware Implementation of Data Compression 426
21.1 Introduction 426
21.2 Text Compression Hardware 428
21.3 Image Compression Hardware 436
21.4 Video Compression Hardware 438
21.5 References 463
Index 468
Color Plate Section 478