Dictionary Compression

Repeated sequences in dictionary compression

Statistical methods such as Huffman coding use the frequency of individual symbols. Data also contains repeated sequences, phrases, and byte patterns. A dictionary coder represents these fragments as references to earlier occurrences. A dictionary can be explicit, storing phrases under indexes, or implicit, using the recent stream as history. A reference saves space only when its encoded cost is lower than writing the fragment.

Consider a text file containing: "The quick brown fox jumps over the lazy dog." A statistical coder may assign short codes to frequent characters such as 'o' and the space. A separate saving comes from the repeated word "the". Its second occurrence can be represented as "repeat the earlier fragment". This idea is the basis of dictionary-based compression. The family includes algorithms developed by Jacob Ziv and Abraham Lempel in the 1970s. Its variants are used in formats such as ZIP and GZIP, while DEFLATE is also used by PNG.

For a short record, the reference cost can exceed the saving.

The LZ77 algorithm and the sliding window

Published in 1977, LZ77 is the first of the two works by Ziv and Lempel from which the LZ family developed. Instead of storing a complete explicit dictionary of phrases, it uses a continuously updated history of recently processed data.

The sliding-window mechanism

The algorithm uses a sliding window, a bounded area containing history and data waiting to be coded. The window has two parts. Its size determines the maximum backward distance, while the look-ahead size limits the match considered:

• Search buffer: This is the history, or implicit dictionary. It has a fixed size, for example a few kilobytes, and contains recently encoded data. The coder searches it for repeated sequences.
• Look-ahead buffer: This smaller buffer contains the next fragment waiting to be encoded. The coder takes symbols from it and searches for a match in the search buffer.

The LZ77 encoding process

Encoding proceeds in a repeated loop:

1. The algorithm examines the symbols at the beginning of the look-ahead buffer.
2. It searches the search buffer for the longest match for the sequence beginning in the look-ahead buffer. The search strategy depends on the implementation.
3. Based on the search result, it makes a decision and outputs one of two types of tokens:
   • No useful match: When no match exists or the match is shorter than a threshold such as 3 characters, the coder emits a literal token. The token contains an input symbol and, in many formats, a marker that distinguishes it from a reference. The threshold avoids references whose representation would be longer than the literal.
   • A match is found: The coder emits a pointer token referring to the history. A typical representation contains a marker, an offset or distance, and a length. For example: $(0, \text{distance}, \text{length})$.
     • The distance indicates how many bytes to go back into the search buffer to find the start of the match.
     • The length indicates how many bytes to copy from that point.
4. Finally, the algorithm slides the window forward. It moves the processed data, either a literal or a matched sequence of length $L$, into the history and reads new input into the look-ahead buffer. The process repeats.

Overlapping matches

LZ77 can represent a long repetition with one reference. Consider "abababababab". After the initial "ab" is in the history, the look-ahead buffer contains "ababababab". The coder can refer 2 bytes backward and specify a length of 10 bytes.

The LZ77 decoder copies a match sequentially. It goes back 2 bytes, copies 'a', then 'b'. Before the third byte is copied, the first 'a' is already part of the history and can be used again. This overlap lets one short pointer reconstruct a long run.

Decompression

The decoder maintains a search buffer containing data already written to the output. When it receives a token, it performs one of two operations:

• For a literal token, it appends the symbol to the output.
• For a pointer token (distance, length), it moves back by the given distance and copies the given length, including when source and destination overlap.

Decoding mainly uses history references and data copies. This simple decoder path is one reason LZ77-based schemes are used widely. A decoder still has to check distance, length, and buffer bounds so it can reject a damaged token.

The LZ78 and LZW family with an explicit dictionary

LZ78, published in 1978, and LZW (Lempel-Ziv-Welch, developed in 1984) use an explicit phrase table. Unlike LZ77, their references point to dictionary entries maintained by the encoder and decoder. Entries are added in the same order at both ends, while a format may limit code width or periodically reset its dictionary.

The LZW mechanism. Building and referencing entries

The LZW procedure consists of initialization, phrase search, and dictionary updates:

1. Initialization: LZW starts with a dictionary containing all single-character symbols.
2. Building phrases: It reads the input and finds the longest sequence of characters present in the dictionary.
3. Output and update: It emits the dictionary code for the longest sequence, then adds a new entry consisting of that sequence and the next input character.

LZ77 and LZW. Different reference models

Both are dictionary coders, while their references differ. LZ77 replaces repetitions with a (distance, length) pointer into the history. LZW emits an integer code that refers to an entry in an explicit phrase dictionary. LZW benefits from recurring multi-character phrases, while LZ77 can find local matches that do not form fixed words.

Modern hybrids

Modern general-purpose lossless compressors often combine dictionary matching with entropy coding. One stage describes repetition, while the other assigns shorter codes to frequent literals and match parameters.

DEFLATE in ZIP, GZIP, and PNG

DEFLATE combines LZ77-style matching with Huffman coding. ZIP can store a DEFLATE stream, GZIP wraps such a stream in the gzip format, and PNG uses a zlib stream with Deflate compression for image data.

1. Stage 1. LZ77 matching: The coder scans data with a maximum backward distance of 32 KiB and replaces repeated strings with (length, distance) pointers. A character without a useful match is emitted as a literal.
2. Stage 2. Huffman coding: The first-stage output contains literals and length-distance pairs. DEFLATE codes literals and lengths with one Huffman tree and distances with a second tree. In a dynamic block, the trees are described in the stream so code lengths can follow element frequencies.

The first stage removes structural repetition, while the second reduces the cost of frequent literals and references. This division explains how DEFLATE combines both coding methods. The stream is divided into blocks. A block can be stored without compression, use fixed Huffman codes, or carry a description of dynamic Huffman trees. The format limits backward distance, so farther repetitions are handled in later blocks or emitted as literals.

LZ4 and the speed priority

Match search and tree construction in DEFLATE can increase encoding cost. Applications handling large in-memory datasets may prioritize decoder throughput. LZ4 was designed with simple processing and speed as priorities.

LZ4 is an LZ77 variant with a simple block format and a short decoding path. Implementations may use a hash table to find candidate matches instead of scanning the whole buffer. This commonly gives a lower ratio than size-oriented methods with short decompression time. LZ4 is used in databases, file systems such as ZFS, and game-asset loading. The LZ4 block format and LZ4 frame format are separate layers. A frame can carry content size, checksums, and block information, while a block describes literals and copy operations. A network stream also has to carry block boundaries and the information required by the decoder. LZ77 and LZ4 do not define one universal container for every use, so the frame format matters for portability. LZ78 represents entries as an index and a symbol, whereas LZW emits indices after extending its table. All of these schemes require the encoder and decoder to maintain compatible dictionary state. If the window or code width changes, the decoder must read the setting from a header or receive it from the stream context. This metadata overhead matters for short fragments. Match selection affects the number of references and the search cost during encoding, so it should be evaluated together with decoding time. A decoder can reconstruct entries in the same order only when the reset rules and initial dictionary are identical. In DEFLATE, block type and tree descriptions are part of the stream, so a decoder can select the proper Huffman tables. LZ4 keeps the block grammar small, but its frame still determines content-size and checksum handling. These details explain why a benchmark should identify the exact container, implementation, and settings. They also affect interoperability across tools.