Lempel-Ziv Coding

Lempel-Ziv (LZ) coding is a class of universal lossless compression algorithms that do not require prior knowledge of source statistics. Unlike Huffman or Shannon-Fano coding, which need a probability model of the source, LZ coding builds a dictionary dynamically from the input data itself. This makes it applicable to arbitrary data sources, including text, binary files, and communication streams, without any training phase.

Core Concept Explanation

The central idea in all Lempel-Ziv variants is dictionary-based compression. Instead of assigning shorter codes to more frequent individual symbols as Huffman does, LZ coding finds repeated patterns or phrases in the data and replaces them with shorter references to previously seen occurrences. The dictionary is not fixed before encoding: it is built incrementally as the encoder reads the input, so the same algorithm works for any source without needing to know its statistics in advance.

There are two main families. LZ77 (Lempel and Ziv, 1977) uses a sliding window over the recent past as its implicit dictionary. When a match is found between the current input and a substring in the window, it encodes the match as a triple (offset from current position, match length, next non-matching character). The decompressor maintains the same window and reconstructs the original string using the offsets and lengths.

LZ78 (Lempel and Ziv, 1978) uses an explicit, incrementally built dictionary. Each new entry is formed by taking the longest phrase already in the dictionary that matches the current input and appending the next symbol. The encoder outputs the dictionary index of the matched phrase plus the new symbol. The decompressor builds the same dictionary synchronously, so no dictionary needs to be transmitted. LZW (Lempel-Ziv-Welch, 1984) is a refinement of LZ78 that initializes the dictionary with all single-character entries and omits the extra symbol from the output, improving compression ratio further.

Mathematical Expression

LZ coding is provably asymptotically optimal: as the input sequence length n grows to infinity, the compression ratio achieved by LZ coding converges to the entropy rate H_inf of the source. This is a remarkable result because it holds without any knowledge of the source distribution. Formally, if R_n is the average number of bits per symbol used by LZ coding on a sequence of length n, then lim_{n->inf} R_n = H_inf. This property is called universality.

For LZW, the number of bits used per codeword grows as the dictionary fills: early codewords may use 9 bits (when the dictionary has up to 512 entries) and later codewords use more bits as the dictionary grows. The compression ratio is defined as the ratio of the uncompressed size to the compressed size. For a string with many repetitions, LZW achieves high compression ratio because long repeated substrings get replaced by short dictionary codes.

Practical Understanding

LZ77 is the foundation of DEFLATE, which is used inside ZIP files, PNG images, gzip, and HTTP content encoding. The sliding window approach is memory-efficient and suitable for streaming applications where the entire input is not available before compression begins. The window size is a tunable parameter: larger windows find longer matches and improve compression but require more memory and computation.

LZW was used in early GIF image compression and in telecommunications modems (V.42bis standard). It fell out of favor for image compression after patent issues in the 1990s, but the underlying algorithm remains important in networking and storage. Modern compressors like Zstandard and Brotli use LZ-based matching as a core stage, combined with entropy coding (Huffman or Asymmetric Numeral Systems) on the match lengths and offsets to get even better compression.

One important distinction from statistical coders like Huffman is that LZ compression is adaptive: the encoder and decoder build the same model (the dictionary) from the data itself as they process it. This means LZ coding can handle non-stationary sources where symbol statistics change over time, which makes it more robust in practice than Huffman coding applied to the entire file with a fixed global probability table.

Given:
Input string to compress using LZW algorithm:
Input: ABABABAB
Initial dictionary: {A=256 (reuse single char), actually LZW starts with entries for A(65) and B(66) in ASCII}
For simplicity use: A=1, B=2 as initial entries.

Why this formula applies:
LZW builds the dictionary by extending the longest matching prefix with the next symbol.
Encoder outputs dictionary code for matched phrase.

LZW Encoding trace:
Step 1: Read A -> matches entry 1 -> buffer = A
Step 2: Read B -> AB not in dict -> output code 1 (A), add AB=3 to dict, buffer = B
Step 3: Read A -> BA not in dict -> output code 2 (B), add BA=4 to dict, buffer = A
Step 4: Read B -> AB IS in dict (entry 3) -> buffer = AB
Step 5: Read A -> ABA not in dict -> output code 3 (AB), add ABA=5 to dict, buffer = A
Step 6: Read B -> AB IS in dict (entry 3) -> buffer = AB
Step 7: Read A -> ABA IS in dict (entry 5) -> buffer = ABA
Step 8: Read B -> ABAB not in dict -> output code 5 (ABA), add ABAB=6 to dict, buffer = B
Step 9: End of input -> output code 2 (B)

Substitution:
Original: 8 symbols, assuming 8 bits each = 64 bits uncompressed
Encoded output codes: [1, 2, 3, 5, 2] = 5 codes

Calculation:
With 9-bit codes (dict up to 512 entries):
Compressed = 5 * 9 = 45 bits
Compression ratio = 64 / 45 = 1.42

Final Answer: Compression ratio = 1.42 (42% size reduction)
The repetitive ABAB pattern enables dictionary reuse and drives compression gain.

Exam Tip: LZ coding is universal — it achieves the entropy rate of any stationary ergodic source asymptotically without needing to know source statistics. GATE may contrast LZ coding with Huffman by asking which method is adaptive and which requires a pre-specified probability model. LZW is adaptive and model-free; Huffman requires known probabilities. Also remember that LZ compression ratio improves significantly with longer input sequences due to the growing dictionary.

LZW Algorithm Mechanism

• LZ coding is universal: no prior knowledge of source statistics is needed. The dictionary is built adaptively from the input itself.
• LZ77 uses a sliding window over recent past data as its implicit dictionary. Output is (offset, length, next symbol) triples.
• LZ78 and LZW build an explicit dictionary. Each new entry is the longest matched phrase plus one new symbol. Output is a dictionary index code.
• LZW initializes the dictionary with all single-character entries. The decompressor builds the same dictionary synchronously without it being transmitted.
• Compression ratio improves with input length and repetitiveness. LZ compression is less effective on already-random or encrypted data.
• LZ coding achieves the entropy rate asymptotically (universality theorem), making it theoretically optimal in the limit of long sequences.
• Practical applications: LZ77 in DEFLATE (ZIP, gzip, PNG); LZW in GIF, TIFF, V.42bis; modern systems combine LZ matching with arithmetic or Huffman coding.

Quick Revision

• LZ coding is dictionary-based and adaptive: no pre-specified probability model needed. Works on any source.
• LZ77: sliding window dictionary, output = (offset, length, next char). Used in DEFLATE, ZIP, PNG, gzip.
• LZ78/LZW: explicit dictionary, output = dictionary index. LZW initializes with single characters. Used in GIF, V.42bis.
• Universality: LZ compression ratio approaches the source entropy rate H_inf as input length n grows to infinity.
• LZW trace: longest match in dictionary + new symbol creates a new entry. Decoder builds identical dictionary without transmission.
• Compression ratio = uncompressed size / compressed size. Improves with repetitive inputs and longer sequences.
• Exam trap: LZ coding does NOT require source statistics unlike Huffman coding. It is the key reason LZ is preferred for general-purpose compression where source statistics are unknown or change over time.