LZ77, LZ78, and the Shift from Symbols to Substrings

Entropy coding assumes a model that assigns probabilities to symbols, and its guarantees are relative to that model. Dictionary coding starts from a different premise: that the data contains repeated substrings, and that a repetition can be described more cheaply by pointing at its earlier occurrence than by describing its contents. The two approaches are not competitors so much as layers, and the modern compressor almost always uses both: a dictionary parser to find repetitions, then an entropy coder over the resulting tokens.

The LZ77 formulation: a sliding window and a length-distance pair

LZ77 encodes the input as a sequence of triples, each consisting of a distance back into the already-processed text, a match length, and the next literal byte that breaks the match. A triple with distance zero and length zero is a literal with no match behind it, and a triple with a nonzero length carries its literal after the copied run. The distance is bounded by a window size: a reference may point only into the preceding $W$ bytes. The original formulation already bounded the lookback, and every format fixes a value because the decoder must be able to resolve any distance the encoder emits.

The decoding rule is what defines the format, and it has one subtlety. When the copy operation overlaps the current output position, which happens when the distance is smaller than the length, the copy repeats the pattern and acts as run-length encoding at no extra cost. Decoding a token with distance 1 and length 5 at a position where the last output byte is a produces aaaaa for the match and then emits the literal. Any decoder that copies byte by byte in order handles this naturally; one that copies in blocks must be written to tolerate the overlap, and getting that wrong is a common source of divergence between encoder and decoder.

The format is not self-delimiting in a useful way: the encoder must signal end of stream, and the choice of how to encode distances and lengths is format-specific. DEFLATE encodes match lengths in 29 codes and distances in 30 codes, each covering a base value plus extra bits, and then Huffman-codes the code symbols themselves. That Huffman layer is where entropy coding returns, applied to the token stream rather than to the original bytes.

A minimal decoder makes the mechanics concrete:

def lz77_decode(tokens):
    out = bytearray()
    for dist, length, literal in tokens:
        if dist == 0:
            out.append(literal)          # no match: emit the literal only
            continue
        start = len(out) - dist
        for i in range(length):
            out.append(out[start + i])   # byte-at-a-time copy handles overlap
        if literal is not None:
            out.append(literal)
    return bytes(out)

The dist == 0 convention marks a literal run with no match, which every practical format needs because incompressible data produces matches of length zero constantly. The overlap tolerance is in the out[start + i] read, which sees bytes appended earlier in the same loop.

LZ78 and the explicit dictionary

LZ78 replaces the window with a dictionary built during encoding. At each step the encoder finds the longest dictionary entry that is a prefix of the remaining input, emits the index of that entry plus the next character, and adds the concatenation to the dictionary. Indices are numbered in order of creation, so the decoder can reconstruct the dictionary from the index sequence alone, without transmitting it.

The difference from LZ77 is structural. LZ77 refers to positions in a bounded recent window; LZ78 refers to an unbounded set of phrases discovered so far. LZ77’s references are cheap to encode because the distance distribution is skewed toward small values, and it adapts instantly to local repetition. LZ78’s dictionary grows monotonically and never forgets, which is better for long-range structure and worse for nonstationary data, where stale entries waste index space.

LZW, the variant that became widely deployed, preloads the dictionary with all single-byte strings and emits only indices, with the dictionary extended by one entry per output code. It needs no literal channel at all, which simplifies the format, and it is the algorithm behind the compress utility and the GIF image format. Its weakness is equally structural: each output code adds at most one dictionary entry, and the code width must widen as the table grows, so a decoder has to infer the encoder’s widening rule exactly. A table reset discards everything learned, and the point at which it can happen is a format decision that affects the compression ratio on long inputs.

Why entropy is the wrong yardstick here

The source-coding theorems bound the expected length of a code for a probabilistic source. Dictionary coders are defined for individual strings, with no distribution assumed, and their guarantees are stated differently: the Lempel–Ziv schemes are universal in the sense that for a stationary ergodic source, with the window or dictionary allowed to grow with the input, their compression ratio converges to the entropy rate without any knowledge of the source. That is an asymptotic statement about a family of inputs, not a bound on any particular string, and it says nothing useful about a short input or a source that changes.

