Compression Algorithms for Real Programmers
- 1st Edition - September 30, 1999
- Author: Peter Wayner
- Language: English
- Paperback ISBN:9 7 8 - 0 - 1 2 - 7 8 8 7 7 4 - 6
- eBook ISBN:9 7 8 - 0 - 0 8 - 0 5 0 2 4 3 - 4
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.… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteIn 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
* 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
programmers, software engineers
Preface.
Book Notes.
1. Introduction
1.1 Grading Compression Algorithms
1.2 Philosophical Hurdles
1.3 How to Use this Book
2. Statistical Basics
2.1 Huffman Encoding
2.2 Shannon-Fano Encoding
2.3 Entropy and Information Theory
2.4 Character Grouping Schemes
2.5 Conclusion
3. Dictionary Techniques
3.1 Basic Lempel-Ziv-Welch
3.2 Simple Windows with LZSS
3.3 Coding Notes
3.4 Variations
3.5 Commercially Available Standards
3.6 Conclusions
4. Arithmetic Compression
4.1 Three Examples
4.2 Programming Arithmetic Coding
4.3 Products Using Arithmetic Coding
4.4 Conclusion
5. Adaptive Compression
5.1 Escape Codes
5.2 Adaptive Huffman Coding
5.3 Windows of Data
5.4 Conclusion
6. Grammar Compression
6.1 SEQUITUR
6.2 Code Compression
6.3 Conclusion
7. Programmatic Solutions
7.1 PostScript
7.2 Conclusion
8. Quantization
8.1 Basic Quantization
8.2 Adaptive Quantization
8.3 Vector Quantization
8.4 Dimension Reduction
8.5 Conclusion
9. Wavelet Transforms
9.1 Basic Fourier Mathematics
9.2 Discrete Cosine Transform
9.3 Two-Dimensional Approaches
9.4 Other Wavelet Functions
9.5 Conclusion
10. JPEG
10.1 JPEG Overview
10.2 Basic JPEG
10.3 JPEG Enhancements
10.4 Lossless JPEG
10.5 Progressive Transmission
10.6 Hierarchical Transmission
10.7 Conclusions
11. Video Compression
11.1 Pixel Details
11.2 Motion Estimation
11.3 Quantization and Bit Packaging
11.4 MPEG-2
11.5 Conclusions
12. Audio Compression
12.1 Digitization
12.2 Subband Coding
12.3 Speech Compression
12.4 MPEG and MP3
12.5 Conclusion
13. Fractal Compression
13.1 Conclusion
14. Steganography
14.1 Statistical Coding
14.2 JPEG and Jsteg
14.3 Quantization
14.4 Grammars
14.5 Conclusions
Appendix A: Patents
A.1 Statistical Patents
A.2 Dictionary Algorithm Patents
A.3 Arithmetic Algorithm Patents
A.4 Adaptive Algorithm Patents
A.5 Grammar Algorithm Patents
A.6 Quantization Algorithm Patents
A.7 Image Algorithm Patents
A.8 Fractal Algorithm Patents
A.9 Other Patents
Appendix B: Bibliography
Index
Book Notes.
1. Introduction
1.1 Grading Compression Algorithms
1.2 Philosophical Hurdles
1.3 How to Use this Book
2. Statistical Basics
2.1 Huffman Encoding
2.2 Shannon-Fano Encoding
2.3 Entropy and Information Theory
2.4 Character Grouping Schemes
2.5 Conclusion
3. Dictionary Techniques
3.1 Basic Lempel-Ziv-Welch
3.2 Simple Windows with LZSS
3.3 Coding Notes
3.4 Variations
3.5 Commercially Available Standards
3.6 Conclusions
4. Arithmetic Compression
4.1 Three Examples
4.2 Programming Arithmetic Coding
4.3 Products Using Arithmetic Coding
4.4 Conclusion
5. Adaptive Compression
5.1 Escape Codes
5.2 Adaptive Huffman Coding
5.3 Windows of Data
5.4 Conclusion
6. Grammar Compression
6.1 SEQUITUR
6.2 Code Compression
6.3 Conclusion
7. Programmatic Solutions
7.1 PostScript
7.2 Conclusion
8. Quantization
8.1 Basic Quantization
8.2 Adaptive Quantization
8.3 Vector Quantization
8.4 Dimension Reduction
8.5 Conclusion
9. Wavelet Transforms
9.1 Basic Fourier Mathematics
9.2 Discrete Cosine Transform
9.3 Two-Dimensional Approaches
9.4 Other Wavelet Functions
9.5 Conclusion
10. JPEG
10.1 JPEG Overview
10.2 Basic JPEG
10.3 JPEG Enhancements
10.4 Lossless JPEG
10.5 Progressive Transmission
10.6 Hierarchical Transmission
10.7 Conclusions
11. Video Compression
11.1 Pixel Details
11.2 Motion Estimation
11.3 Quantization and Bit Packaging
11.4 MPEG-2
11.5 Conclusions
12. Audio Compression
12.1 Digitization
12.2 Subband Coding
12.3 Speech Compression
12.4 MPEG and MP3
12.5 Conclusion
13. Fractal Compression
13.1 Conclusion
14. Steganography
14.1 Statistical Coding
14.2 JPEG and Jsteg
14.3 Quantization
14.4 Grammars
14.5 Conclusions
Appendix A: Patents
A.1 Statistical Patents
A.2 Dictionary Algorithm Patents
A.3 Arithmetic Algorithm Patents
A.4 Adaptive Algorithm Patents
A.5 Grammar Algorithm Patents
A.6 Quantization Algorithm Patents
A.7 Image Algorithm Patents
A.8 Fractal Algorithm Patents
A.9 Other Patents
Appendix B: Bibliography
Index
- No. of pages: 240
- Language: English
- Edition: 1
- Published: September 30, 1999
- Imprint: Morgan Kaufmann
- Paperback ISBN: 9780127887746
- eBook ISBN: 9780080502434
PW
Peter Wayner
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.
Affiliations and expertise
Writer, Baltimore, MD, USA