String Compression

Entropy and Prefix-Free Coding

A lossless compressor exploits a probability model rather than making symbols intrinsically smaller. An event of probability $p$ carries self-information $I(p)=-\log_2p$ bits. For probabilities $p_1,\dots,p_\sigma$, the entropy $H(X)=-\sum_i p_i\log_2p_i$ is the ideal expected information per symbol under the model. Real formats also pay for model descriptions, block metadata, checksums, and finite representations.

A binary prefix-free code assigns no symbol a codeword that prefixes another. If lengths are $\ell_1,\dots,\ell_\sigma$, Kraft–McMillan requires $\sum_i2^{-\ell_i}\le 1$: every length-$\ell$ word occupies a fraction $2^{-\ell}$ of a binary tree's leaves, and codeword subtrees must be disjoint.

Huffman repeatedly combines the two least-frequent nodes and minimizes expected length among binary prefix codes for the supplied frequencies. Ties can yield different trees with equal cost. A canonical code transmits only lengths: sort by (length, symbol), assign consecutive integers within a length, and left-shift when length increases. This produces deterministic compact tables.

from collections import Counter
from heapq import heappop, heappush
from itertools import count
from typing import TypeAlias


Tree: TypeAlias = str | tuple["Tree", "Tree"]


def huffman_code_lengths(frequencies: dict[str, int]) -> dict[str, int]:
    """Compute deterministic Huffman code lengths."""
    if not frequencies:
        return {}
    serial = count()
    heap: list[tuple[int, int, Tree]] = []
    for symbol in sorted(frequencies):
        frequency = frequencies[symbol]
        if frequency <= 0:
            raise ValueError("frequencies must be positive")
        heappush(heap, (frequency, next(serial), symbol))
    if len(heap) == 1:
        symbol = heap[0][2]
        assert isinstance(symbol, str)
        return {symbol: 1}
    while len(heap) > 1:
        lf, _, left = heappop(heap)
        rf, _, right = heappop(heap)
        heappush(heap, (lf + rf, next(serial), (left, right)))
    lengths: dict[str, int] = {}

    def visit(node: Tree, depth: int) -> None:
        if isinstance(node, str):
            lengths[node] = max(depth, 1)
        else:
            visit(node[0], depth + 1)
            visit(node[1], depth + 1)

    visit(heap[0][2], 0)
    return lengths


def canonical_codes(lengths: dict[str, int]) -> dict[str, str]:
    """Assign canonical bit strings from code lengths."""
    ordered = sorted(lengths.items(), key=lambda item: (item[1], item[0]))
    code = previous_length = 0
    result: dict[str, str] = {}
    for symbol, length in ordered:
        if length <= 0:
            raise ValueError("code lengths must be positive")
        code <<= length - previous_length
        if code >= 1 << length:
            raise ValueError("invalid prefix-code lengths")
        result[symbol] = format(code, f"0{length}b")
        code += 1
        previous_length = length
    return result


def encode(text: str) -> tuple[str, dict[str, int]]:
    if not text:
        return "", {}
    lengths = huffman_code_lengths(dict(Counter(text)))
    codes = canonical_codes(lengths)
    return "".join(codes[symbol] for symbol in text), lengths


def decode(bits: str, lengths: dict[str, int]) -> str:
    if not lengths:
        if bits:
            raise ValueError("bits supplied without a model")
        return ""
    by_code = {code: symbol for symbol, code in canonical_codes(lengths).items()}
    output: list[str] = []
    prefix = ""
    for bit in bits:
        if bit not in {"0", "1"}:
            raise ValueError("encoded data must contain only bits")
        prefix += bit
        if prefix in by_code:
            output.append(by_code[prefix])
            prefix = ""
    if prefix:
        raise ValueError("encoded data ends inside a codeword")
    return "".join(output)


if __name__ == "__main__":
    for message in ["", "A", "ABRACADABRA", "BANANA_BANDANA"]:
        bits, model = encode(message)
        assert decode(bits, model) == message
        print(message, len(bits), dict(sorted(model.items())))

