Understanding Compression by McAnlis, Colt -- Read -- Imperial Library of Trantor

Index

Foreword Preface

How to Read This Book How to Read This Book Backwards Chapter Synopsis

1. Let’s Not Be Boring

The Five Buckets of Compression Algorithms Claude Shannon Is Infuriating! The Only Thing You Need to Know about Data Compression

A World Built on Data Compression

Music compression Image compression Video compression Genome mapping Compression and the economy

2. Do Not Skip This Chapter

Understanding Binary

Base 10 System Binary Number System

Converting from binary to decimal Converting from decimal to binary

Information Theory

An Excursion into Binary Search Entropy: The Minimum Bits Needed to Represent a Number Standard Number Lengths

3. Breaking Entropy

Understanding Entropy What This Entropy Stuff Is Good For Understanding Probability Breaking Entropy

Example 1: Delta Coding Example 2: Symbol Grouping Example 3: Permutations

Information Theory Versus Data Compression

4. Variable-Length Codes

Morse Code Probability, Entropy, and Codeword Size Variable-Length Codes

Using VLCs

Calculating symbol probabilities Assigning codewords to symbols Encoding Decoding

Creating VLCs

The prefix property

A Handful of Example VLCs

Binary code Unary codes Elias gamma encoding Elias delta coding And so many more!

Finding the Right Code for Your Data Set

5. Statistical Encoding

Statistically Compressing to Entropy Huffman Coding

Building a Huffman Tree Generating Codewords Encoding and Decoding Practical Implementations

Arithmetic Coding

Finding the Right Number Encoding Picking the Right Output Value Decoding Practical Implementations

Asymmetric Numeral Systems

Encoding and Decoding Using a Transform Table Creating the Reference Table

Choosing a maxVal

Using ANS for Compression Decoding Example So Where Does the Compression Come From?

Practical Compression: Which Statistical Algorithm Do I Choose?

6. Adaptive Statistical Encoding

Locality Matters for Entropy Adaptive VLC Encoding

Dynamically Building a VLC Table

Decoding

Literals Resets Knowing When to Reset Using This in Practice

Adaptive Arithmetic Coding Adaptive Huffman Coding The Modern Choice

7. Dictionary Transforms

A Basic Dictionary Transform

Finding the Right “Words”

The Lempel-Ziv Algorithm

How LZ Works

The search buffer Finding matches The “sliding window” Marking a match with a token When no match is found

Encoding Decoding Compressing LZ output

Offsets Lengths Literals

LZ Variants

LZ77 LZSS LZ78 or LZ2 LZW (Lempel–Ziv–Welch)

Collect Them All!

8. Contextual Data Transforms

Run-Length Encoding

Dealing with Short Runs Compressing

Delta Coding

XOR Delta Coding Frame of Reference Delta Coding Patched Frame of Reference Delta Coding

Finding b What do we do with exceptions?

Compressing Delta-Encoded Data Does It Work on Text?

Move-to-Front Coding

Avoiding Rogue Symbols

Move-ahead-k Wait-c-and-move

Compressing MTF

Burrows–Wheeler Transform

Ordering Is Important! How BWT Works Inverse BWT Practical Implementations Compressing BWT

Why not RLE? Why not LZ?

9. Data Modeling

The Chains of Markov

Markov and Compression

Encoding Decoding Compression

Practical Implementations

Prediction by Partial Matching

The Search Trie Compressing a Symbol Choosing a Sensible N Value Dealing with Unknown Symbols

Context Mixing

Types of Models Types of Mixing

The Next Big Thing?

10. Switching Gears

Media-Specific Compression General-Purpose Compression Compression in Practice

11. Evaluating Compression

Compression Usage Scenarios

Compressed Offline, Decompressed On-Client Compressed On-Client, Decompressed In-Cloud Compressed In-Cloud, Decompressed On-Client

Dynamic data that is generated by the cloud resource Large data that’s passed off to the cloud for efficient computing

Compressed On-Client, Decompressed On-Client

Compression Need Compression Ratio Compression Performance Decompression Performance Ability to Decode-Stream Comparing Compressors

12. Compressing Image Data Types

Understanding Quality Versus File Size

What Reduces Image Quality? Measuring Image Quality Making This Work

Image Dimensions Are Important Choosing the Correct Image Format

PNG JPG GIF WebP And Now for Choosing...

GPU Texture Formats Vector Formats Eyes on the Prize

13. Serialized Data

Understanding Common Use Cases

Dynamically Server-Built Data Statically Built Server-Owned Data Dynamically Client-Built Data Statically Client-Owned Data

Issues with Serialized Formats

Human-Readable Text Slow Decode Times

Smaller Serialized Data

Use a Binary Serialization Format Restructure Lists for Better Compression Organize for Efficient Fetching Segment Out Data into the Proper Compression Format

14. Lossy Data Compression 15. Making the World a Little Smaller

Data Compression and You Data Compression and the Bottom Line

User Acquisition and Retention Running Costs Planning Ahead

Making Your Users’ Lives a Little More Magical and Less Expensive Thinking About What’s Next in Technology

The Next Five Billion Users Mobile Networks

...Starting Now

Glossary of Compression Words Index

← Prev
Back
Next →

← Prev
Back
Next →