How GZIP Compression Implementation Works: Compression Explained

1. Introduction and Core Concepts

gzip compression implementation is the practical realization of the GZIP file format defined in RFC 1952, which combines the DEFLATE compressed data format (RFC 1951) with a lightweight container for metadata, integrity checking, and stream framing. While many developers interact with gzip as a black-box command-line tool or a single function call, understanding its implementation reveals a sophisticated interplay of two classic compression techniques: LZ77 dictionary coding and Huffman entropy coding. Together, they form a lossless compression system that remains one of the most ubiquitous standards on the internet more than three decades after its introduction.

At its core, gzip is not a single algorithm but a format specification. The actual compression work is performed by DEFLATE, which itself is a hybrid of LZ77 and Huffman coding. LZ77 exploits repeated substrings by replacing them with back-references, while Huffman coding exploits skewed symbol frequencies by assigning shorter bit codes to more common bytes. The gzip wrapper then adds a 10-byte header containing a magic number, compression method, flags, modification time, operating system identifier, and optional fields such as original filename and comment, followed by the DEFLATE stream and an 8-byte trailer with a CRC32 checksum and the original uncompressed size modulo 2^32.

Understanding gzip compression implementation matters because it underpins critical infrastructure. Every HTTP response with Content-Encoding: gzip, every .tar.gz software distribution, every compressed log file rotated by a Linux server, and countless data pipelines rely on interoperable gzip behavior. For engineers, implementing or tuning gzip correctly affects bandwidth costs, latency, storage efficiency, and CPU utilization. A naive implementation can waste memory, produce incompatible streams, or become vulnerable to decompression bombs, while an optimized implementation can achieve 60-90% size reduction on text-heavy payloads with minimal overhead.

Why GZIP Endures

Despite newer algorithms like Zstandard and Brotli offering better ratios or speed, gzip persists due to its universal support, deterministic output, patent-free status, and excellent balance of compression ratio and decompression speed. Its decompression is extremely fast and requires little memory, making it ideal for clients with constrained resources such as browsers, embedded devices, and mobile apps. The format's streaming nature also allows compression and decompression to begin before the entire input is available, which is essential for network protocols.

Key terminology for any implementation includes: literals (raw bytes that could not be compressed), length-distance pairs (LZ77 back-references), Huffman trees (prefix code tables), blocks (independent DEFLATE units with their own header), and the sliding window (a 32KB history buffer used by LZ77). Mastering these concepts is prerequisite to writing correct and performant gzip code.

2. How It Works

Gzip compression implementation operates as a pipeline with three major stages: LZ77 parsing, Huffman modeling, and bitstream framing. Input bytes first enter the LZ77 stage, which maintains a 32KB sliding window of recently seen data. As each new position is examined, the compressor searches the window for the longest previous match. If a match of at least 3 bytes is found, it is emitted as a length-distance pair; otherwise, the literal byte is emitted. This step transforms the original byte stream into a sequence of symbols consisting of 0-255 for literals, 256 for end-of-block, and 257-285 for length codes combined with distance codes 0-29.

The second stage applies Huffman coding to this symbol sequence. DEFLATE supports three block types: stored (no compression), fixed Huffman (using a predefined code table defined by the RFC), and dynamic Huffman (where the compressor builds custom Huffman trees based on actual symbol frequencies and transmits the trees in the block header). Most gzip implementations use dynamic Huffman for optimal compression, though they fall back to stored or fixed blocks when the data is incompressible or very small. Two Huffman trees are constructed per dynamic block: one for literal/length symbols and one for distance symbols. The trees themselves are compressed using a third Huffman tree for code lengths, with run-length encoding for efficiency.

Finally, the Huffman-encoded symbols are packed into a bitstream where bits are written in LSB-first order, a distinctive feature of DEFLATE that often confuses new implementers. The gzip container then wraps this bitstream. The header validation, optional extra fields, and trailer generation are straightforward but must be byte-exact to ensure interoperability. During decompression, the process reverses: the gzip header is parsed, the DEFLATE bitstream is decoded using the transmitted Huffman trees, length-distance pairs are resolved by copying from the sliding window, and the CRC32 is verified against the trailer.

