LZW dictionary decoding: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Rebuild the dictionary from previous phrases, including the code-equals-next-entry special case.

Decode each known phrase and append the previous phrase plus the first character of the current phrase to the dictionary. If the next code equals the next unused code, reconstruct it as previous phrase plus its first character.

Open the 3D visualization

LZW dictionary decoding example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use LZW dictionary decoding

Reconstructing an LZW integer code stream while rebuilding the encoder dictionary.

Choosing an alternative

The encoder searches for known phrase extensions. The decoder knows phrase boundaries from codes and follows prefix/suffix chains to recover characters.

Worked example: input and state changes

Example input

0,1,26,28,27,27

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Initialize dictionary codes 0..25 for a..z.

    State at this checkpoint
    {
      "values": [
        "Read: ",
        "Pending: ",
        "Output: ",
        "0: a",
        "1: b",
        "2: c",
        "3: d",
        "4: e",
        "5: f",
        "6: g",
        "7: h",
        "8: i",
        "9: j",
        "10: k",
        "11: l",
        "12: m",
        "13: n",
        "14: o",
        "15: p",
        "16: q",
        "17: r",
        "18: s",
        "19: t",
        "20: u",
        "21: v",
        "22: w",
        "23: x",
        "24: y",
        "25: z"
      ],
      "active": [],
      "kind": "matrix",
      "columns": 8,
      "output": [],
      "result": 0
    }
  2. Step 2: Decode phrase and grow the dictionary.

    State at this checkpoint
    {
      "values": [
        "Read: 0,1",
        "Pending: b",
        "Output: ab",
        "0: a",
        "1: b",
        "2: c",
        "3: d",
        "4: e",
        "5: f",
        "6: g",
        "7: h",
        "8: i",
        "9: j",
        "10: k",
        "11: l",
        "12: m",
        "13: n",
        "14: o",
        "15: p",
        "16: q",
        "17: r",
        "18: s",
        "19: t",
        "20: u",
        "21: v",
        "22: w",
        "23: x",
        "24: y",
        "25: z",
        "26: ab"
      ],
      "active": [
        4
      ],
      "kind": "matrix",
      "columns": 8,
      "output": [
        97,
        98
      ],
      "result": 2
    }
  3. Step 4: Decode the next-code special case and grow the dictionary.

    State at this checkpoint
    {
      "values": [
        "Read: 0,1,26,28",
        "Pending: aba",
        "Output: abababa",
        "0: a",
        "1: b",
        "2: c",
        "3: d",
        "4: e",
        "5: f",
        "6: g",
        "7: h",
        "8: i",
        "9: j",
        "10: k",
        "11: l",
        "12: m",
        "13: n",
        "14: o",
        "15: p",
        "16: q",
        "17: r",
        "18: s",
        "19: t",
        "20: u",
        "21: v",
        "22: w",
        "23: x",
        "24: y",
        "25: z",
        "26: ab",
        "27: ba",
        "28: aba"
      ],
      "active": [
        31
      ],
      "kind": "matrix",
      "columns": 8,
      "output": [
        97,
        98,
        97,
        98,
        97,
        98,
        97
      ],
      "result": 7
    }
  4. Step 5: Decode phrase and grow the dictionary.

    State at this checkpoint
    {
      "values": [
        "Read: 0,1,26,28,27",
        "Pending: ba",
        "Output: ababababa",
        "0: a",
        "1: b",
        "2: c",
        "3: d",
        "4: e",
        "5: f",
        "6: g",
        "7: h",
        "8: i",
        "9: j",
        "10: k",
        "11: l",
        "12: m",
        "13: n",
        "14: o",
        "15: p",
        "16: q",
        "17: r",
        "18: s",
        "19: t",
        "20: u",
        "21: v",
        "22: w",
        "23: x",
        "24: y",
        "25: z",
        "26: ab",
        "27: ba",
        "28: aba",
        "29: abab"
      ],
      "active": [
        30
      ],
      "kind": "matrix",
      "columns": 8,
      "output": [
        97,
        98,
        97,
        98,
        97,
        98,
        97,
        98,
        97
      ],
      "result": 9
    }
  5. Step 7: Decoded abababababa.

    State at this checkpoint
    {
      "values": [
        "Read: 0,1,26,28,27,27",
        "Pending: ",
        "Output: abababababa",
        "0: a",
        "1: b",
        "2: c",
        "3: d",
        "4: e",
        "5: f",
        "6: g",
        "7: h",
        "8: i",
        "9: j",
        "10: k",
        "11: l",
        "12: m",
        "13: n",
        "14: o",
        "15: p",
        "16: q",
        "17: r",
        "18: s",
        "19: t",
        "20: u",
        "21: v",
        "22: w",
        "23: x",
        "24: y",
        "25: z",
        "26: ab",
        "27: ba",
        "28: aba",
        "29: abab",
        "30: bab"
      ],
      "active": [],
      "kind": "matrix",
      "columns": 8,
      "output": [
        97,
        98,
        97,
        98,
        97,
        98,
        97,
        98,
        97,
        98,
        97
      ],
      "result": 11
    }

Expected final state

Decoded abababababa.

Complexity and input bounds

Family: Strings. Time complexity: O(n + decoded length) with prefix chains.

Implementation detail: The initial dictionary is a..z codes 0..25. Streams have at most 24 codes and expand to at most 24 letters. Invalid codes and expansion overflow return -1 in downloads; output is unspecified on error.

Space complexity: O(code count + decoded length) auxiliary storage and output for portable prefix chains, plus saved frames.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

1..24 comma-separated codes; initial a..z codes 0..25. At most 24 decoded letters. Invalid codes are rejected.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

The code-equals-next-entry case is valid; a larger code is invalid. The first code must be a literal. Bound the expanded length as well as the number of codes.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// Integer LZW codes n 0..24 with initial dictionary a..z codes 0..25, no control codes or bit packing. First code must be a literal. Handles the special code equal to next dictionary entry; larger or negative codes return -1. Output capacity at least 24. Returns decoded length or -1 if malformed or expanded text exceeds 24 letters; output unspecified on error. Prefix-chain portable decoding uses O(n + decoded length) time and O(n + decoded length) scratch. Empty input returns 0. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(codes, n, output) {
    if (n < 0 || n > 24) { return -1; }
    if (n == 0) { return 0; }
    if (codes[0] < 0 || codes[0] >= 26) { return -1; }
    let prefix = Array(256).fill(0); let suffix = Array(256).fill(0); let stack = Array(256).fill(0); let size = 26; let previous = codes[0]; let first = previous+97; let count = 1; let code = 0; let original = 0; let top = 0;
    output[0] = first;
    for (let i = 1; i < n; i++) { code = codes[i]; original = code; top = 0; if (code < 0 || code > size) { return -1; } if (code == size) { stack[top] = first; top++; code = previous; }
     while (code >= 26) { stack[top] = suffix[code]; top++; code = prefix[code]; }
     stack[top] = code+97; top++; first = stack[top-1]; if (count+top > 24) { return -1; }
     while (top > 0) { top--; output[count] = stack[top]; count++; }
     prefix[size] = previous; suffix[size] = first; size++; previous = original;
    }
    return count;
}

Source

Primary Welch research for LZW. The bounded playground uses a 26-letter initial alphabet and integer codes, omitting file framing and bit packing.