Lossless Compression: Huffman Optimality Proof, LZ77 Sliding Window & DEFLATE

1. Prefix-Free Codes, Kraft's Inequality & Huffman Optimality Proof

Given an alphabet $\Sigma$ with symbol frequencies $f_c > 0$, a prefix-free code assigns each $c \in \Sigma$ a bitstring of length $\ell_c$ such that no codeword is a prefix of another codeword. Equivalently, symbols correspond to leaves of a binary tree where left edges are $0$ and right edges are $1$. We want to minimize the weighted path length $L(T) = \sum_{c \in \Sigma} f_c \cdot \ell_c$. Huffman's algorithm repeatedly extracts the two minimum-frequency nodes $(x, y)$ from a min-heap and replaces them with a parent node of frequency $f_x + f_y$. Its optimality rests on two lemmas:

1. Greedy Choice Property (Sibling Exchange): Let $x, y \in \Sigma$ have the two smallest frequencies ($f_x \le f_y \le f_z$ for all other $z$), and let $T^*$ be any optimal full binary tree with two sibling leaves $a, b$ at maximum depth $d_{\max}$. Swapping $x \leftrightarrow a$ and $y \leftrightarrow b$ changes the total cost by: $$\Delta L = (f_a - f_x)(d_{\max} - d_a) + (f_b - f_y)(d_{\max} - d_b) \ge 0$$ because $f_a \ge f_x$, $f_b \ge f_y$, and $d_{\max} \ge d_a, d_b$. Since $T^*$ was already optimal, $\Delta L = 0$, so placing $x, y$ as deepest siblings is optimal!
2. Optimal Substructure (Merged Meta-Symbol): Once $x, y$ are fixed as sibling leaves under parent $p$ at depth $d_p$, their contribution to $L(T)$ is $(f_x + f_y)(d_p + 1) = (f_x + f_y)d_p + (f_x + f_y)$. Since $(f_x + f_y)$ is a constant additive term, minimizing $L(T)$ is identical to minimizing the tree cost over $\Sigma' = (\Sigma \setminus \{x, y\}) \cup \{p\}$ with $f_p = f_x + f_y$.

2. Canonical Huffman Codes & The DEFLATE (LZ77 + Huffman) Pipeline

How does a gzip file transmit the Huffman tree in its header without wasting bytes encoding tree pointers? Via Canonical Huffman Coding: if we sort symbols primarily by bit-length $\ell_c$ and secondarily by alphabet value $c$, and assign sequential binary integers (left-shifted whenever $\ell_c$ increases), the decoder can reconstruct the exact bitstring of every symbol from the array of lengths $\ell_c$ alone!

In DEFLATE (RFC 1951), the compressor scans the input with a 32 KB LZ77 sliding window (using a chained hash table keyed on 3-byte prefixes to find the longest match of length $3..258$ at distance $1..32768$), emitting a unified stream of Literal bytes ($0..255$), End-of-Block ($256$), and Length codes ($257..285$) followed by Distance codes ($0..29$), all compressed with Canonical Huffman trees.

3. Visual Trace: DEFLATE Pipeline & Canonical Huffman Assignment

4. Production Implementation: Huffman Code Lengths, Canonical Bit-Assignment & LZ77 Tokenizer

#include <algorithm>
#include <cstdint>
#include <queue>
#include <string_view>
#include <utility>
#include <vector>

struct CanonicalCode {
    uint8_t sym;
    uint8_t bit_len;
    uint32_t bits; // MSB-first canonical codeword in lower bit_len bits
};

// 1. Computes Optimal Huffman Lengths & Canonical Prefix-Free Bitstrings
std::vector<CanonicalCode> build_canonical_huffman(const std::vector<uint64_t>& freq) {
    struct Node {
        uint64_t w;
        int left, right, sym;
        bool operator>(const Node& o) const { return w > o.w; }
    };
    std::vector<Node> pool;
    std::priority_queue<std::pair<uint64_t, int>,
                        std::vector<std::pair<uint64_t, int>>,
                        std::greater<>> pq;

    for (int c = 0; c < static_cast<int>(freq.size()); ++c) {
        if (freq[c] > 0) {
            int id = static_cast<int>(pool.size());
            pool.push_back({freq[c], -1, -1, c});
            pq.push({freq[c], id});
        }
    }
    if (pq.empty()) return {};
    if (pq.size() == 1) {
        return {{static_cast<uint8_t>(pool[0].sym), 1, 0}};
    }

    while (pq.size() > 1) {
        auto [w1, u] = pq.top(); pq.pop();
        auto [w2, v] = pq.top(); pq.pop();
        int p = static_cast<int>(pool.size());
        pool.push_back({w1 + w2, u, v, -1});
        pq.push({w1 + w2, p});
    }

    std::vector<CanonicalCode> codes;
    auto dfs = [&](auto& self, int u, uint8_t d) -> void {
        if (pool[u].sym != -1) {
            codes.push_back({static_cast<uint8_t>(pool[u].sym), d, 0});
            return;
        }
        self(self, pool[u].left, d + 1);
        self(self, pool[u].right, d + 1);
    };
    dfs(dfs, pq.top().second, 0);

    // Sort by (bit_len, sym) and assign Canonical codewords
    std::sort(codes.begin(), codes.end(), [](const CanonicalCode& a, const CanonicalCode& b) {
        return (a.bit_len != b.bit_len) ? (a.bit_len < b.bit_len) : (a.sym < b.sym);
    });
    uint32_t cur_bits = 0;
    for (size_t i = 0; i < codes.size(); ++i) {
        if (i > 0) {
            cur_bits = (cur_bits + 1) << (codes[i].bit_len - codes[i - 1].bit_len);
        }
        codes[i].bits = cur_bits;
    }
    return codes;
}

// 2. LZ77 Sliding-Window Tokenizer with Overlap Support (e.g., dist=1, len=10 RLE)
struct LZ77Token {
    uint16_t dist; // 0 if literal
    uint16_t len;  // 0 if literal, else match length >= 3
    uint8_t lit;   // valid if dist == 0
};

std::vector<LZ77Token> lz77_encode(std::string_view src, size_t window_size = 32768) {
    std::vector<LZ77Token> out;
    const size_t n = src.size();
    size_t i = 0;
    while (i < n) {
        size_t best_dist = 0, best_len = 0;
        size_t start_j = (i > window_size) ? (i - window_size) : 0;
        for (size_t j = start_j; j < i; ++j) {
            size_t len = 0;
            while (i + len < n && len < 258 && src[j + len] == src[i + len]) {
                ++len;
            }
            if (len >= 3 && len > best_len) {
                best_len = len;
                best_dist = i - j;
            }
        }
        if (best_len >= 3) {
            out.push_back({static_cast<uint16_t>(best_dist), static_cast<uint16_t>(best_len), 0});
            i += best_len;
        } else {
            out.push_back({0, 0, static_cast<uint8_t>(src[i])});
            ++i;
        }
    }
    return out;
}