Compression Algorithms for Real Programmers (eBook)

Peter Wayner (Autor)

eBook Download: PDF

1999 | 1. Auflage
240 Seiten
Elsevier Science (Verlag)
978-0-08-050243-4 (ISBN)

Infos

In life, time is money, and on the Internet, the size of data is money. Small programs and small files take less disk space and cost less to send over the Internet. Compression Algorithms for Real Programmers describes the basic algorithms and approaches for compressing information so you can create the smallest files possible. These new algorithms are making it possible for people to take impossibly large audio and video files and compress them enough that they can flow over the Internet.
* Examines the classic algorithms like Huffman coding, arithmetic compression, and dictionary-based schemes in depth
* Describes the basic approaches used to squeeze audio and video signals by factors of as much as 100:1
* Discusses the philosophy of compression to illustrate the underlying trade-offs in the algorithms
* Explores the use of wavelets and other modeling techniques that use repetitive functions to squeeze audio and video
* Shows how programming solutions like Adobe PostScript can save space and make networks more efficient
* Describes new approaches using fractals and grammars just being explored by the compression community
* Shows how to extend the algorithms and use them for copyright protection

Peter Wayner is a writer living in Baltimore and is the author of Digital Cash and Agents at Large (both Academic Press). His writings appear in numerous academic journals as well as the pages of more popular forums such as MacWorld and the New York Times. He has taught various computer science courses at Cornell University and Georgetown University.

Inhalt

Cover 1
Contents 6
Preface 10
Book Notes 12
Chapter 1. Introduction 13
1.1 Grading Compression Algorithms 18
1.2 Philosophical Hurdles 21
1.3 How to Use This Book 25
Chapter 2. Statistical Basics 27
2.1 Huffman Encoding 28
2.2 Shannon-Fano Encoding 33
2.3 Entropy and Information Theory 34
2.4 Character Grouping Schemes 40
2.5 Conclusion 44
Chapter 3. Dictionary Techniques 47
3.1 Basic Lempel-Ziv-Welch 48
3.2 Simple Windows with Lzss 52
3.3 Coding Notes 55
3.4 Variations 58
3.5 Commercially Available Standards 58
3.6 Conclusions 60
Chapter 4. Arithmetic Compression 61
4.1 Three examples 63
4.2 Programming Arithmetic Coding 69
4.3 Products Using Arithmetic Coding 71
4.4 Conclusion 72
Chapter 5. Adaptive Compression 73
5.1 Escape Codes 74
5.2 Adaptive Huffman Coding 75
5.3 Windows of Data 77
5.4 Conclusion 78
Chapter 6. Grammar Compression 79
6.1 SEQUITUR 81
6.2 Code Compression 83
6.3 Conclusion 87
Chapter 7. Programmatic Solutions 89
7.1 PostScript 90
7.2 Conclusions 94
Chapter 8. Quantization 97
8.1 Basic Quantization 98
8.2 Adaptive Quantization 101
8.3 Vector Quantization 106
8.4 Dimension Reduction 110
8.5 Conclusion 112
Chapter 9. Wavelet Transforms 113
9.1 Basic Fourier Mathematics 115
9.2 Discrete Cosine Transform 118
9.3 Two-Dimensional Approaches 120
9.4 Other Wavelet Functions 123
9.5 Conclusion 135
Chapter 10. JPEG 137
10.1 JPEG Overview 138
10.2 Basic JPEG 139
10.3 JPEG Enhancements 145
10.4 Lossless JPEG 146
10.5 Progressive Transmission 148
10.6 Hierarchical Transmission 149
10.7 Conclusions 151
Chapter 11. Video Compression 153
11.1 Pixel Details 154
11.2 Motion Estimation 156
11.3 Quantization and Bit Packing 162
11.4 MPEG-2 165
11.5 Conclusions 165
Chapter 12. Audio Compression 169
12.1 Digitization 171
12.2 Subband Coding 172
12.3 Speech Compression 173
12.4 MPEG and MP3 173
12.5 Conclusion 176
Chapter 13. Fractal Compression 177
13.1 Conclusion 179
Chapter 14. Steganography 183
14.1 Statistical Coding 184
14.2 JPEG and JSteg 185
14.3 Quantization 186
14.4 Grammars 187
14.5 Conclusions 189
Appendix A. Patents 191
A.1 Statistical Patents 192
A.2 Dictionary Algorithm Patents 195
A.3 Arithmetic Algorithm Patents 206
A.4 Adaptive Algorithm Patents 221
A.5 Grammar Algorithm Patents 225
A.6 Quantization Algorithm Patents 226
A.7 Image Algorithm Patents 227
A.8 Fractal Algorithm Patents 229
A.9 Other Patents 231
Appendix B. Bibliography 233
Index 247

Produkt-Details

• Erscheint lt. Verlag: 11.10.1999
• Sprache: englisch
• Themenwelt: Sachbuch/Ratgeber
• Themenwelt: Mathematik / Informatik ► Informatik ► Datenbanken
• Themenwelt: Mathematik / Informatik ► Informatik ► Grafik / Design
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• Themenwelt: Mathematik / Informatik ► Informatik ► Software Entwicklung
• Themenwelt: Informatik ► Theorie / Studium ► Algorithmen
• Themenwelt: Mathematik / Informatik ► Mathematik
• ISBN-10: 0-08-050243-1 / 0080502431
• ISBN-13: 978-0-08-050243-4 / 9780080502434