LZW Compression: Dictionary-Based Encoding and Decoding Explained

Have you ever wondered how GIF images or Unix 'compress' achieve such small file sizes? The secret lies in LZW (Lempel-Ziv-Welch) compression, a dictionary-based lossless algorithm that adapts to the data it compresses. Unlike fixed-dictionary methods, LZW builds its dictionary on the fly, encoding repeated patterns as single codes. This makes it incredibly effective for text and images with repetitive content.

In this tutorial, you'll learn the inner workings of LZW compression and decompression, with production-ready Python code. We'll walk through a real-world bug that caused data corruption, provide a debugging guide for production issues, and cover common mistakes. By the end, you'll be able to implement LZW and understand its trade-offs.

LZW is a cornerstone of data compression, and mastering it will deepen your understanding of adaptive algorithms. Let's dive in!

How LZW Compression Works

LZW compression builds a dictionary of substrings encountered during encoding. Initially, the dictionary contains all single characters (e.g., 0-255 for bytes). The encoder reads input character by character, building a current string. As long as the current string is in the dictionary, it continues reading. When the next character would make a string not in the dictionary, it outputs the code for the current string, adds the new string (current + next char) to the dictionary, and resets the current string to the next character.

This adaptive approach allows LZW to learn longer and longer patterns, achieving high compression ratios on repetitive data. The dictionary grows until a predefined maximum size (e.g., 4096 entries for 12-bit codes). After that, the encoder may stop adding new entries or reset the dictionary.

Let's look at a simple example with a string 'ABABABA'. Initial dictionary: A=0, B=1. Encoder steps: - Read A (current='A', in dict). Read B: 'AB' not in dict -> output 0, add 'AB'=2, current='B'. - Read A: 'BA' not in dict -> output 1, add 'BA'=3, current='A'. - Read B: 'AB' in dict -> current='AB'. Read A: 'ABA' not in dict -> output 2, add 'ABA'=4, current='A'. - Read B: 'AB' in dict -> current='AB'. Read A: 'ABA' in dict -> current='ABA'. End of input -> output 4. Output codes: 0,1,2,4. Original length 7, compressed to 4 codes (assuming fixed-width codes).

def lzw_compress(data: bytes, max_dict_size: int = 4096) -> list:
    # Build initial dictionary of single bytes
    dictionary = {bytes([i]): i for i in range(256)}
    next_code = 256
    current = b''
    result = []
    for byte in data:
        new_current = current + bytes([byte])
        if new_current in dictionary:
            current = new_current
        else:
            result.append(dictionary[current])
            if next_code < max_dict_size:
                dictionary[new_current] = next_code
                next_code += 1
            current = bytes([byte])
    if current:
        result.append(dictionary[current])
    return result

LZW Decompression: Rebuilding the Dictionary

LZW decompression reconstructs the original data from the compressed codes. It starts with the same initial dictionary (single bytes). It reads codes one by one. For each code, it outputs the corresponding string from the dictionary. Then it updates the dictionary by adding the previous string plus the first character of the current string. This is the classic LZW decoding algorithm.

A special case occurs when the decoder encounters a code that is not yet in the dictionary. This happens when the encoder added a new entry and immediately used it. The decoder can handle this by using the previous decoded string plus its first character.

Example: Decoding codes [0,1,2,4] from earlier. - Code 0 -> output 'A', prev='A'. Next code 1 -> output 'B', add 'A'+'B'='AB'=2, prev='B'. - Code 2 -> output 'AB', add 'B'+'A'='BA'=3, prev='AB'. - Code 4 -> not in dict yet (next code is 4). Use prev='AB' + first char of prev='A' -> 'ABA'=4. Output 'ABA', add 'AB'+'A'='ABA'=4, prev='ABA'. Output: 'A','B','AB','ABA' -> 'ABABABA'.

def lzw_decompress(codes: list, max_dict_size: int = 4096) -> bytes:
    # Build initial dictionary (reverse mapping)
    dictionary = {i: bytes([i]) for i in range(256)}
    next_code = 256
    result = []
    prev = dictionary[codes[0]]
    result.append(prev)
    for code in codes[1:]:
        if code in dictionary:
            current = dictionary[code]
        else:
            # Special case: code equals next_code
            current = prev + prev[:1]
        result.append(current)
        if next_code < max_dict_size:
            dictionary[next_code] = prev + current[:1]
            next_code += 1
        prev = current
    return b''.join(result)

