Data Compression Cheatsheet

What is Data Compression?

The process of reducing the size of data (number of bits) to store or transmit it more efficiently.

Why Compress?

• Storage Savings: Store more data in the same space.
• Faster Data Transmission: Reduce time and bandwidth needed to transfer data.
• Reduced Costs: Lower expenses for storage and bandwidth.

Information Theory Basics:

• Entropy: A measure of the inherent randomness or uncertainty in data. Represents the theoretical lower bound for compression.
• Redundancy: Information that is repeated or predictable. Types include:
  • Spatial Redundancy
  • Temporal Redundancy
  • Statistical/Symbol Redundancy
  • Perceptual Redundancy

Incompressibility

Truly random data (or data that appears random, like encrypted or already well-compressed data) cannot be significantly compressed further by lossless methods. Applying a lossless compressor might even slightly increase size due to overhead.

Rate-Distortion Theory (Lossy)

A mathematical framework defining the trade-off between compression rate (bits used) and distortion (loss of fidelity). It sets the minimum achievable rate for a given distortion level, guiding lossy codec design.

Lossless vs. Lossy

Near-Lossless Compression

A specialized category where decompressed data isn't identical, but differences are strictly bounded and often imperceptible (e.g., some scientific data, medical imaging).

• Compression Ratio/Savings: Original Size / Compressed Size or (1 - CS/OS) * 100%.
• Compression/Decompression Speed: Rate of data processing (e.g., MB/s).
• Computational Cost: CPU, memory usage.
• Fidelity/Quality (Lossy): Objective (PSNR, SSIM) or subjective perception.
• Asymmetry: Difference in computational cost between compression and decompression.
• Robustness to Errors: How well a compressed stream recovers from bit errors.

• Dictionary-Based: Replaces sequences with references (e.g., LZ77, LZW).
  Diagram: Sliding Window & Dictionary
• Statistical Modeling: Shorter codes for frequent symbols (e.g., Huffman, Arithmetic).
  Diagram: Huffman Tree Example
• Transform Coding: Converts data to a more compressible domain (e.g., DCT in JPEG).
  Diagram: DCT Block Transformation
• Run-Length Encoding (RLE): Replaces sequences of identical symbols (e.g., AAAAA -> 5A).
• Predictive Coding: Encodes difference from predicted value.
• Context Modeling: Estimates symbol probability based on preceding symbols.
• Burrows-Wheeler Transform (BWT): Reversible transform grouping similar characters (used in bzip2).
• Delta Coding: Stores difference between consecutive data elements.

Core Idea:

Replaces runs of identical data with a count and the single data value (e.g., WWWWBB -> 4W2B).

Use Cases:

Simple graphics, icons, fax transmissions, bitmap images (BMP), TIFF.

Strengths:

Very simple, computationally inexpensive, fast.

Weaknesses:

Inefficient for data without long runs; can even increase file size.

File Extensions:

Used within BMP, TIFF, PDF.

Core Idea:

Builds a prefix code tree where more frequent symbols have shorter paths (codes).

Use Cases:

Component in Deflate (ZIP, GZIP), JPEG, MP3, PNG.

Strengths:

Optimal per-symbol coding, relatively simple.

Weaknesses:

Requires symbol frequencies beforehand (or two passes). Not adaptive by itself.

Core Idea:

Replace repeated sequences with references to previously seen data.

Use Cases:

General-purpose text/data. Basis for Deflate (ZIP, GZIP).

Strengths:

Adaptive, good compression ratios.

Weaknesses:

Can be slower if not optimized.

Core Idea:

Builds a string translation table from input data; outputs codes for encountered sequences.

Use Cases:

GIF images, compress utility, TIFF, PDF.

Strengths:

Simple, fast decompression.

Weaknesses:

Patents (now expired). Less efficient than modern LZ variants.

File Extensions:

.gif (internally)

Core Idea:

Reorders data using BWT to group similar characters, then compresses the transformed data.

Use Cases:

General file compression, software distribution (common on Linux/Unix).

Strengths:

Generally better compression ratios than Deflate.

Weaknesses:

Significantly slower compression and decompression than Deflate, Zstd.

File Extensions:

.bz2

Core Idea:

Combines an LZ77-like dictionary coder with sophisticated probability modeling (range coder).

