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.
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.
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 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 }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 }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 }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:
- 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 | // 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.
- A Technique for High-Performance Data Compression
Terry A. Welch (1984). Original LZW research paper.