Handling Dictionary Overflow and Reset

In practice, the dictionary cannot grow indefinitely. A maximum size is set, typically 4096 entries (12-bit codes) or 65536 (16-bit). When the dictionary reaches its maximum, the encoder must decide what to do. Common strategies: 1. Stop adding new entries: The dictionary becomes static. Compression may degrade for new patterns. 2. Reset the dictionary: Clear all entries except the initial 256 single-byte codes. This allows the algorithm to adapt to new data but loses learned patterns. 3. LRU eviction: Remove least recently used entries, but this adds complexity.

In many implementations (e.g., GIF), the dictionary is reset when full. A special 'clear code' (often 256) is inserted into the output stream to signal the decoder to reset its dictionary. This ensures both encoder and decoder stay synchronized.

Let's implement a version with reset support.

def lzw_compress_with_reset(data: bytes, max_dict_size: int = 4096, clear_code: int = 256) -> list:
    dictionary = {bytes([i]): i for i in range(256)}
    next_code = 257  # after clear code
    current = b''
    result = []
    for byte in data:
        new_current = current + bytes([byte])
        if new_current in dictionary:
            current = new_current
        else:
            result.append(dictionary[current])
            if next_code < max_dict_size:
                dictionary[new_current] = next_code
                next_code += 1
            else:
                # Dictionary full: emit clear code and reset
                result.append(clear_code)
                dictionary = {bytes([i]): i for i in range(256)}
                next_code = 257
            current = bytes([byte])
    if current:
        result.append(dictionary[current])
    return result

Variable-Length Codes and Bit Packing

LZW codes are often stored as variable-length binary strings to save space. Initially, codes are 9 bits (since we have 256+2 codes). As the dictionary grows, the code width increases up to a maximum (e.g., 12 bits). This requires careful bit packing.

For simplicity, many tutorials use fixed-width codes (e.g., 12 bits), but that wastes space for small dictionaries. In production, you'll need to implement a bitstream that writes codes with varying bit lengths.

Here's a simple bit packing approach: start with 9 bits, and when the next code exceeds the current maximum representable value, increase the bit width by 1. The decoder must track the same bit width changes.

Example: Initial max code = 257 (9 bits). When next_code reaches 512, switch to 10 bits, etc.

def write_codes(codes: list, max_bits: int = 12) -> bytes:
    # Simplified: pack codes into bytes using variable bit length
    # Start with 9 bits, increase as needed
    bit_width = 9
    max_code = (1 << bit_width) - 1
    buffer = 0
    bits_in_buffer = 0
    output = []
    for code in codes:
        # Increase bit width if necessary
        while code > max_code and bit_width < max_bits:
            bit_width += 1
            max_code = (1 << bit_width) - 1
        buffer = (buffer << bit_width) | code
        bits_in_buffer += bit_width
        while bits_in_buffer >= 8:
            bits_in_buffer -= 8
            output.append((buffer >> bits_in_buffer) & 0xFF)
    if bits_in_buffer > 0:
        output.append((buffer << (8 - bits_in_buffer)) & 0xFF)
    return bytes(output)

Real-World Applications and Trade-offs

LZW is a great educational tool for understanding adaptive dictionary compression. For new projects, consider using DEFLATE or LZMA, but LZW's simplicity makes it a classic.

Performance Analysis and Optimization

LZW compression time is O(n) where n is input length, assuming dictionary lookup is O(1) (hash table). Decompression is also O(n). Memory is O(dictionary size).

Example: Using a trie for dictionary can improve speed for long matches.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.code = None

def lzw_compress_trie(data: bytes, max_dict_size: int = 4096) -> list:
    root = TrieNode()
    for i in range(256):
        node = TrieNode()
        node.code = i
        root.children[i] = node
    next_code = 256
    current = root
    result = []
    for byte in data:
        if byte in current.children:
            current = current.children[byte]
        else:
            result.append(current.code)
            if next_code < max_dict_size:
                new_node = TrieNode()
                new_node.code = next_code
                current.children[byte] = new_node
                next_code += 1
            current = root.children[byte]
    if current is not root:
        result.append(current.code)
    return result