Use Cases:

Default for 7-Zip (.7z), XZ Utils (.xz). Software distribution, large archives.

Strengths:

Very high compression ratios.

Weaknesses:

Slow compression, high memory usage. Decompression is faster but not top-tier.

File Extensions:

.7z, .xz

Core Idea:

Finds duplicate strings with LZ77, then compresses literals and LZ77 output with Huffman.

Use Cases:

.zip, .gz files, PNG images, HTTP compression.

Strengths:

Good balance of speed and ratio, widely adopted.

Weaknesses:

Outperformed in ratio and/or speed by modern algorithms like Zstd, Brotli.

File Extensions:

.zip, .gz, .png (internally)

Core Idea:

Represents the input data as a single fractional number in the range [0,1). More efficient than Huffman for skewed probabilities.

Use Cases:

Component in JPEG 2000, H.264/AVC, some bzip2 variants.

Strengths:

Higher compression efficiency than Huffman, especially for skewed probabilities.

Weaknesses:

More computationally complex, historically patent-encumbered.

Core Idea:

Uses LZ77, Huffman coding, 2nd order context modeling, and a large pre-defined static dictionary.

Use Cases:

Web content (HTTP compression), WOFF2 fonts. Excels on text.

Strengths:

Excellent compression ratios, fast decompression.

Weaknesses:

Compression can be slower than Gzip/Zstd, though offers quality levels.

File Extensions:

.br (files), br (HTTP content encoding)

Core Idea:

Combines an LZ77-variant with a fast entropy stage (Finite State Entropy - FSE, an Asymmetric Numeral System variant).

Use Cases:

General-purpose, databases (MySQL, RocksDB), file systems (ZFS, Btrfs), real-time, archives (.tar.zst).

Strengths:

Very fast compression/decompression, flexible levels, good ratios, dictionary support.

Weaknesses:

Newer, so adoption still growing vs. Deflate (though rapidly).

File Extensions:

.zst

Core Idea:

Uses preceding symbols (context) to predict the next symbol's probability for arithmetic coding.

Use Cases:

Text compression, general-purpose where ratio is paramount.

Strengths:

Very high compression ratios, adaptive.

Weaknesses:

Computationally expensive (CPU and memory), can be very slow.

Core Idea:

Models audio signal with linear prediction, encodes residual error.

Use Cases:

Archival of music, high-fidelity audio playback.

Strengths:

Good audio compression (30-60% reduction), royalty-free, widely supported.

Weaknesses:

Specifically for audio.

File Extensions:

.flac, .fla

Core Idea:

Similar to FLAC, uses linear prediction with different parameters and entropy coding.

Use Cases:

Used within Apple's ecosystem (Apple Music Lossless, iTunes libraries).

Strengths:

Similar compression to FLAC, well-integrated in Apple products.

Weaknesses:

Less universal support outside Apple ecosystem compared to FLAC.

File Extensions:

.m4a (when containing ALAC)

Core Idea:

Transforms 8x8 pixel blocks using Discrete Cosine Transform (DCT), quantizes coefficients, then entropy codes.

Use Cases:

Still images (photographs). Very common on the web.

Strengths:

Widely supported, good for photos at reasonable quality.

Weaknesses:

Blocking artifacts at low quality, not ideal for sharp lines/text.

Parameters:

Quality setting (1-100), chroma subsampling.

File Extensions:

.jpg, .jpeg

Core Idea:

Stores HEVC-encoded image data within an HEIF container. Offers better compression than JPEG for similar quality.

Use Cases:

Default image capture on modern iPhones/iPads. Growing support on other platforms.

Strengths:

~50% smaller file size than JPEG for similar quality. Supports transparency, animations, depth maps, Live Photos.

Weaknesses:

Not as universally supported as JPEG yet, though adoption is increasing. Can have licensing considerations (HEVC patents).

Parameters:

Typically managed by capture device settings.

File Extensions:

.heic, .heif

Core Idea:

Intra-frame DCT-based codecs optimized for editing performance and high image fidelity.

Use Cases:

Video acquisition (iPhone Cinematic Mode), professional video editing (Final Cut Pro), intermediate/mastering format.

Strengths:

Excellent image quality, robust editing performance, supports alpha channels (ProRes 4444), multiple data rates/quality levels.

