LZ77 and LZ78 Parsing: Offsets Versus a Phrase Dictionary

Both Lempel–Ziv families replace repeated substrings with references, and both decode in time linear in the output with no auxiliary index. They differ in what a reference points at. LZ77 points backwards into the text already produced, by a distance and a length. LZ78 points into a dictionary of phrases built during the scan, by an index. The first needs no dictionary at decode time because the output itself is the dictionary; the second needs the dictionary to be rebuilt, in the same order, by the decoder.

That difference determines almost everything else: the maximum reference distance, whether decoding can start in the middle of a stream, how the encoder searches for matches, and how the compressed format is specified.

The sliding window and its arithmetic

LZ77 maintains a window of the most recent W bytes as the dictionary and a lookahead buffer of the next few bytes. At each step the encoder finds the longest prefix of the lookahead that occurs in the window and emits a reference to it: classically a triple of (distance, length, next literal), advancing by length + 1 bytes, and in the compact variant used below a (distance, length) pair for a match or a (0, byte) pair for a literal.

The distance is measured backwards from the current position, so distance 1 means the immediately preceding byte. The length is the match length; the literal in a zero-distance token is copied verbatim. Emitting a literal is the escape for “no useful match here”, and encoders fall back to it whenever a reference would cost more than a literal.

Two parameters bound the format. W bounds the distance field: a 15-bit distance field addresses at most 32768 positions. A length field of a few bits bounds the match length; DEFLATE’s maximum match is 258 bytes, and its minimum is 3, because a shorter match costs more to encode than the literals it replaces. The minimum length is set by the cost of the length and distance codes relative to literal codes; the maximum is set by the length code table’s size, which uses a base value and extra bits per code.

The window size is the main compression knob. A larger window finds longer matches at greater distances and therefore compresses better, but the decoder must retain W bytes and the encoder’s search structure grows with W. The 32 KB window in DEFLATE is a compromise fixed by the format’s field widths, not by any property of the data.

def lz77_encode(data, window=4096, max_len=15):
    out, pos = [], 0
    while pos < len(data):
        limit = min(max_len, len(data) - pos)
        best_len, best_dist = 0, 0
        for i in range(max(0, pos - window), pos):
            n = 0
            while n < limit:
                if data[i + n] == data[pos + n]:
                    n += 1
                    if i + n == pos:      # the copy has reached its own source
                        break
                else:
                    break
            if n > best_len:
                best_len, best_dist = n, pos - i
        if best_len >= 3:
            out.append((best_dist, best_len))   # the decoder repeats the copy
            pos += best_len
        else:
            out.append((0, data[pos]))
            pos += 1
    return out

The overlap case is the one that surprises people. A match may extend past the current position, because the decoder copies byte by byte from a region it is simultaneously writing. Encoding a run of identical bytes as distance 1, length 258 is legal and is how long runs compress to a handful of bytes. The encoder’s comparison loop must therefore allow the source index to reach the current position, and the inner comparison deliberately stops there: the bytes beyond pos have not been seen yet, but once the decoder copies byte pos it holds the same value as data[i], so the comparison is guaranteed to succeed through the end of the overlap. The decoder must copy forward one byte at a time rather than using a block move, since a block move with overlapping ranges has undefined behaviour in most memory APIs.

Finding the match without quadratic search

The loop above is O(W) candidate positions per input byte, each with a comparison up to the maximum length, which is far too slow for W in the tens of thousands. Practical encoders use one of three search structures.

Hash chains. A hash table maps a short prefix (three bytes, typically) to the most recent position with that prefix, and each position stores a link to the previous position with the same prefix. Searching walks the chain, newest first, and stops after a fixed number of candidates or when the distance exceeds the window. The chain is bounded by the window and by the candidate limit, so the search is O(1) per byte with a constant that depends on the limit. This is the structure zlib uses for its default strategy, and the candidate limit is the encoder’s main speed-versus-ratio trade: more candidates means better matches and slower compression.

Binary search trees. A tree keyed by the current suffix, ordered lexicographically, with nodes inserted as the window advances and removed as it slides. The tree finds the longest match by descending to the predecessor and successor of the current suffix, which are the lexicographically nearest strings and therefore the best candidates. Each update costs O(log W) and the match search is bounded by the depth. The structure gives better ratios than a short chain at the cost of more work per byte, and it is the classic choice when the encoder is allowed to spend time rather than memory.

Suffix arrays or suffix automata over the window. Rebuilding a suffix array per window position is too expensive, but maintaining one over the window with incremental updates, or using a suffix automaton over the window with deletion support, gives exact longest matches. The cost is implementation complexity, and the gain over a good tree is small for the window sizes DEFLATE-style formats actually use.

A fourth option, used in high-ratio compressors, is to parse the input with a slower optimiser that considers several candidate matches and chooses the sequence minimising the encoded size, rather than greedily taking the longest match at each position. The greedy choice is not optimal: taking a slightly shorter match now can expose a much longer one at the next position. Lookahead heuristics, such as lazy matching, test whether the next position offers a match longer than the current one by more than a threshold and, if so, emit a literal now and take the longer match next. This is a bounded form of the full optimisation problem, which is solvable by dynamic programming over the input when the match set per position is known.

LZ78 and the explicit phrase table

LZ78 abandons the window. It builds a dictionary of phrases during the scan: at each step it reads the longest prefix of the remaining input that is a dictionary entry, emits (index of that entry, next character), and adds the concatenation as a new entry.

