gzip Compression — Binary Data Expansion with LZ77

Every gzip file, every zip archive, every PNG image, every HTTPS response with Content-Encoding: gzip — all of these use DEFLATE, which is LZ77 combined with Huffman coding. Lempel and Ziv published two papers in 1977 and 1978 that are among the most cited in information theory. The algorithms they described became the foundation of essentially all practical lossless compression for the next 50 years.

The key insight in LZ77 is that the best dictionary for compressing text is the text you have already seen. Instead of building a static dictionary from training data, the encoder and decoder both maintain a sliding window of recent output — they are always perfectly synchronised without transmitting the dictionary itself. This is why LZ compression is both efficient and streamable.

How LZ77 Compression Actually Works — Sliding Windows and Back-References

LZ77 and LZ78 are dictionary-based compression algorithms that replace repeated sequences with back-references. LZ77 uses a sliding window over already-seen data: it searches for the longest match between the current input and the window, then emits a (length, distance) pair instead of the raw bytes. LZ78 builds an explicit dictionary of phrases as it goes, emitting (index, next character) pairs. Both achieve compression by exploiting redundancy, but LZ77's window size directly limits how far back it can look — typically 32KB in gzip.

In practice, LZ77 is the core of gzip (RFC 1951). It operates in O(n) time with a hash-chain or binary-tree lookup for matches, but worst-case O(n²) if poorly implemented. The key property: compression ratio improves with larger windows and more redundancy, but memory usage scales with window size. LZ78's dictionary grows unbounded unless pruned, making it less common in modern formats.

Use LZ77 when you need a fast, streaming compressor with bounded memory — HTTP compression, file archives, and network protocols. It's not ideal for small payloads (under a few hundred bytes) where the overhead of back-references can actually expand data. Understanding this trade-off is critical: gzip can inflate tiny JSON responses by 20-30% due to header overhead and failed matches.

LZ77 — Sliding Window Compression

LZ77 maintains a sliding window of recently seen data (search buffer) and a lookahead buffer. For each position, it finds the longest match in the search buffer. The output is a triple: (offset, length, next_char). Offset is the distance back to the match; length is how many characters match; next_char is the literal following the match (or empty if at end).

The window size is a key parameter. Larger windows catch longer repetitions but increase search time and memory. In practice, DEFLATE uses 32KB maximum window. LZ77 is the core of all modern ZIP, gzip, and PNG compression.

def lz77_encode(data: str, window: int = 20, lookahead: int = 10) -> list:
    """
    Returns list of (offset, length, next_char) tokens.
    offset=0, length=0 means literal character.
    """
    tokens = []
    i = 0
    while i < len(data):
        best_offset = best_length = 0
        # Search in window for longest match
        start = max(0, i - window)
        for j in range(start, i):
            length = 0
            while (length < lookahead and
                   i + length < len(data) and
                   data[j + length] == data[i + length]):
                length += 1
            if length > best_length:
                best_length = length
                best_offset = i - j
        if best_length >= 2:
            next_char = data[i + best_length] if i + best_length < len(data) else ''
            tokens.append((best_offset, best_length, next_char))
            i += best_length + 1
        else:
            tokens.append((0, 0, data[i]))
            i += 1
    return tokens

def lz77_decode(tokens: list) -> str:
    result = ''
    for offset, length, char in tokens:
        if offset == 0 and length == 0:
            result += char
        else:
            start = len(result) - offset
            for k in range(length):
                result += result[start + k]
            result += char
    return result

text = 'abracadabrabracabra'
tokens = lz77_encode(text)
print(f'Tokens: {tokens}')
print(f'Decoded: {lz77_decode(tokens)}')
print(f'Original: {len(text)} chars, Tokens: {len(tokens)} (each needs ~3 bytes)')

LZ78 — Dictionary-Based Compression

LZ78 builds an explicit dictionary of phrases. Instead of a sliding window, the encoder maintains a growing table of previously seen substrings. Each token is (dictionary_index, new_char). The index refers to a previously added phrase; new_char extends it. The decoder builds the same dictionary as it reads tokens — no side-channel transmission needed.

The key difference from LZ77: LZ78 can refer to any past phrase, even very old ones, as long as they are in the dictionary. However, the dictionary has a fixed maximum size in practice. LZ78 is the basis for GIF (via LZW), TIFF, and Unix compress.

Practical implementations limit dictionary size (e.g., 12-bit indices = 4096 entries). When full, the dictionary is either frozen or reset.

def lz78_encode(data: str) -> list[tuple]:
    dictionary = {}
    tokens = []
    current = ''
    for char in data:
        extended = current + char
        if extended in dictionary:
            current = extended
        else:
            idx = dictionary.get(current, 0)
            tokens.append((idx, char))
            dictionary[extended] = len(dictionary) + 1
            current = ''
    if current:
        tokens.append((dictionary.get(current, 0), ''))
    return tokens

text = 'abababab'
tokens = lz78_encode(text)
print(f'Input: {text}')
print(f'LZ78 tokens: {tokens}')

Real-World Derivatives

DEFLATE (LZ77 + Huffman): Powers gzip, ZIP, PNG, HTTP compression (Content-Encoding: gzip). The dominant compression format on the internet.

LZW: LZ78 derivative. Used in GIF, old TIFF, Unix compress. Patents expired, now freely usable.

zstd (Zstandard): Modern Facebook LZ77 derivative. 3-5x faster than gzip with similar ratios. Used in Linux kernel, Facebook infrastructure, Hadoop.

Snappy: Google's LZ77 variant optimising for speed over ratio. Used in LevelDB, Cassandra, Hadoop.

