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.
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.
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 }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 }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 }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 }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:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
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.
- A Technique for High-Performance Data Compression
Terry A. Welch (1984). Original LZW research paper.