For an individual string, the natural measure is the number of distinct phrases in its LZ78 parsing. That number is bounded by the solution of $m(m+1)/2 \le n$, since $m$ distinct phrases of lengths $1, \ldots, m$ consume at least $m(m+1)/2$ symbols, so it grows no faster than about $\sqrt{2n}$ even for a string with no structure at all; the linear-in-$n$ figure of $n/\log n$ belongs to the Lempel–Ziv complexity defined through a different parsing. The compressed size of a string under LZ78 is proportional to its phrase count times the index width, so the achievable size is a property of the string’s repetitiveness rather than of any distribution.

This is where dictionary coding and entropy coding diverge in what they are bounded by, and why a dictionary coder can appear to beat an order-0 entropy estimate without paradox. Shannon’s 1951 estimates of the entropy of printed English, obtained from a subject’s predictions rather than from a frequency table, put the rate near one bit per character once long-range dependence is accounted for, far below the 4.7 bits that a uniform 27-symbol alphabet would imply. A dictionary coder operating below a published order-0 figure is exploiting dependence over a longer range than that figure’s model represents, so the two numbers measure different things.

Parsing decisions dominate the result

The encoder’s freedom is in how it chooses matches, and the choice is a genuine optimization problem. Greedy parsing takes the longest match available at each position. That is locally sensible and globally suboptimal: a long match now may consume the start of an even longer match that would have paid better.

The standard improvement is lazy matching, used in DEFLATE encoders. At each position, find the best match; then check whether the next position has a strictly longer match. If it does, emit a literal at the current position and take the longer match next. The rule costs one extra search per position and buys back some of the gap to optimal parsing, with no guarantee of how much.

Optimal parsing formulates the choice as a shortest-path problem. Each position is a node, each candidate match is an edge with cost equal to the bits needed to encode it under the current entropy model, and the cheapest path through the string is the optimal token sequence. The catch is that the cost of a token depends on the entropy model, which depends on the token frequencies, which depend on the parse. Practical encoders iterate: parse with the current model, recount, reparse. Two or three iterations are typical, and the process is not guaranteed to converge to a global optimum.

The window size is the other dominant parameter. A larger window finds more matches and costs more memory and search time; the search structure is usually a hash chain or a binary tree over the last $W$ bytes. Doubling the window doubles the number of positions a new match can refer to and roughly doubles the search work per position, and every format fixes a maximum because a reference beyond the decoder available history cannot be resolved. DEFLATE bounds distances at 32768 bytes, which the distance codes encode directly.

Failure modes specific to dictionary coding

Pathological inputs. Data with no repetition compresses to slightly more than its original size, because every literal is emitted with token overhead. The overhead is bounded and small, a few percent for a byte-oriented format, but it is positive, and a format that must never expand needs a stored-block escape. DEFLATE provides one: a block can be marked as stored and copied verbatim.

Adversarial expansion. Because the format is known, inputs can be constructed whose parse produces many short matches and long distance codes, inflating the output relative to the input. This is the mechanism behind decompression bombs in formats that allow high ratios, and it is a reason to bound the expansion factor when decompressing untrusted data.

Window-induced divergence. A reference at distance $d$ is only valid if the decoder has at least $d$ bytes of history. In streaming use the decoder’s history is the window, and an encoder that emits a distance beyond the negotiated window produces a stream that decodes incorrectly rather than failing cleanly. Format specifications state the maximum distance explicitly for this reason.

Dictionary resets and shared dictionaries. A reset discards context; a preset dictionary lets the decoder start with context the encoder assumes. The second is effective for small payloads, where a few hundred bytes of boilerplate can be encoded entirely as references, but it couples the stream to the dictionary, so the decoder must obtain the exact same bytes. Any mismatch produces silent corruption, not an error.

The layered structure is what makes the approach practical. The dictionary parser reduces the problem to a token stream with a skewed distribution; the entropy coder, described in Range Coding and rANS in Modern Compressors, then extracts the remaining redundancy from that stream. Neither layer alone reaches the rates that current formats achieve, and the interface between them, meaning which symbols the entropy coder sees and how their probabilities are estimated, is where most of the remaining design work happens.