**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

- The Algorithm
**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

- Digital Audio Concepts
**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

- Enter Compression
**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

- CAR and CARMAN
**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