Arithmetic, Range, and Context Coding

Arithmetic coding represents a complete message as a subinterval of $[0,1)$. A model partitions the current interval by cumulative probability; encoding selects the next symbol's region repeatedly and finally emits a value inside the end-symbol interval. Unlike a prefix code, this amortizes fractional information across symbols.

Range coders implement the same idea with integer low and high bounds. They emit shared leading bits or bytes, renormalize before precision is exhausted, and specify carry and underflow rules exactly. A static model transmits fixed frequencies; an adaptive model updates agreed initial counts after each symbol. Context models condition probabilities on preceding symbols and may back off to shorter contexts when evidence is sparse.

Decoding is symmetric: map the coded value to a cumulative-frequency position, select the symbol, narrow the interval exactly as the encoder did, update the model, and renormalize. One disagreement in frequencies or update order corrupts every subsequent decision.

Run-Length and Dictionary Compression

RLE replaces a maximal run with a symbol-count pair. It excels on masks, repeated pixels, sparse bitmaps, and transformed data, but can expand alternating input; practical formats mix literal blocks and run blocks.

LZ77 uses already decoded text as a sliding dictionary and emits literals or (distance, length) references. Overlapping references can generate long repetitions from short seeds. Greedy LZ factorization selects the longest previous factor at each position, while practical encoders limit match search using hash chains or suffix-based indexes.

LZ78 builds explicit phrases and emits (prior phrase, next symbol). LZW makes the initial single-symbol dictionary implicit and emits phrase codes while encoder and decoder add entries synchronously. Width growth, reset rules, and the next-not-yet-created-code case belong to the format contract.

The Burrows-Wheeler Compression Pipeline

With a unique sentinel smaller than every alphabet symbol, the BWT sorts cyclic rotations and emits their final column plus a primary-row convention. It does not compress by itself; it clusters symbols preceding similar contexts, creating local runs.

For inversion, stable sorting the last column $L$ produces the first column $F$. The $k$-th occurrence of a symbol in $L$ corresponds to its $k$-th occurrence in $F$. Repeated LF steps reconstruct the text. Cumulative counts and occurrence ranks implement the mapping without storing rotations.

Move-to-front replaces each BWT symbol by its current position in an alphabet list and moves it to the front, turning clusters into many small ranks and zeros. RLE compresses zero runs, then Huffman, arithmetic, or range coding encodes the resulting distribution. Decompression reverses the stages exactly.

flowchart LR
    TEXT["Text plus sentinel"]
    BWT["Burrows-Wheeler transform"]
    MTF["Move-to-front ranks"]
    RLE["Run-length encoding"]
    ENTROPY["Entropy coding"]
    STREAM["Compressed bitstream"]
    TEXT -->|"reversible permutation"| BWT
    BWT -->|"clusters become small ranks"| MTF
    MTF -->|"collapse zero runs"| RLE
    RLE -->|"encode symbol probabilities"| ENTROPY
    ENTROPY --> STREAM
    STREAM -. decode .-> ENTROPY
    ENTROPY -. expand .-> RLE
    RLE -. inverse MTF .-> MTF
    MTF -. LF mapping .-> BWT
    BWT -. restore .-> TEXT

Compression Engineering and Search

Compression ratio must be balanced against encode time, decode throughput, memory, latency, and parallelism. Larger blocks expose longer repetition; smaller independent blocks improve random access, bounded memory, parallel decoding, and corruption containment.

DEFLATE combines bounded-window LZ77 with fixed or transmitted Huffman tables. A damaged length, distance, or entropy symbol can desynchronize a block, so containers add checksums, frames, restart points, and lengths. Grammar compression represents repeated substrings as nonterminals in a straight-line grammar; it can be excellent for repetitive collections, though construction and indexed navigation are more complex.

Ordinary streams are not inherently seekable because late output may depend on earlier dictionary and model state. Seekable formats add independently decodable frames and offset indexes. Compressed indexes retain rank, select, sampling, or grammar-navigation data so search and extraction can run without reconstructing the whole text.