The DEFLATE Block Structure

Each DEFLATE block begins with a 3-bit header: 1 bit indicating whether it is the final block, and 2 bits indicating the block type (00 = stored, 01 = fixed Huffman, 10 = dynamic Huffman, 11 = reserved/error). Stored blocks are byte-aligned and contain a 16-bit length and its one's complement, followed by raw bytes. Fixed and dynamic blocks contain Huffman-encoded data until the end-of-block symbol (256). This block structure allows the compressor to adapt its strategy per chunk, for example using stored blocks for already-compressed JPEG data and dynamic blocks for compressible HTML.

Sliding Window and Hash Chains

Efficient LZ77 matching is the performance-critical part of gzip. A naive O(n^2) search of the 32KB window is infeasible. Production implementations use a hash table keyed by 3-byte sequences to quickly locate candidate matches, with hash chains linking positions that share the same hash. Parameters like hash bits, chain length limit, and lazy evaluation (checking if a better match exists at the next position before emitting the current one) control the trade-off between speed and ratio. This is where compression levels 1-9 diverge: level 1 uses a small hash table and no lazy matching for speed, while level 9 uses exhaustive search and optimal parsing.

3. Implementation

Implementing gzip correctly in Python requires understanding both the high-level gzip module and the low-level zlib DEFLATE engine it wraps. The standard library handles header/trailer generation and CRC calculation automatically, but custom implementations must manage these details manually when streaming or when building compatible tools.

The following example demonstrates idiomatic, production-ready gzip compression and decompression using the standard library, with explicit handling of compression levels, modification time, and streaming interfaces.

import gzip
import io
import os
import time

def compress_bytes(data: bytes, level: int = 6, filename: str = "") -> bytes:
    """Compress bytes to gzip format with configurable level and metadata."""
    # level 1 = fastest, 9 = best ratio, 6 = default trade-off
    # mtime is stored in header; use fixed value for deterministic output
    buf = io.BytesIO()
    mtime = int(time.time())
    with gzip.GzipFile(fileobj=buf, mode='wb', compresslevel=level, mtime=mtime, filename=filename) as gz:
        gz.write(data)
    return buf.getvalue()

def decompress_bytes(gz_data: bytes) -> bytes:
    """Decompress gzip bytes and verify CRC32 and ISIZE trailer."""
    with gzip.GzipFile(fileobj=io.BytesIO(gz_data), mode='rb') as gz:
        # .read() automatically validates CRC32 and size
        return gz.read()

# Example usage
original = b"ABABABABABABABAB " * 1000
compressed = compress_bytes(original, level=6, filename="example.txt")
decompressed = decompress_bytes(compressed)
assert decompressed == original
print(f"Original: {len(original)} bytes, Compressed: {len(compressed)} bytes")
print(f"Ratio: {len(compressed) / len(original):.2%}")

For cases where you need to understand or reimplement the DEFLATE layer itself, the next example shows a simplified LZ77 tokenizer. This is educational code, not a replacement for zlib, but it illustrates the core dictionary search that every gzip implementation performs. Note how hash-based lookup avoids brute-force scanning.

from collections import defaultdict

WINDOW_SIZE = 32768
MIN_MATCH = 3
MAX_MATCH = 258

