To access the contents, click the chapter and section titles.

The Data Compression Book-
(Imprint: M & T Books)
(Publisher: IDG Books Worldwide, Inc.)
Author: Mark Nelson
ISBN: 1558514341

Afterword
Why This Book Is For You

Chapter 1—Introduction to Data Compression
The Audience
Why C?
Which C?
Issues in Writing Portable C
Keeping Score
The Structure

Chapter 2—The Data-Compression Lexicon, with a History
The Two Kingdoms
Data Compression = Modeling + Coding
The Dawn Age
Coding
An Improvement
Modeling
Statistical Modeling
Dictionary Schemes
Ziv and Lempel
LZ77
LZ78
Lossy Compression
Programs to Know

Chapter 3—The Dawn Age: Minimum Redundancy Coding
The Shannon-Fano Algorithm
The Huffman Algorithm
Huffman in C
BITIO.C
A Reminder about Prototypes
MAIN-C.C AND MAIN-E.C
MAIN-C.C
ERRHAND.C
Into the Huffman Code
Counting the Symbols
Saving the Counts
Building the Tree
Using the Tree
The Compression Code
Putting It All Together
Performance

Chapter 4—A Significant Improvement: Adaptive Huffman Coding
Adaptive Coding
Updating the Huffman Tree
What Swapping Does
The Algorithm
An Enhancement
The Escape Code
The Overflow Problem
A Rescaling Bonus
The Code
Initialization of the Array
The Compress Main Program
The Expand Main Program
Encoding the Symbol
Updating the Tree
Decoding the Symbol
The Code

Chapter 5—Huffman One Better: Arithmetic Coding
Difficulties
Arithmetic Coding: A Step Forward
Practical Matters
A Complication
Decoding
Where’s the Beef?
The Code
The Compression Program
The Expansion Program
Initializing the Model
Reading the Model
Initializing the Encoder
The Encoding Process
Flushing the Encoder
The Decoding Process
Summary
Code

Chapter 6—Statistical Modeling
Higher-Order Modeling
Finite Context Modeling
Adaptive Modeling
A Simple Example
Using the Escape Code as a Fallback
Improvements
Highest-Order Modeling
Updating the Model
Escape Probabilities
Scoreboarding
Data Structures
The Finishing Touches: Tables –1 and –2
Model Flushing
Implementation
Conclusions
Enhancement
ARITH-N Listing

Chapter 7—Dictionary-Based Compression
An Example
Static vs. Adaptive
Adaptive Methods
A Representative Example
Israeli Roots
History
ARC: The Father of MS-DOS Dictionary Compression
Dictionary Compression: Where It Shows Up
Danger Ahead—Patents
Conclusion

Chapter 8—Sliding Window Compression
The Algorithm
Problems with LZ77
An Encoding Problem
LZSS Compression
Data Structures
A Balancing Act
Greedy vs. Best Possible
The Code
Constants and Macros
Global Variables
The Compression Code
Initialization
The Main Loop
The Exit Code
AddString()
DeleteString()
Binary Tree Support Routines
The Expansion Routine
Improvements
The Code

Chapter 9—LZ78 Compression
Can LZ77 Improve?
Enter LZ78
LZ78 Details
LZ78 Implementation
An Effective Variant
Decompression
The Catch
LZW Implementation
Tree Maintenance and Navigation
Compression
Decompression
The Code
Improvements
Patents

Chapter 10—Speech Compression
Digital Audio Concepts
Fundamentals
Sampling Variables
PC-Based Sound
Lossless Compression of Sound
Problems and Results
Lossy Compression
Silence Compression
Companding
Other Techniques

Chapter 11—Lossy Graphics Compression
Enter Compression
Statistical and Dictionary Compression Methods
Lossy Compression
Differential Modulation
Adaptive Coding
A Standard That Works: JPEG
JPEG Compression
The Discrete Cosine Transform
DCT Specifics
Why Bother?
Implementing the DCT
Matrix Multiplication
Continued Improvements
Output of the DCT
Quantization
Selecting a Quantization Matrix
Coding
The Zig-Zag Sequence
Entropy Encoding
What About Color?
The Sample Program
Input Format
The Code
Initialization
The Forward DCT Routine
WriteDCTData()
OutputCode()
File Expansion
ReadDCTData()
Input DCT Codes
The Inverse DCT
The Complete Code Listing
Support Programs
Some Compression Results

Chapter 12—An Archiving Package
CAR and CARMAN
The CARMAN Command Set
The CAR File
The Header
Storing the Header
The Header CRC
Command-Line Processing
Generating the File List
Opening the Archive Files
The Main Processing Loop
Skipping/Copying Input File
File Insertion
File Extraction
Cleanup
The Code

Chapter 13—Fractal Image Compression
A brief history of fractal image compression
What is an Iterated Function System?
Basic IFS mathematics
Image compression with Iterated Function Systems
Image compression with Partitioned Iterated Function Systems
Fractal image decoding
Resolution independence
The sample program
The main compression module
Initialization
Domain classification
Image partitioning
Finding optimal affine maps
The decompression module
The complete code listing
Some Compression Results
Patents
Bibliography
Appendix A
Appendix B
Glossary
Index