How LZW Encodes Color Indices in GIF Files

The Graphics Interchange Format (GIF) achieves compact file sizes by decoupling pixel geometry from 24-bit RGB values through an indexed color model and compressing the resulting index data with the Lempel-Ziv-Welch (LZW) algorithm. Instead of processing red, green, and blue values directly, the LZW algorithm operates entirely on a stream of integer pointers that reference an external color palette. This article explains the technical pipeline of how GIF structures its color palette, generates index streams, and applies LZW dictionary encoding to those indices.

The Indexed Color Palette Foundation

A standard RGB image requires 24 bits (3 bytes) per pixel—one byte each for red, green, and blue channels. GIF reduces this overhead by restricting each frame to a maximum of 256 colors (an 8-bit color depth).

Before any compression occurs, the GIF encoder analyzes the image and builds a Color Table (either a Global Color Table for the entire file or a Local Color Table for an individual frame). The Color Table is an array of RGB triplets:

By establishing this lookup table, the raw pixel canvas ceases to be an array of multi-byte color values and becomes an array of single-byte indices pointing to entries in the Color Table.

The Index Stream Generation

The image raster data is converted into a linear sequence of index numbers read row-by-row, from top-left to bottom-right. For example, a horizontal line of alternating black and white pixels is represented not as (0,0,0), (255,255,255), (0,0,0), (255,255,255), but as the index sequence:

1, 0, 1, 0

This stream of integer indices serves as the raw input data for the LZW compression stage.

LZW Dictionary Initialization

The GIF specification uses a modified version of LZW that dynamically creates a dictionary of recurring patterns. The initial state of the dictionary is determined by the image's color depth, defined by the "LZW Minimum Code Size."

If an image uses 4 distinct colors, the minimum code size is 2 bits (\(2^2 = 4\)). The dictionary initializes with:

Any subsequent dictionary entry created during compression begins at index code 6. For an 8-bit image, codes 0 to 255 represent raw indices, code 256 is the Clear Code, code 257 is the EOI Code, and pattern codes begin at 258.

Pattern Matching and Output Encoding

Once initialized, the LZW encoder reads the incoming index stream one token at a time:

  1. Prefix Matching: The encoder reads an index and checks whether the current sequence (prefix + current index) already exists in the dictionary.
  2. Dictionary Expansion: When it encounters an index sequence not present in the dictionary, it outputs the code for the existing prefix to the bitstream. It then assigns a new code number to the combined sequence (prefix + new index) and inserts it into the dictionary.
  3. Reset Prefix: The newly encountered index becomes the starting point (prefix) for the next sequence evaluation.

Through this process, repeated sequences of color indices—such as solid background areas or recurring dither patterns—are replaced by single variable-length codes.

Decompression and Rendering

During decompression, the GIF decoder initializes the exact same default dictionary based on the Color Table size. As it unpacks the variable-length bitstream, it resolves the LZW codes back into sequences of single indices while reconstructing the dictionary simultaneously.

Finally, the decoder passes the reconstituted index stream to the display pipeline. The display engine uses each index to query the Color Table, retrieve the actual 24-bit RGB values, and render the final pixels on screen. At no point does the LZW algorithm process or store RGB data directly; it operates entirely as an abstraction layer over the index array.