How 7-Zip Uses Deflate Compression for ZIP Files

When you create a standard ZIP archive in 7-Zip, the software relies primarily on the Deflate algorithm to shrink your data without losing any information. This article explains the mechanics of Deflate within 7-Zip, detailing how it pairs LZ77 dictionary compression with Huffman entropy encoding, packages the resulting bitstreams into standard ZIP containers, and leverages 7-Zip's proprietary optimizations to achieve superior compression ratios.

The Two-Stage Compression Pipeline

The Deflate algorithm is a hybrid system defined in RFC 1951. It achieves lossless compression by processing data through two distinct, consecutive phases: duplicate sequence elimination (LZ77) and bit-level symbol optimization (Huffman coding).

Phase 1: LZ77 Sliding Window Matching

The first phase eliminates duplicate data patterns:

  1. Sliding Window: 7-Zip maintains a 32 KB sliding window over the input byte stream. As data flows through, the algorithm looks backward within this 32 KB buffer to find matching sequences.
  2. Pointers vs. Literals: When a duplicate string of bytes (at least 3 bytes long) is found, 7-Zip replaces the duplicate with a reference pointer consisting of two values:
    • Distance: How far back in the 32 KB window the match starts.
    • Length: How many bytes match (up to 258 bytes).
  3. Literals: Any byte sequence that does not match previous data within the sliding window is retained as an uncompressed "literal" byte.

Phase 2: Huffman Coding

The stream of literals, match lengths, and match distances produced by the LZ77 stage is then processed to minimize the physical bits required to represent each value:

  1. Frequency Analysis: 7-Zip analyzes the frequency of every literal byte and length-distance code across discrete blocks of data.
  2. Tree Generation: It creates dynamic prefix trees (Huffman trees). Symbols that appear frequently are assigned short bit codes (e.g., 2 or 3 bits), while rare symbols are assigned longer bit codes.
  3. Block Types: 7-Zip packages the data into blocks. Depending on the input, it chooses the most efficient block mode:
    • Uncompressed Blocks: Used if compression would actually expand the data (e.g., already compressed media).
    • Fixed Huffman: Uses a predefined, standardized code tree defined by the Deflate specification.
    • Dynamic Huffman: Constructs and stores custom trees tailored specifically to the current data block, which yields the smallest file size for most data types.

7-Zip's Implementation and Optimizations

While standard ZIP tools rely on basic implementations of Deflate like zlib, 7-Zip uses a custom, highly optimized Deflate encoder written by Igor Pavlov.

  • Exhaustive Match Finding: When setting 7-Zip's compression level to "Maximum" or "Ultra," the encoder uses deeper search algorithms (such as hash chains and binary trees) to locate optimal matches rather than merely "greedy" first matches.
  • Optimal Parsing: Standard implementations often pick the first available match. 7-Zip evaluates whether taking a shorter match now allows for a significantly longer match on the next byte, leading to a smaller overall bit representation.
  • Pass Count Tuning: High compression presets in 7-Zip increase the number of optimization passes, allowing the algorithm to recalculate Huffman trees repeatedly to find the absolute minimum bit representation for a block.

Writing to the ZIP Structure

Once the Deflate stream is finalized, 7-Zip encapsulates the compressed payload inside the standard ZIP file structure:

  1. Local File Header: 7-Zip writes metadata preceding each file, indicating compression method 8 (standard Deflate) or method 9 (Deflate64, which uses a 64 KB window), original file size, and timestamps.
  2. Deflate Bitstream: The compressed payload is written immediately following the local header.
  3. CRC-32 Checksum: A 32-bit cyclical redundancy check is calculated on the uncompressed data to ensure integrity upon extraction.
  4. Central Directory: At the end of the archive, 7-Zip appends the Central Directory, which indexes all contained files, file offsets, and compression parameters so extractors can parse the archive without scanning the entire file sequentially.