How ZIP Files Compress Data: LZ77, Huffman Coding, and Byte Packing

ZIP files are the universal wrappers of the computing world, but how do they squeeze gigabytes of text and images into tiny archive packages? The magic behind the modern ZIP archive is almost entirely driven by the DEFLATE compression algorithm, standardized in RFC 1951. DEFLATE is a two-step process: it first uses LZ77 (Lempel-Ziv) dictionary matching to remove duplicate strings, and then uses Huffman coding to optimize the bit representation of the remaining characters.

Let's break down the first step: LZ77. As the algorithm reads a stream of text (like 'the banana ate the other banana'), it maintains a sliding window of recently read characters. When it detects a repeating phrase, instead of writing the characters again (e.g., 'banana'), it writes a relative pointer: a back-reference composed of a distance (how many characters to look back) and a length (how many characters to copy). This simple dictionary substitution replaces long words and patterns with tiny coordinate pairs.

Once duplicate strings are converted into coordinate pointers, the second step—Huffman coding—begins. In standard ASCII text, every character takes exactly 8 bits (1 byte) of memory. Huffman coding maps characters to variable-length binary codes based on their frequency. Frequently used characters (like 'e' or space) are assigned short binary strings (like '01' or '10'), while rare characters (like 'z' or 'q') get much longer codes (like '1101011'). These codes are organized in a binary prefix tree, ensuring that no code is a prefix of another, allowing the decoder to read the compressed bitstream sequentially without dividers.