Weaknesses:

Large file sizes compared to distribution codecs (H.264/HEVC). Not intended for final delivery to end-users.

Variants:

ProRes Proxy, LT, 422, 422 HQ, 4444, 4444 XQ, ProRes RAW.

File Extensions:

.mov (QuickTime container)

Core Idea:

Applies wavelet transform to entire image or large tiles, offering progressive decoding.

Use Cases:

Medical imaging (DICOM), digital cinema, archival.

Strengths:

Better quality than JPEG at high compression, lossless option, ROI coding.

Weaknesses:

More complex, less native software support than JPEG, computationally intensive.

Parameters:

Compression ratio/bitrate, quality layers, lossless/lossy.

File Extensions:

.jp2, .j2k

Core Idea:

Lossy uses intra-frame prediction from VP8 video; lossless uses different techniques (spatial prediction, LZ77).

Use Cases:

Web images, aiming to replace JPEG, PNG, GIF.

Strengths:

Better compression than JPEG (lossy) and PNG (lossless). Supports animation & alpha.

Weaknesses:

Lossy quality can be debated vs. highly optimized JPEGs or newer AVIF.

Parameters:

Quality setting (lossy), effort setting (lossless).

File Extensions:

.webp

Core Idea:

Leverages AV1 video compression techniques for still images, stored in HEIF container.

Use Cases:

Web images, aiming for superior quality/ratio over JPEG/WebP.

Strengths:

Significantly better compression than JPEG/WebP. Supports HDR, wide color gamut, lossless, animation. Royalty-free.

Weaknesses:

Newer, software/browser support still growing. Can be computationally demanding.

Parameters:

Quality setting (quantizer), speed/effort.

File Extensions:

.avif

Core Idea:

Advanced video coding with flexible macroblocks, improved prediction, in-loop deblocking filter.

Use Cases:

Blu-ray, streaming, video conferencing, most web video.

Strengths:

Excellent quality/ratio balance, wide hardware support.

Weaknesses:

More complex than MPEG-2, royalty-bearing.

Parameters:

Bitrate, profiles (Baseline, Main, High), levels, GOP settings.

File Extensions:

.mp4, .mkv, .mov

Core Idea:

Larger coding units (CTUs), improved prediction modes, Sample Adaptive Offset (SAO) filtering.

Use Cases:

4K/UHD Blu-ray, high-resolution streaming. Default video on modern iPhones/iPads.

Strengths:

Significantly better compression than H.264.

Weaknesses:

More complex, licensing was complicated (improving).

Parameters:

Bitrate, profiles (Main, Main10), tiers, levels.

File Extensions:

.mp4, .mkv, .mov

Core Idea:

Advanced video coding techniques, designed for web streaming and real-time communication.

Use Cases:

YouTube, WebRTC, other streaming services.

Strengths:

Good compression efficiency (comparable to early H.265), royalty-free, strong browser support.

Weaknesses:

Largely being superseded by AV1 for top-tier efficiency.

File Extensions:

Often in .webm, .mp4.

Core Idea:

Advanced techniques: larger superblocks, sophisticated prediction, CDEF/loop restoration filters.

Use Cases:

Web streaming (YouTube, Netflix, Twitch), real-time communications (WebRTC).

Strengths:

Excellent compression (better than HEVC), royalty-free. Apple hardware decoding from A17 Pro/M3 chips.

Weaknesses:

Very computationally intensive to encode (improving), decode can also be heavy without hardware support.

Parameters:

Bitrate, quality settings (CRF), speed presets.

File Extensions:

.mkv, .webm, .mp4 (with ISOBMFF)

Core Idea:

Discards parts of audio signal less perceptible to human hearing using psychoacoustic models.

Use Cases:

Digital audio, music files, podcasts.

Strengths:

Ubiquitous support, good quality at moderate bitrates.

Weaknesses:

Older, less efficient than AAC/Opus. Audible artifacts at low bitrates.

Parameters:

Bitrate (CBR/VBR, e.g., 128, 192, 320 kbps).

File Extensions:

.mp3

Core Idea:

Improved psychoacoustic model, MDCT with better windowing, more efficient coding techniques (TNS, PNS).

Use Cases:

Apple Music/iTunes, YouTube, streaming, digital radio (DAB+).

Strengths:

Better quality than MP3 at same bitrate, especially lower bitrates.

Weaknesses:

Several variants (AAC-LC, HE-AAC) can cause confusion.

Parameters:

Bitrate, profiles (LC, HE, HEv2).

File Extensions:

.aac, .m4a, .mp4

Core Idea:

Combines SILK (speech) and CELT (music) algorithms, dynamically switching or combining.

Use Cases:

VoIP, video conferencing (WebRTC default), game chat, streaming, audiobooks. Used by FaceTime audio.

Strengths:

Excellent quality across wide bitrate range, very low delay, royalty-free, adaptive.

Weaknesses:

Less ubiquitous for stored music vs. MP3/AAC (though growing).

Parameters:

Bitrate, application type (VoIP, Audio, Low-Delay).

File Extensions:

.opus (often in .ogg or .webm)

Core Idea:

Uses Modified Discrete Cosine Transform (MDCT), vector quantization, and codebook-based entropy encoding.

Use Cases:

Open-source software, indie games, some streaming (historically Spotify).

Strengths:

Good quality, royalty-free and open.

Weaknesses:

Less efficient than Opus/modern AAC at very low bitrates. Hardware support less widespread.

Parameters:

Quality level (q -1.0 to 10.0), average bitrate.

File Extensions:

.ogg, .oga

Psychoacoustics (Audio)

Lossy audio codecs (MP3, AAC, Opus) exploit auditory masking:

• Frequency Masking: Louder sounds make quieter sounds at nearby frequencies inaudible.
• Temporal Masking: A loud sound masks quieter sounds immediately before (pre-masking) or after (post-masking) it.

Codecs discard or heavily quantize information in masked regions.

Psychovisuals (Image/Video)

Lossy image/video codecs (JPEG, H.264) exploit Human Visual System (HVS) characteristics:

• Luminance vs. Chrominance Sensitivity: Humans are more sensitive to brightness (luminance) than color (chrominance). Chroma subsampling reduces color info.
• Frequency Sensitivity: Less sensitive to high-frequency details. Transform coding allows selective quantization.
• Contrast Masking: Visual patterns can mask noise within those regions.

Key Questions:

1. What data type? (Text, image, audio, video, binary)
2. Is loss acceptable? (Lossless vs. Lossy)
3. Primary goal? (Ratio, speed, quality, low cost)
4. Resource constraints? (CPU, RAM)
5. Target platform/ecosystem support?
6. Licensing/royalty concerns?
7. Energy consumption / battery life needs?
8. Standards compliance / interoperability needs?

General Guidelines:

• Text/Code: Zstd, Brotli, Gzip.
• Archives: Zstd (high levels), 7-Zip (LZMA2), XZ.
• Web Photos: JPEG, WebP, AVIF, HEIC (where supported).

Command-Line Archivers:

• gzip, zip, 7-Zip (7z), tar (with compressors)
• brotli, zstd, bzip2, xz

Libraries for Developers:

• zlib: (C library for Deflate)
• libjpeg-turbo: (JPEG C library)
• FFmpeg: (Audio/video codecs library & tool)

Applications:

Image Editors (GIMP, Photoshop, Pixelmator), Video Editors (DaVinci, Premiere, Final Cut Pro), Audio Editors (Audacity, Logic Pro).

• Databases: Columnar compression, delta encoding.
• Network Traffic: HTTP compression (Gzip, Brotli), real-time (Opus).
• Medical Imaging (DICOM): Lossless (JPEG-LS, RLE) or visually lossless (JPEG 2000).
• Genomics Data (FASTQ, CRAM): Specialized algorithms.

• AI/Neural Network-Based Compression: Promising for images/video/audio, but often computationally expensive.
• Perceptual Video Coding (VVC): Latest MPEG standard, ~30-50% improvement over HEVC.
• Specialized Hardware Acceleration: For newer codecs (AV1, VVC).
• Focus on Semantic Compression: Compressing based on data *meaning*.
• Compression for Privacy: Emerging techniques.

Pre-processing Examples:

• Normalization, noise removal (for lossy), data transformation (like BWT), reordering data fields.

Post-processing Examples:

• Deblocking filters (common in video codecs), deringing filters, error concealment.