def lz77_tokenize(data: bytes):
    """Simplified LZ77 tokenizer yielding (literal) or (distance, length) tokens."""
    n = len(data)
    # hash -> list of positions with that 3-byte hash
    hash_table = defaultdict(list)
    pos = 0
    tokens = []

    while pos < n:
        best_len = 0
        best_dist = 0

        if pos + MIN_MATCH <= n:
            # Compute hash of next 3 bytes
            h = hash(data[pos:pos+3]) & 0xFFFF
            candidates = hash_table[h]

            # Search recent candidates within window
            for cand in reversed(candidates[-64:]):  # limit chain length
                if pos - cand > WINDOW_SIZE:
                    continue
                # Extend match
                length = 0
                while (pos + length < n and 
                       cand + length < pos and 
                       data[cand + length] == data[pos + length] and 
                       length < MAX_MATCH):
                    length += 1
                if length >= MIN_MATCH and length > best_len:
                    best_len = length
                    best_dist = pos - cand
                    if length == MAX_MATCH:
                        break

            # Update hash chain
            hash_table[h].append(pos)
            # Prune old entries to bound memory
            if len(hash_table[h]) > 256:
                hash_table[h] = hash_table[h][-128:]

        if best_len >= MIN_MATCH:
            tokens.append(('match', best_dist, best_len))
            # Add intermediate positions to hash table for future matches
            for k in range(1, best_len):
                if pos + k + 3 <= n:
                    hk = hash(data[pos+k:pos+k+3]) & 0xFFFF
                    hash_table[hk].append(pos + k)
            pos += best_len
        else:
            tokens.append(('lit', data[pos]))
            pos += 1

    return tokens

tokens = lz77_tokenize(b"abcabcabcabc xyz xyz xyz")
print(tokens[:10])

After LZ77 tokenization, Huffman coding assigns variable-length codes. The following snippet builds canonical Huffman codes from symbol frequencies, which is exactly what a dynamic DEFLATE block does. Canonical Huffman codes allow the tree to be transmitted compactly as code lengths only.

import heapq
from collections import Counter

def build_huffman_lengths(frequencies: dict) -> dict:
    """Build Huffman code lengths from symbol frequencies using a heap."""
    # frequencies: symbol -> count
    heap = [[freq, [sym, ""]] for sym, freq in frequencies.items()]
    heapq.heapify(heap)
    if len(heap) == 1:
        # Special case: single symbol needs 1 bit
        sym = heap[0][1][0][0]
        return {sym: 1}
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    # Extract lengths
    huff = sorted(heap[0][1:], key=lambda p: (len(p[1]), p[0]))
    return {sym: len(code) for sym, code in huff}

def canonical_codes(lengths: dict) -> dict:
    """Convert code lengths to canonical Huffman codes (integer, bit length)."""
    # Sort by length then symbol value
    sorted_syms = sorted(lengths.items(), key=lambda x: (x[1], x[0]))
    code = 0
    prev_len = 0
    result = {}
    for sym, length in sorted_syms:
        code <<= (length - prev_len)
        result[sym] = (code, length)
        code += 1
        prev_len = length
    return result

freqs = Counter([1,1,1,1,2,2,3])
lengths = build_huffman_lengths(freqs)
codes = canonical_codes(lengths)
print(lengths)
print(codes)

For streaming scenarios such as web servers, you should avoid buffering the entire payload. The next example shows incremental gzip compression using zlib.compressobj with wbits=31 to produce gzip framing, which is essential for large files and network sockets.

import zlib

def gzip_stream_compress(chunks, level: int = 6):
    """Incrementally compress an iterable of byte chunks to gzip format."""
    # wbits=31 means gzip header+trailer (15 + 16)
    comp = zlib.compressobj(level=level, method=zlib.DEFLATED, wbits=31, memLevel=8, strategy=zlib.Z_DEFAULT_STRATEGY)
    for chunk in chunks:
        if len(chunk) == 0:
            continue
        out = comp.compress(chunk)
        if len(out) > 0:
            yield out
    # Flush with Z_FINISH to write trailer
    tail = comp.flush(zlib.Z_FINISH)
    if len(tail) > 0:
        yield tail

def gzip_stream_decompress(gz_chunks):
    """Incrementally decompress gzip chunks."""
    decomp = zlib.decompressobj(wbits=31)
    for chunk in gz_chunks:
        if len(chunk) == 0:
            continue
        out = decomp.decompress(chunk)
        if len(out) > 0:
            yield out
    # Verify trailer
    yield decomp.flush()

# Simulate streaming a large file
def file_chunks(path, size=8192):
    with open(path, 'rb') as f:
        while True:
            c = f.read(size)
            if not c:
                break
            yield c

4. Step-by-Step Example

