Deflate Compression: Block Structure and Algorithmic Mechanics
Deflate is a widely used compression algorithm that transforms a sequence of bytes into a compressed stream of blocks. The process is reversible: decompression takes these blocks and restores the original byte sequence. To achieve efficiency, Deflate utilizes a little-endian format, where bit 0 is treated as the least significant bit in a byte.
The Anatomy of a Deflate Block
Every block in a Deflate stream begins with a 3-bit header containing two critical fields: BFINAL and BTYPE.
- BFINAL (1 bit): A flag indicating the block's position. A value of 1 signifies the final block in the sequence; 0 indicates more blocks follow.
- BTYPE (2 bits): Defines the compression method used for the block.
Block Type Classifications
The BTYPE field determines how the subsequent data is handled:
- 00 (No Compression): Also known as "stored" blocks. These are used for high-entropy or already compressed data to avoid unnecessary overhead. The block contains a 16-bit length (LEN), a 16-bit one's complement of that length (NLEN), and up to 65,535 bytes of uncompressed data.
- 01 (Static Huffman): Uses a pre-defined Huffman tree specified in the RFC. This is ideal for short messages where the overhead of defining a custom tree would outweigh the compression gains.
- 10 (Dynamic Huffman): The most common method for compressible data. It generates an optimized Huffman tree customized for the specific data within that block.
- 11 (Reserved): This value is reserved and results in an error.
The Two-Stage Compression Process
Deflate achieves its reduction in size through two primary stages: duplicate string elimination and bit reduction.
1. Duplicate String Elimination
The algorithm searches for repeated sequences of bytes. When a duplicate string is found, Deflate replaces the repetition with a back-reference (a pointer) to the previous occurrence of that string.
A back-reference consists of an 8-bit length (representing 3 to 258 bytes) and a 15-bit distance (representing 1 to 32,768 bytes). These references can span multiple blocks, provided the distance falls within the sliding window—the last 32 KiB of decoded uncompressed data.
Interestingly, if the distance is shorter than the length, the duplicate overlaps itself, allowing the algorithm to efficiently encode long runs of identical bytes.
2. Bit Reduction via Huffman Coding
After eliminating duplicates, Deflate applies Huffman coding. This process replaces symbols with variable-length codes: frequently occurring symbols receive shorter bit-sequences, while rare symbols receive longer ones. This creates an unprefixed tree of non-overlapping intervals.
The system utilizes two distinct trees:
- Length/Literal Tree (288 symbols):
- 0–255: Literal bytes.
- 256: End of block marker.
- 257–285: Match lengths (3–258 bytes) combined with extra bits.
- 286–287: Reserved/Illegal.
- Distance Tree (32 symbols):
- 0–3: Distances 1–4.
- 4–31: Various distance ranges (e.g., 5–8, 9–16) accompanied by "extra bits" to reach the final distance value.
- 30–31: Reserved/Illegal.
For distance symbols 2 through 29, the number of extra bits is calculated using the formula: ⌊ n / 2 ⌋ − 1.
Key Facts
- Sliding Window: Limited to the last 32 KiB of uncompressed data.
- Max Stored Block: Up to 65,535 bytes per uncompressed block.
- Back-reference Range: Lengths from 3–258 bytes; distances from 1–32,768 bytes.
- Computational Cost: Searching for duplicate substrings is the most expensive part of the algorithm.
- Tree Encoding: Dynamic trees are encoded as canonical Huffman codes and further compressed using run-length encoding.
| BTYPE | Method | Best Use Case | Overhead/Characteristic |
|---|---|---|---|
| 00 | Stored | Incompressible/Random data | ~5 bytes per block |
| 01 | Static Huffman | Short messages | Fixed RFC-defined tree |
| 10 | Dynamic Huffman | Most compressible data | Customized tree per block |
| 11 | Reserved | N/A | Error |
Frequently Asked Questions
What is the purpose of the sliding window in Deflate?
The sliding window is the buffer of the last 32 KiB of uncompressed data. It defines the maximum distance a back-reference can look back to find a duplicate string.
How does Deflate handle data that cannot be compressed?
Deflate uses the "stored" block type (BTYPE 00). This allows the data to be passed through with minimal overhead (approximately 5 bytes per block) rather than wasting bits attempting to compress high-entropy data.
What is the difference between static and dynamic Huffman trees?
A static tree uses a fixed, pre-agreed set of codes defined in the RFC, which saves space by not needing to transmit the tree. A dynamic tree is custom-built for the specific data in the block, providing better compression ratios for larger datasets.
How are match lengths and distances determined?
Match lengths are derived from the 288-symbol tree (symbols 257–285) and may include extra bits. Distances are derived from a separate 32-symbol tree, where the symbol indicates a range and additional extra bits specify the exact distance.
Why is searching for duplicates the most expensive part of the process?
The algorithm must scan the preceding text within the sliding window to find the longest possible matching substrings. The intensity of this search is what typically determines the compression level settings.