LZW dictionary encoding: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Extend the longest known phrase; emit its code and add the phrase plus the next character to the dictionary.

Start with one dictionary entry for each lowercase letter. Extend the current phrase while it remains in the dictionary; otherwise emit its code, add the extended phrase, and start a new phrase at the current letter.

Open the 3D visualization

LZW dictionary encoding 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 encoding

Learning adaptive dictionary coding without sending a separate frequency table.

Choosing an alternative

Huffman assigns variable-length bit codes using symbol frequencies. LZW creates codes for repeated multi-character phrases as it reads.

Worked example: input and state changes

Example input

abababababa

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 3: Emit 1 and add 27: ba.

    State at this checkpoint
    {
      "values": [
        "Read: aba",
        "Pending: b",
        "Output: 0,1",
        "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"
      ],
      "active": [
        30
      ],
      "kind": "matrix",
      "columns": 8,
      "output": [
        0,
        1
      ],
      "result": 2
    }
  3. Step 6: Extend the current dictionary phrase.

    State at this checkpoint
    {
      "values": [
        "Read: ababab",
        "Pending: ab",
        "Output: 0,1,26",
        "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": [
        29
      ],
      "kind": "matrix",
      "columns": 8,
      "output": [
        0,
        1,
        26
      ],
      "result": 3
    }
  4. Step 9: Extend the current dictionary phrase.

    State at this checkpoint
    {
      "values": [
        "Read: ababababa",
        "Pending: ba",
        "Output: 0,1,26,28",
        "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": [
        0,
        1,
        26,
        28
      ],
      "result": 4
    }
  5. Step 12: Emit the final phrase.

    State at this checkpoint
    {
      "values": [
        "Read: abababababa",
        "Pending: ",
        "Output: 0,1,26,28,27,27",
        "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": [
        0,
        1,
        26,
        28,
        27,
        27
      ],
      "result": 6
    }

Expected final state

Emit the final phrase.

Complexity and input bounds

Family: Strings. Time complexity: O(n^2) bounded dictionary scan.

Implementation detail: The teaching dictionary starts at a..z codes 0..25 and accepts at most 24 letters. No clear/end codes, code-width growth or bit packing are implemented; this stream is not GIF, TIFF or Unix compress format.

Space complexity: O(n) prefix/suffix dictionary storage in portable versions; Python string keys can use O(n^2), plus output and recorded 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 lowercase letters. Initial dictionary a..z has codes 0..25; outputs are integer codes, not a packed file.

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

Emit the final pending phrase. Encoder and decoder must start with the identical alphabet and allocate new codes in the same order. Integer-code count alone does not describe packed-file size.

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
// Lowercase ASCII integer codes 97..122, n 0..24. Initial dictionary a..z has codes 0..25; no clear/end codes or bit packing. Output capacity n; returns number of integer codes written. Empty input returns 0. Portable versions store phrase prefix/suffix pairs and scan the bounded dictionary, O(n^2) time, O(n) scratch. Python uses a string dictionary. Teaching code stream, not GIF/TIFF/compress file compatibility. 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(text, n, output) {
    if (n == 0) { return 0; }
    let prefix = Array(256).fill(0); let suffix = Array(256).fill(0); let size = 26; let phrase = text[0]-97; let found = -1; let count = 0;
    for (let i = 1; i < n; i++) { found = -1; for (let code = 26; code < size; code++) { if (prefix[code] == phrase && suffix[code] == text[i]) { found = code; break; } } if (found != -1) { phrase = found; } else { output[count] = phrase; count++; prefix[size] = phrase; suffix[size] = text[i]; size++; phrase = text[i]-97; } }
    output[count] = phrase; count++; 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.