To make the pipeline concrete, consider compressing the ASCII string ABABABAABABABA (15 bytes). This string is highly repetitive and ideal for LZ77. We will walk through how a gzip implementation processes it block by block, including tokenization, Huffman assignment, and bit packing.

Step 1: LZ77 parsing with a 32KB window initially empty. At position 0, bytes A and B have no prior matches, so they are emitted as literals: A, B. At position 2, the compressor sees A B A ... and finds a match at distance 2 with length 5 (ABABA). Instead of emitting five literals, it emits a length-distance pair (5, 2). The parser then advances to position 7, where it sees A A B .... The longest match is A alone, which is too short, so it emits literal A. At position 8, it finds B A B A B A matching the prefix at distance 7 with length 6. The final token sequence is: [lit A, lit B, (2,5), lit A, (7,6)], reducing 15 bytes to 5 symbols.

Step 2: Frequency analysis for Huffman coding. In this block, literal A appears 3 times counting the isolated literal, literal B appears 1 time, and length codes for 5 and 6 each appear once. Distance codes 2 and 7 each appear once. A dynamic Huffman tree would assign the shortest codes to the most frequent symbols. For example, A might get 0 (1 bit), B gets 10 (2 bits), length 5 gets 110, length 6 gets 1110, and the two distance codes share the remaining space. The end-of-block symbol 256 is also assigned a code. The compressor then writes the code lengths into the block header using the code-length alphabet, which itself is Huffman-coded.

Step 3: Bitstream packing and gzip framing. The block header is written as 1 bit final=1, 2 bits type=10 (dynamic), followed by the encoded Huffman trees. Then each token is written using its Huffman code: literals directly, and matches as a length code plus extra bits plus a distance code plus extra bits. For instance, length 5 maps to code 257 with 0 extra bits, and distance 2 maps to code 1 with 0 extra bits. Bits are packed LSB-first into bytes. After the block, the gzip trailer is appended: CRC32 of the original 15 bytes (e.g., 0x8B9E1234) and ISIZE = 15. The total compressed size might be 12-14 bytes, barely smaller for this tiny example, but the ratio improves dramatically with larger inputs where Huffman overhead is amortized.

Tracing Decompression

Decompression reverses the steps exactly. The gzip header is validated (magic bytes 1F 8B), the DEFLATE block is decoded by reading the Huffman trees, then each symbol is decoded: if it is < 256, output the literal byte; if it is > 256, decode length and distance and copy length bytes from output_position - distance in the sliding window. This copy may overlap, which is crucial for correctly expanding runs like ABABA where the source and destination overlap. Finally, the CRC32 of the decompressed output is computed and compared to the trailer; any mismatch indicates corruption, and the ISIZE check detects truncation.

5. Complexity Analysis

The performance of gzip compression implementation is dominated by the LZ77 search and Huffman tree construction. Understanding the asymptotic behavior helps in selecting compression levels and predicting resource usage for large inputs.

Let n be the input size in bytes, w = 32768 the window size, and k the average hash chain length examined per position. Compression time is typically O(n * k) for the LZ77 phase, where k is bounded by a constant (e.g., 32 for fast levels, 4096 for level 9). Huffman construction is O(m log m) where m is the alphabet size (286 literal/length symbols + 30 distance symbols), which is effectively O(1) per block since m is fixed. Bit packing is O(n). Decompression is O(n) in all cases because each output byte is produced once via either literal emission or window copy, and Huffman decoding uses table lookups.

Space complexity is O(w) for the sliding window and hash table during compression, plus O(m) for Huffman trees. Decompression requires only O(w) for the window. In practice, memory usage is controlled by the memLevel parameter (1-9) which scales the hash table size; level 8 uses about 256KB, level 9 uses more for larger hash chains.

Best-case compression occurs with highly repetitive data where long matches are found quickly and Huffman trees are small. Worst-case occurs with random data where no matches exist and the compressor still spends time searching hash chains, plus the output may expand slightly due to block headers and stored-block overhead (5 bytes per 64KB). This is why gzip implementations detect incompressible data and switch to stored blocks to bound expansion to < 0.1%.

