Understanding Compression : Data Compression for Modern Developers

If you want to attract and retain users in the booming mobile services market, you need a quick-loading app that won’t churn through their data plans. The key is to compress multimedia and other data into smaller files, but finding the right method is tricky. This witty book helps you understand how data compression algorithms work—in theory and practice—so you can choose the best solution among all the available compression tools. With tables, diagrams, games, and as little math as possible, authors Colt McAnlis and Aleks Haecky neatly explain the fundamentals. Learn how compressed files are better, cheaper, and faster to distribute and consume, and how they’ll give you a competitive edge. • Learn why compression has become crucial as data production continues to skyrocket • Know your data, circumstances, and algorithm options when choosing compression tools • Explore variable-length codes, statistical compression, arithmetic numerical coding, dictionary encodings, and context modeling • Examine tradeoffs between file size and quality when choosing image compressors • Learn ways to compress client- and server-generated data objects • Meet the inventors and visionaries who created data compression algorithms Copyright 4 Table of Contents 7 Foreword 13 Preface 17 How to Read This Book 19 How to Read This Book Backwards 19 Chapter Synopsis 20 Chapter 1. Let’s Not Be Boring 23 The Five Buckets of Compression Algorithms 23 Claude Shannon Is Infuriating! 24 The Only Thing You Need to Know about Data Compression 25 A World Built on Data Compression 26 Chapter 2. Do Not Skip This Chapter 31 Understanding Binary 31 Base 10 System 31 Binary Number System 32 Information Theory 35 An Excursion into Binary Search 36 Entropy: The Minimum Bits Needed to Represent a Number 38 Standard Number Lengths 39 Chapter 3. Breaking Entropy 41 Understanding Entropy 41 What This Entropy Stuff Is Good For 43 Understanding Probability 44 Breaking Entropy 45 Example 1: Delta Coding 46 Example 2: Symbol Grouping 47 Example 3: Permutations 48 Information Theory Versus Data Compression 53 Chapter 4. Variable-Length Codes 55 Morse Code 55 Probability, Entropy, and Codeword Size 58 Variable-Length Codes 60 Using VLCs 60 Creating VLCs 64 A Handful of Example VLCs 66 Finding the Right Code for Your Data Set 73 Chapter 5. Statistical Encoding 75 Statistically Compressing to Entropy 75 Huffman Coding 77 Building a Huffman Tree 77 Generating Codewords 79 Encoding and Decoding 80 Practical Implementations 80 Arithmetic Coding 82 Finding the Right Number 83 Encoding 84 Picking the Right Output Value 86 Decoding 86 Practical Implementations 91 Asymmetric Numeral Systems 91 Encoding and Decoding Using a Transform Table 92 Creating the Reference Table 93 Using ANS for Compression 96 Decoding Example 97 So Where Does the Compression Come From? 98 Practical Compression: Which Statistical Algorithm Do I Choose? 99 Chapter 6. Adaptive Statistical Encoding 101 Locality Matters for Entropy 101 Adaptive VLC Encoding 103 Dynamically Building a VLC Table 103 Literals 106 Resets 109 Knowing When to Reset 110 Using This in Practice 111 Adaptive Arithmetic Coding 111 Adaptive Huffman Coding 112 The Modern Choice 113 Chapter 7. Dictionary Transforms 115 A Basic Dictionary Transform 116 Finding the Right “Words” 117 The Lempel-Ziv Algorithm 120 How LZ Works 121 Encoding 126 Decoding 127 Compressing LZ output 128 LZ Variants 129 Collect Them All! 132 Chapter 8. Contextual Data Transforms 133 Run-Length Encoding 134 Dealing with Short Runs 134 Compressing 136 Delta Coding 137 XOR Delta Coding 140 Frame of Reference Delta Coding 141 Patched Frame of Reference Delta Coding 142 Compressing Delta-Encoded Data 145 Does It Work on Text? 145 Move-to-Front Coding 145 Avoiding Rogue Symbols 147 Compressing MTF 148 Burrows–Wheeler Transform 148 Ordering Is Important! 150 How BWT Works 150 Inverse BWT 152 Practical Implementations 154 Compressing BWT 154 Chapter 9. Data Modeling 157 The Chains of Markov 158 Markov and Compression 161 Practical Implementations 167 Prediction by Partial Matching 167 The Search Trie 169 Compressing a Symbol 171 Choosing a Sensible N Value 172 Dealing with Unknown Symbols 172 Context Mixing 172 Types of Models 173 Types of Mixing 175 The Next Big Thing? 176 Chapter 10. Switching Gears 177 Media-Specific Compression 177 General-Purpose Compression 178 Compression in Practice 179 Chapter 11. Evaluating Compression 181 Compression Usage Scenarios 181 Compressed Offline, Decompressed On-Client 181 Compressed On-Client, Decompressed In-Cloud 182 Compressed In-Cloud, Decompressed On-Client 182 Compressed On-Client, Decompressed On-Client 183 Compression Need 183 Compression Ratio 184 Compression Performance 185 Decompression Performance 186 Ability to Decode-Stream 186 Comparing Compressors 187 Chapter 12. Compressing Image Data Types 189 Understanding Quality Versus File Size 189 What Reduces Image Quality? 191 Measuring Image Quality 193 Making This Work 195 Image Dimensions Are Important 195 Choosing the Correct Image Format 197 PNG 197 JPG 198 GIF 199 WebP 199 And Now for Choosing... 199 GPU Texture Formats 201 Vector Formats 202 Eyes on the Prize 204 Chapter 13. Serialized Data 205 Understanding Common Use Cases 206 Dynamically Server-Built Data 206 Statically Built Server-Owned Data 206 Dynamically Client-Built Data 206 Statically Client-Owned Data 206 Issues with Serialized Formats 207 Human-Readable Text 207 Slow Decode Times 208 Smaller Serialized Data 208 Use a Binary Serialization Format 208 Restructure Lists for Better Compression 209 Organize for Efficient Fetching 210 Segment Out Data into the Proper Compression Format 213 Chapter 14. Lossy Data Compression 215 Chapter 15. Making the World a Little Smaller 217 Data Compression and You 217 Data Compression and the Bottom Line 217 User Acquisition and Retention 217 Running Costs 218 Planning Ahead 219 Making Your Users’ Lives a Little More Magical and Less Expensive 219 Thinking About What’s Next in Technology 220 The Next Five Billion Users 220 Mobile Networks 220 ...Starting Now 221 Glossary of Compression Words 223 Index 231 About the Authors 240 Colophon 240