LZW Algorithm

Repeated sequences in lossless compression

Huffman coding shortens the representation of frequent symbols, but it mainly analyzes individual symbols. Data also contains repeated sequences, phrases, and patterns. In the sentence "The quick brown fox jumps over the lazy dog", the word "the" appears twice. Symbol coding uses the frequencies of t, h, and e, but it does not directly represent the repeated three-character sequence.

This form of redundancy is handled by dictionary-based compression. Subsequent occurrences of a sequence are replaced with a short code for its dictionary entry. Lempel-Ziv-Welch, or LZW, is one algorithm in this family. A code represents the complete sequence, so its length does not directly depend on the number of characters in the phrase it replaces.

The LZW algorithm and its adaptive dictionary

Terry Welch described LZW in 1984 as an extension of the earlier LZ78 algorithm by Abraham Lempel and Jacob Ziv. The encoder builds a dictionary of recurring phrases while reading the input. In a typical configuration, one pass is sufficient and the dictionary does not need to be included in the output. The decoder reconstructs it from the codes when it uses the same initial alphabet and code-assignment rules. Each new entry consists of a recognized sequence followed by the next character, so both sides create entries in the same order.

Core mechanism

LZW maintains a string table, or dictionary, that maps sequences to numeric codes. The steps are as follows.

1. Initialize the dictionary: The dictionary starts with the single-character strings of the input alphabet. For 8-bit data, it may contain 256 entries with codes from 0 through 255. A format may reserve some codes for control signals, so the details depend on the stream format.
2. Process the input stream: The algorithm reads the data character by character and searches for the longest sequence already in the dictionary. With repeated data, the recognized sequence can quickly contain several characters.
3. The main loop: Let the recognized sequence be P. After reading character C, the algorithm checks whether P + C is in the dictionary.
   • If yes: The algorithm replaces P with P + C and reads the next character.
   • If no: The combination is not yet in the dictionary. The algorithm performs two actions:
     1. It outputs the numeric code for the last known sequence, P.
     2. It adds P + C to the dictionary under the next available code.
4. Start the next sequence: The algorithm sets the single character C as the new P. The loop continues until the input stream ends. At end of input, the encoder outputs the code for the last non-empty sequence.

Example of LZW encoding

The following example applies the encoder to the string TOBEORNOTTOBEORTOBEORNOT.

The initial dictionary contains the input alphabet. New entries receive codes starting at 256. For clarity, only the characters used in this example are listed:

The table shows the successive encoder states.

Result: The 24-character string is represented by 16 output codes: [84, 79, 66, 69, 79, 82, 78, 79, 84, 256, 258, 260, 265, 259, 261, 263]. As the dictionary grows, repeated patterns receive codes for longer sequences. The code width is variable in this configuration. After the 9-bit range ends at 511, codes can use 10 bits. The table shows the beginning of the process; the listed sequence contains later entries created by the remaining input.

LZW decompression

The decoder receives the codes and starts with the same initial dictionary as the encoder. It reconstructs the text by outputting known sequences and inferring new dictionary entries from adjacent codes. The first code is handled as the initial sequence, and a new entry can be formed only after the next code arrives.

For each received code, the decoder outputs its current dictionary sequence. When a previous sequence and a next sequence exist, it creates a new entry by concatenating the previous sequence with the first character of the next sequence.

A special case, often called the KWKWK or string-table-string problem, occurs when the decoder receives the code for an entry it has not added yet. The encoder has created that sequence and used it immediately. The missing sequence is the previous sequence followed by its first character. This rule lets the decoder create the entry and keep the two dictionaries synchronized. In formats with a clear code, receiving it restores the initial dictionary and limits the effect of lost synchronization.

Application: the GIF format

LZW is part of the GIF (Graphics Interchange Format), which stores image data as palette indices. The format has properties that suit dictionary compression.

• Limited color palette: A GIF image can contain at most 256 colors. LZW processes palette indices of up to 8 bits, so the initial alphabet is small and fixed. GIF data also defines a clear code and an end-of-information code; the compression code width starts at the initial code size plus one and grows to a maximum of 12 bits. The clear code can occur within image data, while the end-of-information code terminates the sequence.
• Spatial redundancy: Computer-generated images such as logos and diagrams often contain solid regions or repeating patterns. Reading them row by row produces repeated index sequences that LZW can replace with dictionary entries.

LZW properties and limitations

LZW remains an example of adaptive dictionary compression. Its usefulness depends on the data and on the stream parameters.

Advantages

• One pass: The encoder does not need to analyze the whole file before starting. It extends the dictionary while reading, which suits streaming processing.
• No dictionary transmission: With matching initial parameters, the decoder can rebuild the dictionary from the codes, so the full table need not be sent.
• Simple implementation: The procedure is straightforward, and decoding requires relatively few operations.

Limitations

• Full dictionary: The dictionary limit depends on the format. A stream using 12-bit codes can hold 4096 entries. Once the limit is reached, an implementation may stop adding entries, clear the dictionary, or use another rule, which affects compression. The 4096-entry limit applies to a configuration with at most 12-bit codes, not to every LZW implementation.
• Error sensitivity: A bit error can make the decoder and encoder dictionaries diverge. The damage may propagate until a clear code or another resynchronization mechanism is received.
• Patent history: LZW was covered by patents for many years, including patents held by Unisys. Licensing disputes affected software using GIF and LZW. PNG uses Deflate, a combination of LZ77 and Huffman coding.

The main LZW patents have expired. Deflate and newer LZ variants are used in many current applications, and the adaptive dictionary mechanism remains a useful example of lossless compression.