How data compression algorithms work

The Interview Question

Interviewer: "You are building a logging pipeline that ingests 50 GB of log data per hour. Your team wants to compress the logs before writing them to object storage to reduce costs. Walk me through how compression algorithms work, what tradeoffs exist between compression ratio and speed, and which algorithm you would pick for this use case."

This question tests whether you understand compression beyond "make file smaller." The interviewer wants to hear about the fundamental techniques (Huffman coding, dictionary matching), how they combine in real algorithms (DEFLATE, Zstd), and the engineering tradeoffs between CPU cost, compression ratio, and decompression speed. Candidates who only say "use gzip" without explaining why miss the depth this question targets.

What to Clarify Before Answering

You: "Before I recommend an algorithm, let me understand the constraints..."

• "Is this hot path (compressing in real-time as logs arrive) or cold path (batch compression after landing)? That affects whether I optimize for compression speed or ratio."
• "Do we need random access into compressed files, or is sequential decompression acceptable?"
• "What is the downstream read pattern? Are logs queried frequently (favor fast decompression) or archived for compliance (favor high ratio)?"
• "Is the data mostly text (JSON logs, CSV) or binary (protobuf, images)?"
• "Are there repeated patterns across log entries? That determines whether dictionary-based approaches give outsized wins."

Why this matters: Compressing 50 GB/hour of structured JSON logs with a pre-trained dictionary (Zstd with a shared dictionary) gives 10-15x compression ratios. Compressing random binary data gives maybe 1.1x. The algorithm choice depends entirely on the data characteristics and access patterns.

The 30-Second Answer

Data compression removes redundancy from data using two fundamental techniques: statistical coding (Huffman/arithmetic coding) assigns shorter bit sequences to frequent symbols, and dictionary matching (LZ77/LZ78) replaces repeated byte sequences with back-references to earlier occurrences. The DEFLATE algorithm (used by gzip and zip) combines both: LZ77 finds repeated sequences, then Huffman coding compresses the resulting stream of literals and back-references. Modern algorithms improve on DEFLATE's 30-year-old design. Zstd adds finite state entropy coding and pre-trained dictionaries for 3-5x faster compression at similar ratios. Brotli uses a large built-in dictionary of common web content for better HTTP compression. LZ4 sacrifices ratio for extreme speed (4 GB/s decompression). The right choice depends on your bottleneck: CPU-bound pipelines want LZ4/Snappy, bandwidth-bound transfers want Brotli/Zstd, and archival storage wants Zstd at high compression levels.

The Architecture Overview

Compression is fundamentally about finding and removing redundancy. There are two kinds of redundancy in data: statistical redundancy (some bytes appear more often than others) and sequential redundancy (the same byte patterns repeat). The best algorithms exploit both.

I find it helpful to think of compression as translation. You are translating data from a verbose language (8-bit ASCII where every character costs the same) into a compact language where common words are short and rare words are long.

Huffman Coding: Frequency-Based Compression

Huffman coding is the foundation of statistical compression. The idea is simple: if the letter "A" appears 500 times and the letter "Z" appears twice, why should both cost 8 bits? Assign "A" a 2-bit code and "Z" a 12-bit code. On average, the encoded data is much smaller.

Building the Huffman tree

The algorithm works bottom-up:

1. Count the frequency of every symbol in the input
2. Create a leaf node for each symbol
3. Repeat: take the two nodes with the lowest frequency, merge them into a parent node whose frequency is the sum
4. The root of the tree is reached when only one node remains
5. Assign codes by traversing the tree: left branch = 0, right branch = 1

The result is a prefix-free code, meaning no code is a prefix of another code. This is critical for unambiguous decoding. When the decoder sees "0", it immediately knows that is "A" without needing to look ahead. If it sees "1", it knows more bits follow.

Compression ratio analysis

For the "ABRACADABRA" example: the original is 11 characters at 8 bits each (88 bits). The Huffman-encoded version is 23 bits. That is a 74% reduction, but only because the frequency distribution is highly skewed.