Impact of Block Size and Level

Gzip does not use a fixed block size; it emits a new dynamic block when the Huffman trees become stale or when the internal buffer (typically 16KB-64KB) fills. Smaller blocks adapt faster to changing statistics but incur tree overhead. Higher compression levels increase k and enable lazy matching and optimal parsing, improving ratio by 5-15% at the cost of 3-10x slower compression. Decompression speed is largely unaffected by level, which is why gzip is often chosen when decompression speed matters more than compression speed, such as in content delivery.

6. Variations and Optimizations

Production gzip implementations include numerous optimizations beyond the textbook algorithm. One major optimization is lazy evaluation: instead of immediately emitting a match at position i, the compressor checks if a longer match exists at i+1. If so, it emits the literal at i and uses the better match at i+1. This one-byte lookahead improves ratio by 1-3% with minimal cost and is enabled at levels 4 and above.

Another optimization is optimal parsing using dynamic programming or greedy parsing with heuristics. The classic DEFLATE uses greedy parsing, but advanced encoders like Zopfli and libdeflate use optimal parsing to choose the sequence of literals and matches that minimizes total Huffman-coded size, not just the number of matches. This can improve ratio by 3-8% but is significantly slower, making it suitable for static assets that are compressed once and served many times.

Hash function and table design also vary. The original gzip uses a simple 3-byte hash with 2^15 entries, while modern ports use 2^16 or larger tables, rolling hashes, and separate tables for different match lengths. Some implementations use a binary tree or suffix array for exhaustive search at level 9, while others use a hash chain with a configurable max chain length to bound worst-case time. Memory level tuning, SIMD-accelerated CRC32 (using PCLMULQDQ or ARM CRC instructions), and fast Huffman table generation via counting sort further accelerate throughput.

Strategies and Presets

zlib, the reference engine behind gzip, exposes strategy parameters that alter LZ77 behavior: Z_DEFAULT_STRATEGY for general data, Z_FILTERED for filtered data with small values, Z_HUFFMAN_ONLY to disable LZ77 entirely (useful for already compressed or encrypted data), and Z_RLE for run-length encoding. Choosing the correct strategy can prevent wasted CPU on incompressible data. Additionally, dictionary presetting allows priming the sliding window with common substrings, such as HTTP headers, to improve compression of small messages where the window would otherwise be empty.

Parallel and Hardware Acceleration

Standard gzip is inherently sequential due to the sliding window dependency, but large files can be compressed in parallel using independent blocks or the BGZF (Blocked GNU Zip Format) variant used in bioinformatics, which concatenates multiple gzip members each with its own header and trailer. Modern CPUs also provide hardware acceleration: Intel's QAT and ARM's NEON can accelerate LZ77 and Huffman coding, while specialized libraries like Intel's ISA-L achieve multi-GB/s throughput. For Python, the fastest path is to delegate to the C-implemented zlib or use isal or zstandard bindings when available.

7. Real-World Applications

Gzip compression implementation is embedded in nearly every layer of modern computing. Its most visible role is in HTTP content encoding, where servers compress HTML, CSS, JavaScript, and JSON on the fly. Nginx, Apache, and CDNs like Cloudflare negotiate Accept-Encoding: gzip and compress responses at level 4-6 to balance CPU and bandwidth. Studies show gzip reduces text payloads by 70-85%, directly improving Largest Contentful Paint and Time to First Byte metrics. Browsers decompress streams incrementally, allowing rendering to begin before the full response arrives.

Beyond the web, gzip is the standard for log rotation and archival. Tools like logrotate, syslog, and cloud logging agents compress daily logs with gzip, achieving 10:1 reduction on repetitive log lines. Software distribution relies on .tar.gz and .tgz archives; package managers such as pip, apt, and npm distribute gzip-compressed tarballs. Databases including PostgreSQL (TOAST), MySQL (compressed tables), and time-series stores use gzip for cold storage and backups. Even the PNG image format uses DEFLATE internally, making gzip-related code relevant to image processing pipelines.

