How LZW Compression Works in GIF Files

The Graphics Interchange Format (GIF) relies on the Lempel-Ziv-Welch (LZW) lossless compression algorithm to reduce image sizes without sacrificing visual quality. This article breaks down how LZW functions within the GIF standard, examining how it transforms raw streams of pixel color indices into compact, variable-length codes using a dynamic dictionary. By understanding this process, you will see how repetitive color patterns are identified and encoded to achieve efficient file storage.

Pixel Stream Preparation

A GIF image does not store direct RGB color values for every pixel. Instead, it utilizes an indexed color palette containing up to 256 distinct colors (an 8-bit palette). Each pixel in the raster graphic is represented by an index pointing to a specific color entry in this palette. Before LZW compression begins, the image is flattened into a one-dimensional stream of numeric color indices, usually reading left-to-right and top-to-bottom across the pixel grid.

Initializing the LZW Dictionary

The core of the LZW algorithm is a string-translation table known as the dictionary or code table. Unlike static compression formats, the GIF file does not need to store this dictionary; both the compressor and decompressor construct identical tables on the fly.

1. Root Codes: The dictionary is initialized with entries for all individual possible pixel indices. If an image uses a 4-color palette (2-bit), the root dictionary contains codes for indices 0, 1, 2, and 3.
2. Special Control Codes: Two special codes are appended directly after the root entries:
   • Clear Code (CC): Signals the decoder to reset the dictionary back to its initial state.
   • End of Information (EOI): Indicates the termination of the compressed pixel data stream.
3. Available Entries: New entries generated by the algorithm are assigned the next available integers following the EOI code.

The Compression Loop

The algorithm searches for repeating patterns of color indices, replacing multi-pixel sequences with single integer codes:

1. Initialize Buffer: Read the first pixel index from the stream and store it in an internal buffer, variable \(P\).
2. Read Next Pixel: Fetch the next pixel index, variable \(K\), from the stream.
3. Pattern Check:
   • If the combined string \(P + K\) already exists in the dictionary, set \(P = P + K\) (extend the sequence) and repeat step 2.
   • If \(P + K\) is not in the dictionary, output the established code for \(P\) to the compressed stream. Then, insert the new sequence \(P + K\) into the dictionary as the next sequential code entry. Finally, reset \(P = K\).
4. Final Flush: When the end of the pixel stream is reached, output the remaining code stored in \(P\), followed by the EOI code.

Through this loop, single-color spans and repeating multi-color patterns are mapped to newly generated codes. Subsequent occurrences of those identical patterns can then be transmitted using only a single dictionary code.

Variable-Length Code Size

GIF LZW optimizes data density further by varying the bit length of the output codes as the dictionary grows:

• Compression starts with a bit width defined as the image's base color bit-depth plus one (to accommodate the Clear and EOI codes). For an 8-bit image, the initial code width is 9 bits.
• As entries are added to the dictionary and code values cross binary power boundaries (such as code 512 or 1024), the code size increments by 1 bit (e.g., from 9 bits to 10 bits).
• The maximum code length permitted in the GIF specification is 12 bits, capping the dictionary at 4,096 total entries.

The Clear Code and Memory Limits

Once the dictionary fills all 4,096 positions (entries 0 through 4095), the encoder can no longer add new sequences. To maintain high compression ratios on changing image data, the encoder outputs the Clear Code. Both the encoder and the decoder immediately wipe all dynamically generated sequences from memory, restore the base root codes, reset the code size back to its original bit width, and begin rebuilding patterns from scratch.

Symmetric Decompression

LZW compression enables high-speed decoding because the decoder reads the exact same sequence of transmitted codes, looks up the corresponding pixel chains, and rebuilds the identical dictionary entries without requiring pattern tables to be packaged within the GIF container.