If every symbol appeared with equal frequency, Huffman coding would produce codes of nearly equal length, and the compression ratio would approach 1:1 (no savings). This is a fundamental limit: Huffman coding only works well when the frequency distribution is uneven.

Practical limitations

Huffman coding has a hard floor: each symbol must be assigned at least 1 bit. If a symbol appears 99% of the time, the optimal code length is about 0.014 bits per symbol (from information theory), but Huffman assigns it 1 bit. For highly skewed distributions, arithmetic coding or ANS (Asymmetric Numeral Systems) can get closer to the theoretical limit by encoding multiple symbols together into a single fractional-bit stream.

LZ77: Sliding Window Dictionary Matching

LZ77 (Lempel-Ziv 1977) takes a completely different approach from Huffman coding. Instead of compressing individual symbols, it finds repeated sequences of bytes and replaces them with back-references.

The algorithm maintains a sliding window over the input data. The window has two parts: the search buffer (data already processed, typically 32KB) and the look-ahead buffer (data about to be processed, typically 258 bytes). At each step, the algorithm looks for the longest match between the look-ahead buffer and anything in the search buffer.

How matching works

Consider compressing "ABCABCABC":

1. Process "A": no match in search buffer (empty). Output literal "A".
2. Process "B": no match. Output literal "B".
3. Process "C": no match. Output literal "C".
4. Process "A": match found at offset 3, length 3 ("ABC" matches). Output back-reference (3, 3).
5. Process position 7: match found at offset 3, length 3 ("ABC" again). Output back-reference (3, 3).

Result: A B C (3,3) (3,3) instead of A B C A B C A B C. The back-references are much shorter than the repeated data.

The tradeoff: search time

Finding the longest match in the search buffer is expensive. A naive implementation checks every position, giving O(n * w) complexity where w is the window size. Real implementations use hash chains or suffix trees to find matches quickly.

gzip uses hash chains: it hashes 3-byte sequences and chains positions with the same hash. When looking for a match, it only checks positions on the hash chain, dramatically reducing the search space. The compression level parameter (1-9 in gzip) controls how many chain entries to check before giving up. Level 1 checks very few (fast but mediocre compression), level 9 checks many (slow but best compression).

DEFLATE: The Algorithm Behind gzip and zip

DEFLATE combines LZ77 and Huffman coding into a single pipeline. It was invented by Phil Katz in 1993 and is the core of gzip, zip, zlib, and PNG compression. Almost every compressed file you have ever seen uses DEFLATE.

The two-pass pipeline

DEFLATE processes data in blocks (up to 64KB each). For each block:

Pass 1 (LZ77): Scan the input for repeated sequences. Replace matches with (distance, length) pairs. Sequences shorter than 3 bytes are not worth replacing (the back-reference would be larger than the literal).

Pass 2 (Huffman): Take the stream of literals and back-references from pass 1. Build two Huffman trees: one for the literal/length alphabet (256 byte values + 29 length codes) and one for the distance alphabet (30 distance codes). Encode everything using these trees.

The Huffman trees themselves are included in the compressed block so the decoder can reconstruct them. DEFLATE supports three block types:

• Type 0: No compression (stored as-is, used for already-compressed data)
• Type 1: Fixed Huffman codes (predefined, no tree overhead, adequate for small blocks)
• Type 2: Dynamic Huffman codes (custom trees optimized for this block, best for large blocks)

Why DEFLATE dominated for 30 years

DEFLATE hit a sweet spot in 1993: reasonable compression ratio (60-70% for text), fast enough for real-time use, and simple enough to implement correctly. The zlib library made it trivially accessible. HTTP adopted gzip (which wraps DEFLATE with a header and checksum), and it became the universal compression format for the web.

The downside: DEFLATE's 32KB sliding window limits compression of data with long-range patterns. Its compression ratio has been surpassed by every modern algorithm. But its ubiquity means it is still the default choice when compatibility matters.

Modern Algorithms: Zstd, Brotli, LZ4, and Snappy