LZ77 vs LZ78 — Key Differences and Trade-offs

Both algorithms belong to the same family, but they differ fundamentally in how they encode repetition. LZ77 stores references to a fixed-size sliding window; LZ78 stores references to an ever-growing dictionary of phrases. This leads to different strengths:

• LZ77 produces variable-length tokens depending on offset range, requiring entropy coding (Huffman) afterwards for efficiency.
• LZ78 tokens are fixed-length (dictionary index bit width), simplifying the output but limiting the dictionary size.
• LZ77 decompression is minimal overhead; LZ78 requires rebuilding the dictionary.
• LZ78 can match patterns across very long distances (as long as they entered the dictionary), while LZ77 is limited by window size.

In practice, LZ77 dominates (DEFLATE, zstd, brotli, LZMA). LZ78 appears in legacy GIF.

Compression in Practice: Choosing the Right Algorithm

Selecting between LZ variants depends on the data, constraints, and use case. Here's a pragmatic guide:

• Web delivery: Use Brotli (LZ77 + custom entropy) for text assets; gzip fallback.
• File archives: Use zstd for speed+ratio; LZMA for maximum ratio but slower.
• Databases (LSM trees): Use Snappy or LZ4 for per-block compression — low CPU overhead.
• Network compression (e.g., SSH): Use zlib (DEFLATE) for balanced compression.
• Image formats: PNG uses DEFLATE; GIF uses LZW; both are LZ-based.

When implementing custom compression: start with an LZ77 variant and add entropy coding (Huffman, arithmetic) if needed.

The Hidden Cost: Why LZ77 and LZ78 Can Bite You in Production

Everyone loves compression ratios until the CPU spins at 100% for 30 seconds on a 10MB file. The sliding window in LZ77 and the growing dictionary in LZ78 have real costs that junior engineers ignore until pager duty calls.

LZ77's sliding window means you're doing string comparisons against every position in the buffer for every input byte. That's O(n * m) in the worst case, where m is your window size. Dial the window too large — say 32KB for a 1MB file — and you'll watch your throughput crater. Production systems like nginx and Apache tune this constantly.

LZ78's dictionary has its own pain point: memory. Every new substring adds an entry. On repetitive data like logs or configuration files, that dictionary balloons. You'll hit the OOM killer before you hit your compression target. Real-world derivatives like GIF limit the dictionary to 4096 entries for exactly this reason — they know the cost.

The trade-off isn't just compression ratio vs speed. It's predictability. LZ77 gives you bounded memory and unbounded CPU. LZ78 gives you bounded CPU but unbounded memory. Pick your poison based on the production environment, not the textbook.

// io.thecodeforge — dsa tutorial

// Simulating LZ78 dictionary bloat on repetitive log data
import java.util.*;

public class MemoryBloatSimulation {
    public static void main(String[] args) {
        String input = "ERROR timeout connecting to db\n".repeat(10000);
        Map<String, Integer> dictionary = new HashMap<>();
        
        int dictSize = 0;
        for (int i = 0; i < input.length(); i++) {
            String pattern = "";
            for (int j = i; j < Math.min(i + 10, input.length()); j++) {
                pattern += input.charAt(j);
                dictionary.putIfAbsent(pattern, dictSize++);
                if (dictionary.size() % 10000 == 0) {
                    System.out.println("Dictionary entries: " + dictionary.size());
                }
            }
        }
    }
}

Why Your Compressor Needs a Minimum Match Length

The textbooks show LZ77 outputting (offset, length, nextChar) for every match. They never tell you that matching a 2-byte sequence costs more than just emitting the raw bytes. This is the hidden gotcha that separates a working prototype from a production compressor.

Every back-reference requires you to encode, store, and decode an offset and a length. On a modern CPU, that's not free. If you emit a reference for a 2-byte match, you've just spent 2-3 bytes of metadata to save 1 byte of data. Net loss. Real compressors like zlib and LZMA enforce a minimum match length — typically 2 or 3 bytes. Anything shorter gets emitted as a literal.

The impact is measurable. On random data, minimum match length of 3 means most output is literals. That's fine — random data doesn't compress anyway. On structured data like JSON or XML, the minimum match threshold filters out noise matches that would bloat your compressed stream. I've seen 15% compression ratio improvements just by tuning this value from 1 to 3.

Production tip: profile your data. If your compressor produces more back-references than literals on common input, your minimum match length is probably too low. Raise it. Watch your ratio improve. Every byte counts when you're shipping firmware over cellular.

// io.thecodeforge — dsa tutorial

// Testing impact of minimum match length on compression ratio
public class MinMatchLengthTuner {
    public static double compressRatio(String input, int minMatch) {
        int literalSize = input.length();
        int referenceCount = 0;
        int referenceBytes = 0;
        
        for (int i = 0; i < input.length() - minMatch; i++) {
            for (int j = 1; j <= i; j++) {
                if (input.regionMatches(i - j, input, i, minMatch)) {
                    referenceCount++;
                    referenceBytes += 2; // offset + length
                    i += minMatch - 1;
                    break;
                }
            }
        }
        
        int totalOutput = literalSize - (minMatch * referenceCount) + referenceBytes;
        return (double) totalOutput / input.length();
    }
    
    public static void main(String[] args) {
        String testData = "HTTP/1.1 200 OK\nContent-Type: text/html\nServer: nginx\n\n<html><body>Hello world</body></html>".repeat(10);
        
        for (int minLen = 1; minLen <= 4; minLen++) {
            double ratio = compressRatio(testData, minLen);
            System.out.println("Min match " + minLen + ": " + String.format("%.3f", ratio));
        }
    }
}