How LZW Compresses Horizontal Patterns in GIF

This article examines how the Lempel-Ziv-Welch (LZW) algorithm efficiently compresses horizontal patterns in Graphics Interchange Format (GIF) images. By linearizing two-dimensional pixel arrays into a one-dimensional data stream via raster scanning, GIF transforms adjacent horizontal pixels into contiguous repeating sequences. LZW exploits this structure using deterministic prefix extension, dynamically building a dictionary where repeated sub-sequences collapse into single tokens, reducing redundant horizontal data at an amortized sub-linear rate.

Raster Scanning and Linear Data Representation

GIF stores image data using row-major raster order, reading pixels sequentially from left to right, top to bottom. Because the scan traverses horizontally, any row with uniform colors or repeating horizontal designs produces long, consecutive runs of identical symbols or repeating periodic patterns in the resulting one-dimensional byte stream.

The Prefix Extension Property

The primary mathematical property underpinning LZW’s efficiency is the prefix property of formal languages, implemented via dynamic dictionary parsing.

LZW operates on strings over an alphabet \(\Sigma\). The algorithm maintains an internal dictionary initialized with every individual symbol of \(\Sigma\) (representing palette indices in a GIF). Compression relies on the invariant of prefix closure:

1. Let \(w\) be the longest string currently matching an entry in the dictionary.
2. Read the next incoming character \(c\).
3. Check if the concatenated string \(w \cdot c\) exists in the dictionary.
4. If \(w \cdot c\) is not in the dictionary, output the integer code for \(w\), add \(w \cdot c\) to the dictionary, and reset the search prefix to \(c\).

Because every newly registered dictionary string is an extension of an existing prefix by exactly one character (\(|w \cdot c| = |w| + 1\)), the dictionary naturally forms a prefix tree (trie).

Quadratic Growth in Redundant Sequences

When a GIF encounters horizontal runs of a uniform pixel value \(A\), the input stream presents a run of length \(N\):

\[S = A^N\]

Because of the prefix extension rule, LZW progressively registers patterns of increasing length:

• Step 1 registers \(AA\) (length 2)
• Step 2 registers \(AAA\) (length 3)
• Step 3 registers \(AAAA\) (length 4)
• Step \(k\) registers \(A^{k+1}\) (length \(k+1\))

The sum of the lengths of the parsed tokens forms an arithmetic progression:

\[\sum_{i=1}^{k} i = \frac{k(k + 1)}{2} \approx N\]

Consequently, encoding an unbroken horizontal line of \(N\) identical pixels requires only \(k \approx \sqrt{2N}\) output codes. The raw sequence size \(O(N)\) is compressed into \(O(\sqrt{N})\) dictionary indices, resulting in significant data reduction for solid horizontal fills.

Exploitation of Horizontal Periodicity

Horizontal dithering or alternating patterns yield periodic sequences where \(f(x) = f(x + T)\), with \(T\) representing the period length (e.g., alternating pixels \(ABABAB\)).

Because LZW does not require symbols to be identical—only that the sequence of symbols repeats—the prefix extension property treats multi-byte cycles identically to single-byte runs. Once the dictionary learns the sequence corresponding to the period \(T\), subsequent occurrences of \(T\) are merged into larger multiples (\(2T, 3T, \dots\)), yielding the same square-root token reduction over sustained periodic horizontal scans.