Understanding Compression. Data Compression for

Understanding Compression. Data Compression for - Opis

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 skyrocketKnow your data, circumstances, and algorithm options when choosing compression toolsExplore variable-length codes, statistical compression, arithmetic numerical coding, dictionary encodings, and context modelingExamine tradeoffs between file size and quality when choosing image compressorsLearn ways to compress client- and server-generated data objectsMeet the inventors and visionaries who created data compression algorithms Spis treści:
Foreword
Preface
How to Read This Book
How to Read This Book Backwards
Chapter Synopsis
1. Lets 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 (...) więcej 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 (LempelZivWelch)
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
BurrowsWheeler 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 thats 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 Whats Next in Technology
The Next Five Billion Users
Mobile Networks
...Starting Now
Glossary of Compression Words
Index mniej