The dictionary starts with the empty phrase at index 0, so index 0 is a valid reference meaning “no prefix from the dictionary, the token is a single new character”. A token carries the index of the longest dictionary phrase that prefixes the remaining input, together with the character that follows it, and the pair becomes the next entry. Entries are created at every step, one per token and one for the trailing phrase if the input ends mid-phrase, so the dictionary size grows with the number of tokens rather than being bounded by a window. Because the dictionary starts with only the empty phrase, the first token always carries index 0; later tokens either reference an existing phrase or reuse index 0 when the current character begins no stored phrase. In practice the dictionary is capped and reset or frozen when it fills, which is what the GIF and TIFF variants of the LZW descendant do.

Decoding is a single pass with no search: read the index, look up the phrase, append the character, output the result, and add the new phrase. The dictionary is rebuilt identically because both sides add entries in the same order, which is why an LZ78 stream can be decoded from its beginning without any prior state, and why it cannot be decoded from an arbitrary offset without replaying the dictionary.

The trie is the natural encoder structure. Each dictionary phrase is a node, and reading the input descends the trie until no child exists for the next character; the node reached is the index to emit, the missing character is the literal, and a new child is created for that character. Each token costs one descent step in the trie plus the cost of the child lookup, so encoding is O(n) with a hash-based child map and no search over candidates at all.

def lz78_encode(data):
    phrases = {"": 0}
    out, buf = [], ""
    for ch in data:
        cand = buf + ch
        if cand in phrases:
            buf = cand
        else:
            out.append((phrases[buf], ch))
            phrases[cand] = len(phrases)
            buf = ""
    if buf:
        out.append((phrases[buf], ""))   # final phrase with no trailing character
    return out

LZW, the 1984 variant, removes the literal from each token by pre-loading the dictionary with all single characters and emitting only indices. A reference to a phrase of length L therefore stands for L characters instead of L−1, and the token is a single index rather than an index and a byte, which is what made it suitable for hardware implementations and for formats that store a code width that grows as the dictionary fills. The cost is that the dictionary must be initialised to the alphabet, and the decoder must synchronise the dictionary exactly: the classic LZW decoder defect is adding a phrase one step early or late, which corrupts every subsequent token rather than producing a local error. A second decoder obligation is the one case the encoder can create but the decoder has not yet stored: the code just added can be referenced immediately, and its phrase is the previous phrase followed by its own first character.

Decode cost in both families

LZ77 decoding copies from the output buffer. Each token is a copy of length up to the maximum match, from a distance bounded by the window, and the distance is known before the copy, so the copy can use a bulk memory primitive when it does not overlap. Overlapping copies must be bytewise or handled with a pattern fill. Decode time is proportional to the output size with a small constant, which is why DEFLATE decoders are fast enough to be used in interactive paths.

LZ78 decoding is a table lookup plus an append per token, with the appended phrase copied into the output. Each token produces at least one output byte, and long phrases are copied as a unit, so the work per output byte is bounded but the constant depends on the dictionary’s memory layout. A dictionary of phrases stored as linked lists makes each copy a pointer chase; storing offsets into a single arena makes it a contiguous copy.

The asymmetry between encode and decode cost is much larger for LZ77. The encoder performs a search per input position, which for a hash chain is tens of operations and for a tree is a logarithm of the window, while the decoder performs one copy. That asymmetry suits distribution: compression happens once, decompression happens many times, and a format is worth a slow encoder if the decoder stays fast.

Failure modes and format constraints

Distance beyond the window. A decoder must reject a distance that exceeds the bytes produced so far. Emitting one is a stream corruption, and the decoder cannot recover a sensible output because the referenced bytes do not exist. This is the first check a decoder performs, and it is why the distance field’s width and the window size must agree by construction.

Overlap at the buffer start. A copy of length L from distance D where D < L is legal and produces a periodic extension of the D bytes. A copy from distance D where D ≥ L is a plain copy. A decoder that treats all copies as plain block moves produces wrong output only for the overlapping case, which appears in inputs with runs and is therefore common.

Dictionary resets. LZ78 variants that cap the dictionary must reset it at a defined point and the decoder must reset at the same point. If the reset condition depends on a counter the decoder computes differently — for example counting tokens rather than phrases — the two sides diverge and every later token decodes to garbage.

Length and distance codes at their boundaries. In DEFLATE, the length code for 258 is the last entry and carries no extra bits, while shorter lengths carry extra bits that extend a base value. An encoder that computes the code from the length with an off-by-one produces a stream that decodes to a different length, which shifts every subsequent match. The specification’s tables are the authority, and they are not regular enough to be regenerated from a formula.

The two families are not exclusive. DEFLATE is LZ77 with the token stream Huffman-coded, so the literals and the length and distance codes each get their own code table, and the compression comes from both the match substitution and the entropy coding. The Burrows–Wheeler transform is the alternative route to the same goal: instead of substituting matches, it rearranges the text so that an entropy coder sees long runs. bzip2 uses that route and no match substitution at all, and its decoder is correspondingly slower than a DEFLATE decoder because the inverse transform and the move-to-front stage are sequential.

A practical encoder therefore chooses between LZ77’s search cost and BWT’s sort cost. LZ77’s search can be bounded by a candidate limit and remains linear in the input; BWT’s sort is O(n log n) or O(n) but requires the whole block in memory and produces output only after the block is complete. For streams and for interactive use, the first wins; for archival compression of blocks, the second usually does.