LZW compression

An LZW compressor keeps one current sequence w and extends it with the next symbols as long as the result is in the dictionary. When it is not, it outputs the code of w, adds the new sequence to the dictionary and starts again from the last symbol. The general description is on the LZW algorithm page.

The algorithm

dictionary = every single symbol, numbered from 0 w = "" (empty sequence) for each symbol c in the data: if w + c is in the dictionary: w = w + c otherwise: output code(w) add w + c to the dictionary under the next free number w = c at the end: output code(w)

A trace of the example

Alphabet A = 0, B = 1. Data: A B A B A B A.

Step	w	c	w + c in dictionary?	Code output	New entry
1	""	A	yes (A)
2	A	B	no	0 (A)	AB = 2
3	B	A	no	1 (B)	BA = 3
4	A	B	yes (AB)
5	AB	A	no	2 (AB)	ABA = 4
6	A	B	yes (AB)
7	AB	A	yes (ABA)
end	ABA			4 (ABA)

output: 0 1 2 4

Note step 7: the entry ABA = 4 was created in step 5 and already used in step 7. So the compressor outputs code 4 right after creating it. That is exactly the case that needs special handling in decompression.

How much it saves

On short data, not much: 7 symbols become 4 codes, but the codes need more bits than the symbols because the dictionary grows. The gain shows on long, repetitive data. For the classic example TOBEORNOTTOBEORTOBEORNOT (24 characters, a 6-letter alphabet) LZW produces 16 codes. For an image with large areas of a single color, one code often covers dozens of pixels.

The dictionary in practice

The "is w + c in the dictionary" lookup has to be fast. Usually whole sequences are not stored; instead pairs (prefix code, symbol) go into a hash table: the sequence w + c is simply (code(w), c). Each step is then one table lookup, whatever the sequence length.

Code

// data: array of symbols 0..alphabetSize-1, result: array of codes
function lzwCompress(data, alphabetSize) {
  const dict = new Map();                 // key "prefix,symbol" → code
  let next = alphabetSize;
  let w = -1;                             // code of current sequence, -1 = empty
  const out = [];
  for (const c of data) {
    if (w === -1) { w = c; continue; }
    const key = w + ',' + c;
    if (dict.has(key)) { w = dict.get(key); continue; }
    out.push(w);
    dict.set(key, next++);
    w = c;
  }
  if (w !== -1) out.push(w);
  return out;
}

lzwCompress([0, 1, 0, 1, 0, 1, 0], 2);   // [0, 1, 2, 4]

GIF adds variable-width codes, "clear" and "end" codes and bit packing into bytes on top of this. See LZW compression in GIF.