LZW decompression

The decompressor receives only codes, no dictionary. It rebuilds the dictionary as it goes: every entry the compressor added, the decompressor adds one step later. That is nearly always enough. Once in a while a code arrives that the decompressor does not know yet, and it has to be deduced.

The algorithm

dictionary = every single symbol previous = dictionary[first code]; output previous for each following code k: if k is in the dictionary: entry = dictionary[k] otherwise (k is the next free number): entry = previous + first symbol(previous) ← KwKwK output entry add previous + first symbol(entry) to the dictionary previous = entry

The added entry is "previous sequence + first symbol of the current one". The compressor added exactly the same sequence, just one step earlier: at the moment when, after the previous sequence, it saw the symbol that starts the current one.

A trace of the example

Codes from compression: 0 1 2 4, alphabet A = 0, B = 1.

Code	Known?	Entry	Output	New dictionary entry
0	yes	A	A
1	yes	B	B	A + B = AB = 2
2	yes	AB	AB	B + A = BA = 3
4	no	AB + A = ABA	ABA	AB + A = ABA = 4

result: A B AB ABA = A B A B A B A

The KwKwK case

When code 4 arrives, the decompressor's dictionary ends at 3. Code 4 is precisely the entry the decompressor is about to add in this step. How can it know what is in it?

The compressor sent code 4 right after creating it. That can only happen when the data has the form K w K w K, where K is a symbol and w a sequence: K w is in the dictionary, the compressor adds K w K and uses it at once. So the new entry starts with the same symbol as the previous sequence, and equals:

entry = previous + first symbol(previous) here: previous = AB → entry = AB + A = ABA

Leaving this case out is the most common bug in home-made implementations. The decoder then works on most files and breaks on a few, usually those with long uniform areas, where the K w K w K pattern is frequent.

Code

// codes: array of codes, result: array of symbols
function lzwDecompress(codes, alphabetSize) {
  const dict = [];
  for (let i = 0; i < alphabetSize; i++) dict.push([i]);
  let prev = dict[codes[0]];
  const out = [...prev];
  for (const k of codes.slice(1)) {
    const entry = k < dict.length ? dict[k] : [...prev, prev[0]];   // KwKwK
    out.push(...entry);
    dict.push([...prev, entry[0]]);
    prev = entry;
  }
  return out;
}

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

Storing whole sequences in the dictionary is simple but uses a lot of memory. GIF decoders usually keep only the prefix code and the last symbol for each entry and rebuild the sequence backwards. The GIF details are on the LZW decompression in GIF page.