Networking protocols also leverage gzip framing for extensibility. WebSocket per-message compression (permessage-deflate), HTTP/2 and gRPC metadata compression, and many RPC frameworks support gzip as an optional transform. In data engineering, Apache Kafka, Spark, and Airflow often store intermediate data as gzip files because the format is splittable when concatenated (multiple gzip members) and universally readable. The key advantage in all these contexts is not just ratio but interoperability: any language or tool can decompress gzip without additional dependencies.

When Not to Use GZIP

Gzip is not ideal for already compressed data such as JPEG, MP4, or encrypted payloads, where it adds CPU overhead and may increase size. For such data, use stored blocks or skip compression entirely. For latency-sensitive, high-throughput systems, faster algorithms like LZ4 or Zstandard may be preferable, and for maximum ratio on static text, Brotli often outperforms gzip by 15-20% due to its larger window and static dictionary.

8. Comparison with Alternatives

Choosing a compression algorithm requires weighing ratio, speed, memory, and compatibility. Gzip sits in the middle of the spectrum: moderate ratio, fast decompression, and universal support. Newer algorithms optimize different points in this design space.

Bzip2 achieves better ratio than gzip on text by using the Burrows-Wheeler transform followed by move-to-front and Huffman coding, but it is much slower and not streamable in the same way. LZ4 sacrifices ratio for extreme speed, making it ideal for in-memory caching, database pages, and real-time replication where CPU is the bottleneck. Zstandard is often considered the successor to gzip: it offers a wide level range that can mimic both LZ4-like speed and bzip2-like ratio, with a larger window and finite state entropy coding. Brotli, developed by Google, uses a 120KB static dictionary of common web strings and a larger window, giving it a 15-25% ratio advantage over gzip for HTML and JavaScript, which is why it is now preferred for static assets served over HTTPS.

For Python developers, the practical guidance is: use gzip when compatibility and portability are paramount, use Zstandard when you control both ends and want better performance, use LZ4 for ephemeral or latency-critical data, and use Brotli for precompressed static web content. All four are available via pip (zstandard, lz4, brotli), and the choice can be made per data type rather than globally.

9. Common Mistakes and Best Practices

Even experienced engineers introduce subtle bugs when implementing gzip compression. One frequent mistake is forgetting that gzip is a byte-oriented format and attempting to compress strings without explicit encoding. Passing a Python str directly to gzip.compress raises a TypeError; always encode to utf-8 or the appropriate charset first, and decode after decompression. Another common error is not handling concatenated gzip members: the gzip RFC allows multiple members concatenated together, and gzip.GzipFile correctly decompresses them sequentially, but naive zlib.decompress with wbits=31 may stop after the first member unless you loop until unused_data is empty.

Performance pitfalls include using Python-level loops for LZ77 or Huffman coding instead of delegating to the C zlib engine, which can be 100x slower. When compressing small payloads (< 1KB), the gzip header (10 bytes) and trailer (8 bytes) plus Huffman tree overhead can make the compressed output larger than the input. In HTTP contexts, avoid compressing responses smaller than ~860 bytes or those with Cache-Control: no-transform. Also, never compress already compressed or encrypted data without checking the ratio; blindly gzipping JPEGs or TLS payloads wastes CPU and may expand the data.

Security considerations are critical. Gzip decompression bombs (e.g., 42.zip) exploit the high compression ratio to exhaust memory or disk. Always enforce limits on decompressed size, using streaming decompression with a byte counter and aborting if the output exceeds an expected threshold. Validate the CRC32 and ISIZE trailer, but do not rely on ISIZE alone since it is modulo 2^32. When handling untrusted gzip files, use gzip.open with a bounded read and monitor resource usage.

Best Practices Checklist

• Use gzip.open or zlib.compressobj(wbits=31) for streaming; avoid loading multi-GB files into memory.
• Select compression level deliberately: level 1 for real-time, 6 for default, 9 for archival. Benchmark with representative data.
• Set mtime=0 or a fixed value for deterministic builds to avoid cache invalidation due to timestamp changes.
• Enable filename and comment header fields only when needed; they increase size and may leak metadata.
• Prefer chunked transfer with gzip streaming over buffering entire responses in web servers.
• Test edge cases: empty input, single byte, incompressible random data, concatenated members, and truncated files.
• Monitor compression ratio in production; if ratio < 5%, consider disabling gzip for that content type.

