Index
B
- base 10 number system, Base 10 System
- base 2 number system, Binary Number System
- base64-encoding PNG images in CSS files, Segment Out Data into the Proper Compression Format
- binary code, Binary code
- binary number system, Binary Number System
- binary numbers, Understanding Binary
- binary search, An Excursion into Binary Search, Finding the Right Number
- binary serialization formats, Use a Binary Serialization Format
- binary trees (in Huffman encoding)
- bits
- bits-per-symbol (BPS) reset threshold, Knowing When to Reset
- bitwise exclusive OR (XOR) and delta coding, XOR Delta Coding
- block sorting transforms, Practical Implementations
- blocking in image compression, What Reduces Image Quality?, JPG
- Brin, Sergey, The Chains of Markov
- Brotli compressor, General-Purpose Compression
- browsers
- BSON, Use a Binary Serialization Format
- Burrows, Michael, Burrows–Wheeler Transform
- Burrows-Wheeler transform (BWT), Genome mapping, Burrows–Wheeler Transform-Why not LZ?
- BZIP2 algorithm, Practical Implementations, General-Purpose Compression
C
- Cleary, John, Prediction by Partial Matching
- client-side compression, Compressed On-Client, Decompressed In-Cloud, Compressed On-Client, Decompressed On-Client
- cloud computing
- codecs, Practical Implementations
- codewords
- Cohen, Jared, The Next Five Billion Users
- columns (ANS reference table), determining number of values in, Creating the Reference Table
- compress utility, LZW (Lempel–Ziv–Welch)
- compressed offline, decompressed on-client, Compressed Offline, Decompressed On-Client
- compressed on-client, decompressed in-cloud, Compressed On-Client, Decompressed In-Cloud
- compression
- algorithm classifications, The Five Buckets of Compression Algorithms
- and future trends in technology, Thinking About What’s Next in Technology
- and the bottom line, Data Compression and the Bottom Line
- as rebellion against information entropy, Claude Shannon Is Infuriating!
- compressing a run-length encoded stream, Compressing
- compressing BWT output, Compressing BWT
- compressing delta-encoded data, Compressing Delta-Encoded Data
- compressing Lempel-Ziv output, Compressing LZ output
- compressing move-to-front output, Compressing MTF
- compressing permutations, Example 3: Permutations
- computing world built on, A World Built on Data Compression
- economic importance of, Compression and the economy
- entropy in information theory versus, Information Theory Versus Data Compression
- future of data compression, Data Compression and You
- general purpose, General-Purpose Compression
- in practice, Compression in Practice
- main ideas of, The Only Thing You Need to Know about Data Compression
- Markov chains and, Compression
- media-specific, Media-Specific Compression
- serialized data, Segment Out Data into the Proper Compression Format
- Shannon's research, application to, Claude Shannon Is Infuriating!
- compression ratio, Compression Ratio
- Compressor Head (YouTube series), Burrows–Wheeler Transform
- context, Data Modeling
- (see also contextual transforms; multicontext encoders)
- importance of, Data Modeling
- context mixing, Context Mixing-The Next Big Thing?
- context modeling, The Five Buckets of Compression Algorithms
- contextual transforms, Contextual Data Transforms-Why not LZ?
- conversion rates, web page loading speed and, User Acquisition and Retention
- CSS files, base64-encoding PNG files in, Segment Out Data into the Proper Compression Format
- current reading location in the stream (LZ), The search buffer
D
- data modeling, Data Modeling-The Next Big Thing?
- decimal numbers, Base 10 System
- decision trees, Huffman Coding
- decoding, Example 3: Permutations
- in adaptive VLC encoding, Decoding
- in ANS, using transform table, Encoding and Decoding Using a Transform Table
- in arithmetic coding, Decoding
- in asymmetric numeral systems, Decoding Example
- in Burrows-Wheeler transform, Inverse BWT
- in Huffman coding, Encoding and Decoding
- in Lempel-Ziv algorithm, Decoding
- in Markov chains, Decoding
- in move-to-front coding, Move-to-Front Coding
- in run-length encoding, Run-Length Encoding
- of encoded data in VLCs, Decoding
- slow decode time with serialized formats, Slow Decode Times
- decompression
- DEFLATE algorithm, LZW (Lempel–Ziv–Welch), General-Purpose Compression
- delta coding, Example 1: Delta Coding, Delta Coding-Move-to-Front Coding
- deserialization, Serialized Data
- dictionary encodings, The Five Buckets of Compression Algorithms
- dictionary transforms, Dictionary Transforms-Collect Them All!, Contextual Data Transforms
- divide-by-the-base method, Converting from decimal to binary
- DNA, use of Burrows-Wheeler transforms with, Genome mapping, Practical Implementations
- Duda, Jarek, Asymmetric Numeral Systems
- DXT compressed texture format, GPU Texture Formats
E
- economic importance of compression, Compression and the economy
- (see also finances, data compression and)
- edges, errors in, What Reduces Image Quality?
- Elias delta coding, Elias delta coding
- Elias gamma encoding, Elias gamma encoding
- Elias, Peter, Binary code, Arithmetic Coding
- elimination coding, using to compress permutations, Example 3: Permutations
- encoding
- in adaptive VLC encoding, Decoding
- in ANS, using transform table, Encoding and Decoding Using a Transform Table
- in arithmetic coding, Encoding
- in Huffman coding, Encoding and Decoding
- in Lempel-Ziv algorithm, Encoding
- in Markov chains, Encoding
- in prediction by partial matching, Compressing a Symbol
- in run-length encoding, Run-Length Encoding
- in VLCs, Encoding
- entropy, Entropy: The Minimum Bits Needed to Represent a Number, Understanding Entropy-Information Theory Versus Data Compression
- breaking, Breaking Entropy-Example 3: Permutations
- defined, Understanding Entropy
- failure to take order of symbols into account, Ordering Is Important!
- how it's used, What This Entropy Stuff Is Good For
- in move-to-front coding, Move-to-Front Coding
- in tokenization, Finding the Right “Words”
- information theory versus data compression, Information Theory Versus Data Compression
- Kolmogorov Complexity and, Information Theory Versus Data Compression
- locality, adapting to in statistical coding, Locality Matters for Entropy
- numeric data compression and, Delta Coding
- probability and codeword size, Probability, Entropy, and Codeword Size-Variable-Length Codes
- statistically compressing to, Statistically Compressing to Entropy-Statistically Compressing to Entropy
- understanding probability, Understanding Probability
- entropy coding, Statistically Compressing to Entropy
- (see also statistical coding)
- Entropy of a Set formula, Understanding Entropy
- ETC compressed texture format, GPU Texture Formats
- evaluating compression, Evaluating Compression-Comparing Compressors
- ability to decode streaming data, Ability to Decode-Stream
- comparing compressors, Comparing Compressors
- compression performance, Compression Performance
- compression ratio, Compression Ratio
- decompression performance, Decompression Performance
- matching compression algorithm to data type, Compression Need
- usage scenarios, Compression Usage Scenarios
- compressed in-cloud, decompressed on-client, Compressed In-Cloud, Decompressed On-Client
- compressed offline, decompressed on-client, Compressed Offline, Decompressed On-Client
- compressed on-client, decompressed in-cloud, Compressed On-Client, Decompressed In-Cloud
- compressed on-client, decompressed on-client, Compressed On-Client, Decompressed On-Client
- exclusive OR (XOR), XOR Delta Coding
- exponents, Base 10 System
F
- Facebook
- Fano, Robert, Huffman Coding
- finances, data compression and, Data Compression and the Bottom Line-Planning Ahead
- finite state entropy (FSE), Practical Compression: Which Statistical Algorithm Do I Choose?
- fixed-length buckets of bits for numbers, Standard Number Lengths
- FOR (frame of reference), Frame of Reference Delta Coding
- fractions, bits and, Entropy: The Minimum Bits Needed to Represent a Number
- frame of reference delta coding, Frame of Reference Delta Coding
- frames, Frame of Reference Delta Coding
- frequency or probability P of a symbol v, Understanding Entropy
- FSE (finite state entropy), Practical Compression: Which Statistical Algorithm Do I Choose?
G
- Game Boy Advance BIOS, LZSS
- general purpose compression, General-Purpose Compression
- genome mapping, Genome mapping
- GIF image format, GIF, And Now for Choosing...
- Golomb codes, Compressing
- Golomb, Solomon W., Compressing
- Google
- GPU texture formats, GPU Texture Formats
- gradients, What Reduces Image Quality?
- GZIP algorithm
- gzip compression, Dictionary Transforms
H
- hardware compressor codecs, client support for, Compression Performance
- hardware decoders, Decompression Performance
- Henry, Joseph, Morse Code
- hexadecimal numbers, Converting from decimal to binary
- HTTPArchive website, Planning Ahead
- Huffman coding, Huffman Coding-Arithmetic Coding
- Huffman, David Albert, Practical Implementations
I
- IBM patents, arithmetic coding and, Arithmetic Coding
- image compression, Image compression, The Modern Choice, Compressing Image Data Types-Eyes on the Prize
- images
- indexes, encoding, Example 3: Permutations
- information entropy, Claude Shannon Is Infuriating!, Understanding Entropy
- information theory, Claude Shannon Is Infuriating!, Information Theory-Standard Number Lengths
- Internet connectivity, The Next Five Billion Users
- ITU definition of entropy coder, Statistically Compressing to Entropy
L
- Laplace estimator, Dealing with Unknown Symbols
- Large Text Compression Benchmark, Comparing Compressors
- least significant bit (LSB), Converting from decimal to binary
- Lempel, Abraham, The Lempel-Ziv Algorithm
- Lempel-Ziv algorithm, The Lempel-Ziv Algorithm-LZW (Lempel–Ziv–Welch)
- LENA image, Image compression
- lengths
- lexicographical pemutations, Ordering Is Important!
- LHarc archiver, LZSS
- linear mixing, Types of Mixing
- lists, restructuring for better compression, Restructure Lists for Better Compression
- literals
- local-order-estimator algorithm, Dealing with Unknown Symbols
- locality and contextuality, Types of Models
- locality of entropy of a stream, adapting to, Locality Matters for Entropy
- locality-dependent skewing, Locality Matters for Entropy
- LOG2 form of numbers, Entropy: The Minimum Bits Needed to Represent a Number
- logic synthesis, using for compression, Information Theory Versus Data Compression
- logistic mixing, Types of Mixing
- look ahead buffer (in Lempel-Ziv), The search buffer
- lossless image format (PNG), PNG
- lossy compression, Practical Implementations, Compressing Image Data Types, Lossy Data Compression
- lossy image formats, JPG
- LZ (see Lempel-Ziv algorithm)
- LZ1 (see LZ77 algorithm)
- LZ2 (see LZ78 algorithm)
- LZ77 algorithm, LZ Variants
- LZ78 algorithm, LZ78 or LZ2
- LZMA algorithm, Arithmetic Coding
- LZSS algorithm, LZSS
- LZW (Lempel-Ziv-Welch) algorithm, LZW (Lempel–Ziv–Welch), GIF
M
- Markov chains, The Chains of Markov-Practical Implementations
- Markov, Andrey Andreyevich, The Chains of Markov
- matches in LZ algorithm
- A Mathematical Theory of Communication (Shannon), Claude Shannon Is Infuriating!
- maxVal, choosing for ANS reference table, Choosing a maxVal, So Where Does the Compression Come From?
- mean-square error (MSE) of compressed images, Measuring Image Quality
- media compressors, steaming mode, Ability to Decode-Stream
- media-specific compression, Locality Matters for Entropy, Media-Specific Compression
- mobile computing
- Morse code, Morse Code-Morse Code
- Morse, Samuel F.B., Morse Code
- most significant bit (MSB), Converting from decimal to binary, And so many more!
- MOV file format, Video compression
- move-to-front (MTF) coding, Move-to-Front Coding-Compressing MTF
- Mozilla Firefox, WebP image fomat and, And Now for Choosing...
- MozJPEG codec, And Now for Choosing...
- MP3 file format, Music compression
- MSE (mean-square error) of compressed images, Measuring Image Quality
- MSGPACK, Use a Binary Serialization Format
- multicontext encoders, Data Modeling
- multicontext modeling, The Five Buckets of Compression Algorithms
- multisets, encoding, Example 1: Delta Coding
- music compression, Music compression
N
- N value, choosing in PPM, Choosing a Sensible N Value
- n-grams, Types of Models
- Napster, Music compression
- Netflix, compression technology and running costs, Running Costs
- neural network, use in logistic mixing, Types of Mixing
- never-seen symbol in PPM, Dealing with Unknown Symbols
- New Digital Age (Schmidt and Cohen), The Next Five Billion Users
- NP-complete problems, Locality Matters for Entropy
- number lengths, standard, Standard Number Lengths
- numeric data, compression of, Delta Coding
P
- Page, Larry, The Chains of Markov
- PageRank algorithm, The Chains of Markov
- palletization, GIF
- PAQ series of compression algorithms, Context Mixing
- patched frame of reference delta coding, Patched Frame of Reference Delta Coding
- peak signal to noise ratio (PSNR), Measuring Image Quality
- performance
- permutations, Example 3: Permutations
- PFOR (see patched frame of reference delta coding)
- phrases, A Basic Dictionary Transform
- PKZip, LZSS
- PNG image format, PNG, And Now for Choosing...
- Portable Network Graphics (see PNG image format)
- PPM (see prediction by partial matching)
- PPM*, Choosing a Sensible N Value
- PPMD, Dealing with Unknown Symbols
- PPMZ, Dealing with Unknown Symbols
- prediction by partial matching (PPM), Prediction by Partial Matching-Dealing with Unknown Symbols
- predictive encoders, Data Modeling
- prefix property, The prefix property
- probability
- program synthesis, using for compression, Information Theory Versus Data Compression
- PSNR (peak signal to noise ratio), Measuring Image Quality
- PVR compressed texture format, GPU Texture Formats
R
- range coding, Arithmetic Coding
- range intervals
- in arithmetic encoding, Encoding
- subdivision based on probability, resulting in compression, Decoding
- RAR archiver, LZSS
- raster format images, Vector Formats
- reference tables
- resets in adaptive statistical encoding
- reversible transforms, Inverse BWT
- RGBA_8888 representations, GPU Texture Formats
- Rissanen, Jorma, Arithmetic Coding
- RLE (see run-length encoding)
- rogue symbols in MTF coding, Avoiding Rogue Symbols
- rows (ANS reference table), determining numbers in, Creating the Reference Table
- run-length encoding (RLE), Run-Length Encoding-Delta Coding
- running costs, Running Costs
S
- Schmidt, Eric, The Next Five Billion Users
- search buffer (in Lempel-Ziv), The search buffer
- search trie in PPM, The Search Trie
- second-order context, The Chains of Markov
- serialized data, Serialized Data-Segment Out Data into the Proper Compression Format
- sets, Entropy of a Set formula, Understanding Entropy
- Shannon entropy H of the set G, Understanding Entropy
- Shannon, Claude, Claude Shannon Is Infuriating!, Understanding Entropy
- Shannon-Fano coding, Statistically Compressing to Entropy, Huffman Coding
- Shopzilla, web page loading speed and conversion rates, User Acquisition and Retention
- short runs in RLE, Dealing with Short Runs
- Silicon Valley (TV show), Comparing Compressors
- skewed data, The Only Thing You Need to Know about Data Compression
- sliding window search buffer (LZ), The “sliding window”
- Soderberg, Lena, Image compression
- SortedArray (MTF coding), Move-to-Front Coding
- sparse contexts, Types of Models
- specialized models for different file types (PAQ), Types of Models
- Squash Compression Benchmark, Comparing Compressors
- Squeeze Chart, Comparing Compressors
- statistical compression, The Five Buckets of Compression Algorithms
- statistical encoders, Statistically Compressing to Entropy
- statistical encoding, Statistically Compressing to Entropy-Practical Compression: Which Statistical Algorithm Do I Choose?
- adaptive, Locality Matters for Entropy
- (see also adaptive statistical encoding)
- applying a statistical compressor to run-length encoding, Compressing
- applying statistical compressor to BWT output, Compressing BWT
- arithmetic coding, Arithmetic Coding-Asymmetric Numeral Systems
- combining LZ with, Compressing LZ output
- deciding which algorithm to use, Practical Compression: Which Statistical Algorithm Do I Choose?
- how it works, Contextual Data Transforms
- Huffman coding, Huffman Coding-Arithmetic Coding
- limitations of, A Basic Dictionary Transform
- move-to-front coding and, Compressing MTF
- statistical coders as single-context Markov chains, Markov and Compression
- statistically compressing to entropy, Statistically Compressing to Entropy-Statistically Compressing to Entropy
- using dictonary transforms as preprocessing stage, A Basic Dictionary Transform
- streaming data, Locality Matters for Entropy
- structural similarity (SSIM) index, Measuring Image Quality
- SVG image format, Vector Formats
- symbol groupings, Example 2: Symbol Grouping
- "A Symbolic Analysis of Relay and Switching Circuits", Claude Shannon Is Infuriating!
- symbols
T
- tANS variant of ANS, Encoding and Decoding Using a Transform Table
- (see also asymmetric numeral systems)
- telegraph, invention of, Morse Code
- text
- third-order context, The Chains of Markov
- tokenization, Finding the Right “Words”, Contextual Data Transforms
- tokens
- transform tables, encoding and decoding with, Encoding and Decoding Using a Transform Table
- trie, The Search Trie
- TurboRLE, Compressing
- two-dimensional contexts, Types of Models
V
- Vail, Alfred, Morse Code
- variable-length codes (VLCs), The Five Buckets of Compression Algorithms, Variable-Length Codes-Finding the Right Code for Your Data Set
- adaptive VLC encoding, Adaptive VLC Encoding-Using This in Practice
- applying a static VLC to run-length encoding, Compressing
- creating, Creating VLCs
- examples of, A Handful of Example VLCs
- finding the right code for your data set, Finding the Right Code for Your Data Set-Finding the Right Code for Your Data Set
- how they were built, A Handful of Example VLCs
- infrequent use in modern compression, Statistically Compressing to Entropy
- Morse code, Morse Code-Morse Code
- probability, entropy, and codeword size, Probability, Entropy, and Codeword Size-Variable-Length Codes
- using to encode data, Using VLCs
- using with Markov chains, Compression
- VarInt codes, And so many more!
- vector image formats, Vector Formats-Eyes on the Prize
- video compression, Video compression, The Modern Choice
- VLCs (see variable length codes)
W
- Walmart, web page loading speed and conversion rates, User Acquisition and Retention
- WAV file format, Music compression
- web page loading speed and conversion rates, User Acquisition and Retention
- WebP image format, WebP
- websites, increasing size of, Planning Ahead
- Weissman Score, Comparing Compressors
- Weissman, Tsachy, Comparing Compressors
- Welch, Terry, LZW (Lempel–Ziv–Welch)
- Wheeler, David, Burrows–Wheeler Transform
- whole-word n-grams, Types of Models
- Witten, Ian, Prediction by Partial Matching
- words, finding the right words in dictionary transforms, Finding the Right “Words”
Understanding Compression
Published by
O'Reilly Media, Inc., 2016