The last decade brought a new generation of compression algorithms that significantly improve on DEFLATE's tradeoffs.

Zstd (Zstandard)

Developed by Yann Collet at Facebook (2016), Zstd is the best general-purpose compression algorithm available today. It achieves compression ratios competitive with zlib while being 3-5x faster at compression and 2x faster at decompression.

Key innovations:

• Finite State Entropy (FSE): An entropy coder based on ANS that is faster than Huffman while achieving better compression for skewed distributions
• Match finder optimization: Uses a combination of hash tables and binary trees, adaptively switching based on compression level
• Pre-trained dictionaries: For small payloads (< 1KB), Zstd can train a dictionary on representative data, dramatically improving compression of similar payloads. This is why Zstd is excellent for compressing small JSON API responses or log entries that share structure

Brotli

Developed by Google (2015), Brotli is optimized for HTTP content compression. It achieves 15-25% smaller output than gzip for web content.

Key innovations:

• Built-in static dictionary: 120KB of common HTML, CSS, JavaScript, and English words. The compressor can reference this dictionary without sending it, giving a free head start on web content
• Context modeling: Uses the previous two bytes to predict the next byte, improving entropy coding accuracy
• Large window: Up to 16MB sliding window (vs DEFLATE's 32KB), catching long-range repeats

The tradeoff: Brotli compression is slow (2-5x slower than gzip at equivalent ratios). It is best used for static content that is compressed once and served many times.

LZ4

Developed by Yann Collet (2011), LZ4 is the speed champion. It decompresses at 4+ GB/s on modern hardware, limited primarily by memory bandwidth.

LZ4 achieves this speed by using an extremely simple format: 4-byte literals header, raw literal bytes, 2-byte match offset, variable-length match length. No entropy coding. No complex parsing. The decompressor is a tight loop of memory copies.

The compression ratio is modest (typically 2:1 for text), but when your bottleneck is CPU, not storage, LZ4 is the correct choice. Databases (ClickHouse, RocksDB) and network protocols use LZ4 because decompression speed matters more than storage savings in their hot paths.

Snappy

Developed by Google (2011), Snappy is similar in philosophy to LZ4: prioritize speed over ratio. Google uses Snappy internally in Bigtable, MapReduce, and RPC compression that cannot wait for slow decompression.

Columnar Compression for Analytics Databases

Analytics databases (ClickHouse, Parquet, Delta Lake) use specialized compression techniques that exploit the structure of columnar data. Because columns store values of the same type and often with similar values, specialized encodings achieve dramatically better compression than general-purpose algorithms.

Run-Length Encoding (RLE)

If a column has many consecutive identical values, replace the runs with (value, count) pairs:

Input:  [USA, USA, USA, USA, USA, UK, UK, UK, France, France]
RLE:    [(USA, 5), (UK, 3), (France, 2)]

For sorted columns with low cardinality (country, status, category), RLE compresses 100:1 or better. This is why ClickHouse benefits enormously from sorting data by low-cardinality columns first.

Delta Encoding

For monotonically increasing values (timestamps, auto-increment IDs), store the difference between consecutive values:

Input:   [1000, 1001, 1003, 1004, 1008]
Deltas:  [1000, 1, 2, 1, 4]

The deltas are small numbers that compress extremely well with bit-packing (using 3 bits instead of 64 bits per value). Timestamp columns in time-series databases routinely achieve 20:1 compression with delta encoding alone.

Dictionary Encoding

For columns with repeated string values, build a dictionary mapping each unique value to a small integer:

Dictionary: {0: "error", 1: "warning", 2: "info", 3: "debug"}
Input:    ["error", "info", "info", "debug", "error", "info"]
Encoded:  [0, 2, 2, 3, 0, 2]

The encoded column uses 2-bit integers instead of variable-length strings. Parquet and ORC use dictionary encoding as the default for string columns, falling back to plain encoding only when the dictionary exceeds a size threshold (typically 40% of the page size).

What Happens When Things Break

Performance Characteristics

How This Compares to Alternatives

I reach for Zstd as my default compression algorithm in 2024+. It beats gzip at every compression level on both speed and ratio. I switch to LZ4 when decompression speed dominates (database pages, real-time analytics). I use Brotli only for static web assets where I compress once at build time and serve many times. I keep gzip only for backward compatibility with systems that do not support newer formats.

Interview Cheat Sheet

• When asked about compression basics: "Two fundamental techniques: statistical coding (Huffman) assigns short codes to frequent symbols, and dictionary matching (LZ77) replaces repeated sequences with back-references. DEFLATE combines both."
• When asked about Huffman coding: "Build a binary tree bottom-up from least to most frequent symbols. Each symbol gets a prefix-free variable-length code. More frequent symbols get shorter codes."
• When asked about LZ77: "A sliding window algorithm. It scans for matches between the current position and previously seen data. Matches are replaced with (distance, length) pairs. The window size determines how far back it can look."
• When asked about DEFLATE: "Two passes: LZ77 finds repeated sequences, then Huffman compresses the resulting stream. Used by gzip, zip, and zlib. 32KB window, invented in 1993, still the most widely deployed compression algorithm."
• When asked to choose an algorithm: "Zstd for general purpose (best speed-ratio tradeoff). LZ4 for speed-critical paths (databases, RPC). Brotli for static web content. gzip only for backward compatibility."
• When asked about columnar compression: "Columnar databases layer specialized encodings (RLE for sorted data, delta for timestamps, dictionary for strings) with general compression (LZ4/Zstd) on top. This achieves 10-50x compression on analytics workloads."
• When asked about the CPU vs bandwidth tradeoff: "If the network is the bottleneck, compress aggressively (Zstd level 19). If CPU is the bottleneck, use a fast compressor (LZ4). For most cases, Zstd default level hits the sweet spot."
• When asked about compressing small payloads: "Small payloads (< 1KB) compress poorly because there is not enough data for pattern detection. Zstd with a pre-trained dictionary solves this by sharing structure knowledge across payloads."

Test Your Understanding

Quick Recap

1. Lossless compression exploits two types of redundancy: statistical (unequal symbol frequencies) and sequential (repeated byte patterns).
2. Huffman coding assigns shorter bit codes to more frequent symbols, achieving compression when the frequency distribution is skewed.
3. LZ77 uses a sliding window to find repeated sequences and replaces them with compact back-references (offset, length pairs).
4. DEFLATE combines LZ77 and Huffman coding into a two-pass pipeline, and is the algorithm behind gzip, zip, and zlib.
5. Modern algorithms improve on DEFLATE: Zstd offers 3-5x faster compression at similar ratios, Brotli beats gzip for web content, and LZ4 decompresses at memory-bandwidth speeds.
6. Columnar databases layer specialized encodings (RLE, delta, dictionary) with general compression for 10-50x reduction on analytics workloads.
7. The right algorithm depends on your bottleneck: CPU-bound pipelines want LZ4, bandwidth-bound transfers want Zstd/Brotli, and archival storage wants Zstd at high compression levels.
8. Compression only works when data has redundancy. Random data, encrypted data, and already-compressed data will not compress further.

Related Concepts

• Content encoding in HTTP: Browsers and servers negotiate compression (gzip, Brotli) via Accept-Encoding and Content-Encoding headers, transparently compressing responses in transit.
• Write-ahead logs and storage engines: Databases like RocksDB and PostgreSQL compress WAL segments and data pages to reduce I/O, using the same LZ4/Zstd algorithms discussed here.
• Information theory (Shannon entropy): Shannon's entropy formula defines the theoretical minimum number of bits needed to encode data. No lossless compressor can beat this limit, and it explains why random data is incompressible.
• Network protocol optimization: gRPC uses message compression, Kafka uses batch compression with per-topic algorithm selection, and HTTP/2 uses HPACK header compression, all applying compression principles to reduce bandwidth.
• Storage cost optimization: In cloud environments, compression directly reduces storage costs (S3, GCS charge per GB). A 4:1 compression ratio on logs means 75% cost savings on object storage.