Finally, ensure proper resource cleanup. Always close GzipFile objects to flush the trailer; using a with statement guarantees this. When implementing custom framing, write the header, then DEFLATE data, then CRC32 and ISIZE in little-endian order. Interoperability tests against gunzip and multiple language implementations help catch endianness or bit-ordering bugs early.

10. Interview Questions

Interviewers frequently probe gzip implementation knowledge to assess understanding of compression fundamentals, systems design, and practical trade-offs. The following questions cover theory, implementation details, and applied problem solving.

Q1: Why does gzip combine LZ77 and Huffman coding instead of using just one?

LZ77 alone exploits repetition but leaves redundancy in the distribution of literals and length-distance codes. For example, the letter e may appear far more often than z, but LZ77 would encode both as single bytes. Huffman coding compresses this skewed distribution by assigning shorter codes to frequent symbols. Conversely, Huffman alone cannot exploit long repeated substrings efficiently; encoding ABABAB... byte by byte would still be large, while LZ77 replaces it with a single back-reference. The hybrid achieves better ratio than either alone, which is why DEFLATE and modern compressors like Zstandard and Brotli all use a dictionary + entropy coding pipeline.

Q2: What is the purpose of the 32KB sliding window, and what happens if you increase it?

The 32KB window limits the maximum distance of a back-reference to 32768 bytes, which bounds memory usage and allows distance codes to be encoded in 15 bits. It also ensures decompression can be done with a small, fixed buffer. Increasing the window allows finding longer-distance matches, improving ratio on large files with distant repetitions (e.g., log files or genomic data), which is why Zstandard and Brotli use windows up to megabytes. However, larger windows increase memory, slow down hash table searches, and break gzip compatibility, since the format fixes the window size in the DEFLATE specification.

Q3: How would you implement streaming gzip decompression with a decompression bomb protection?

Use incremental decompression via zlib.decompressobj(wbits=31) and enforce a limit on total output bytes. Pseudocode: create a decompressor, iterate over input chunks, call decompress(chunk), accumulate output length, and abort if it exceeds max_output (e.g., 10x input size or an absolute cap). Also limit the number of output chunks and total time. After the stream ends, call flush() and verify that eof is True and unused_data is handled. This prevents a small 10KB bomb from expanding to gigabytes and exhausting memory. Always process untrusted gzip in a sandboxed or resource-limited environment.

Q4: Explain the difference between fixed and dynamic Huffman blocks in DEFLATE.

Fixed Huffman blocks use a predefined code table specified by RFC 1951: literals 0-143 use 8 bits, 144-255 use 9 bits, 256-279 use 7 bits, and 280-287 use 8 bits; distance codes use 5 bits. No tree is transmitted, so overhead is zero, making fixed blocks good for small or incompressible data. Dynamic blocks build custom trees based on actual frequencies, transmit the code lengths (compressed with run-length encoding), and then use those trees for the block's data. Dynamic blocks achieve better ratio when frequencies are skewed but incur 50-100 bytes of tree overhead. A good compressor estimates the size for each block type and chooses the smallest.

Q5: When should you choose gzip over Zstandard or Brotli for a web service?

Choose gzip when universal compatibility is required, such as for public APIs, legacy clients, or when serving over HTTP without prior content negotiation guarantees. Gzip decompression is supported by every browser, curl, and HTTP library without extra dependencies. Prefer Zstandard when you control both client and server (e.g., microservices, data pipelines) and need higher throughput or better ratio with tunable levels. Prefer Brotli for static assets precompressed at build time and served over HTTPS, where its static dictionary yields 15-20% smaller files. In practice, many CDNs negotiate all three: serve Brotli if Accept-Encoding includes br, else Zstd if it includes zstd, else gzip as the fallback.