LZW Compression

Introduction

Imagine reading a book and keeping a notepad. Every time you meet a phrase you haven't seen before, you jot it down and assign it a number. The next time that phrase appears you write only the number. By the end of the book, your notepad might hold thousands of phrases — and your compressed copy is just a list of numbers pointing into it.

That is exactly how LZW (Lempel–Ziv–Welch) works. Abraham Lempel and Jacob Ziv laid the foundations in their landmark 1977–78 papers on universal compression. Terry Welch refined the idea in 1984 into the practical scheme now named after all three. The trick: encoder and decoder build the same dictionary independently, so the dictionary never needs to be transmitted — only the codes.

LZW became famous as the algorithm inside the GIF image format (1987), TIFF files, and the Unix compress utility. It is lossless — the original data can be recovered bit-for-bit — and it is proven to be asymptotically optimal for any stationary ergodic source, meaning it squeezes as hard as the fundamental limits of information theory allow, given enough data.

Understanding LZW means understanding two beautiful ideas at once: how to exploit repetition without knowing anything about the data in advance, and why a dictionary that nobody transmits can still be shared perfectly between sender and receiver.

Try It

Type anything in the box below — or keep the default — and watch LZW process it character by character. The table shows every dictionary entry the algorithm adds, the code it emits for each match, and the running compression ratio.

<div class="controls">
  <label for="inputText">Input text:</label>
  <textarea id="inputText" rows="2" spellcheck="false">ABABABABAB</textarea>
  <button id="runBtn" type="button">Compress</button>
  <button id="clearBtn" type="button" class="ghost">Reset</button>
</div>
<div id="stats" class="stats hidden"></div>
<div class="table-wrap">
  <table id="dictTable">
    <thead><tr><th>Step</th><th>Matched phrase</th><th>Code emitted</th><th>New entry</th><th>Ratio so far</th></tr></thead>
    <tbody id="dictBody"></tbody>
  </table>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; flex-wrap: wrap; align-items: flex-end; gap: .5rem; margin-bottom: .6rem; }
label { font-weight: 600; font-size: .85rem; margin-bottom: .15rem; display: block; }
textarea { flex: 1 1 180px; min-width: 120px; padding: .4rem .55rem; border: 1px solid #bcc4cc;
           border-radius: 7px; font: 14px ui-monospace, monospace; resize: none; line-height: 1.35; }
button { font: 600 13px system-ui, sans-serif; padding: .42rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; white-space: nowrap; }
button.ghost { background: #fff; color: #1d3557; }
.stats { background: #e9f0f7; border-radius: 7px; padding: .45rem .75rem; margin-bottom: .55rem;
         font-size: .88rem; display: flex; flex-wrap: wrap; gap: .4rem 1.2rem; }
.stats span { color: #1d3557; font-weight: 600; }
.hidden { display: none; }
.table-wrap { overflow-x: auto; max-height: 260px; overflow-y: auto; border: 1px solid #d6dde4; border-radius: 8px; }
table { border-collapse: collapse; width: 100%; font-size: .82rem; }
thead th { position: sticky; top: 0; background: #1d3557; color: #fff; padding: .4rem .65rem;
           text-align: left; font-weight: 600; white-space: nowrap; }
tbody tr:nth-child(even) { background: #f4f7fa; }
tbody tr:hover { background: #dde8f2; }
td { padding: .32rem .65rem; border-bottom: 1px solid #e5eaef; font-family: ui-monospace, monospace; }
td.ratio { color: #0a7d33; font-weight: 600; }
td.ratio.worse { color: #c92f3c; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// LZW encoder: standard algorithm (Welch 1984).
// Initial dictionary = all single chars in the input alphabet (codes 0..k-1).
// On each step: find the longest match W in the dictionary, emit code(W),
// add W + next_char as a new entry, advance past W.
function lzwEncode(input) {
  if (!input.length) return { steps: [], dictSize: 0, outputBits: 0, inputBits: 0 };

  // Build initial dictionary from unique chars in input
  const chars = [...new Set(input.split(''))].sort();
  const dict = {};
  chars.forEach((c, i) => { dict[c] = i; });
  let nextCode = chars.length;

  const steps = [];
  let i = 0;
  let bitsNeeded = (n) => Math.max(1, Math.ceil(Math.log2(n + 1)));

  while (i < input.length) {
    let W = input[i];
    // extend W as far as possible while W is in the dictionary
    while (i + W.length < input.length && dict[W + input[i + W.length]] !== undefined) {
      W = W + input[i + W.length];
    }
    const code = dict[W];
    const nextChar = input[i + W.length] || null;
    const newEntry = nextChar !== null ? W + nextChar : null;
    const dictSizeNow = nextCode;
    // bits: ceil(log2(dictSize)) per code
    const bits = bitsNeeded(dictSizeNow);
    const ratio = ((i + W.length) / (steps.reduce((a, s) => a + s.bits, 0) + bits) * (bits / 8)).toFixed(3);

    steps.push({ step: steps.length + 1, phrase: W, code, newEntry, dictSizeNow, bits });

    if (newEntry !== null) {
      dict[newEntry] = nextCode++;
    }
    i += W.length;
  }

  // Compute overall ratio: input chars (8 bits each) vs output (variable bits per code)
  const inputBits = input.length * 8;
  let bitPos = 0;
  steps.forEach(s => { bitPos += s.bits; });
  return { steps, dictSize: nextCode, outputBits: bitPos, inputBits };
}

function run() {
  const input = document.getElementById('inputText').value;
  if (!input.trim()) return;
  const result = lzwEncode(input);
  const tbody = document.getElementById('dictBody');
  tbody.innerHTML = '';

  let cumBits = 0;
  result.steps.forEach(s => {
    cumBits += s.bits;
    const cumBytes = cumBits / 8;
    const origBytes = /* chars processed so far */ (function() {
      let pos = 0;
      for (let j = 0; j < s.step; j++) pos += result.steps[j - 1] ? result.steps[j-1].phrase.length : 0;
      pos += s.phrase.length;
      return pos;
    })();
    const ratio = (origBytes / cumBytes).toFixed(2);
    const tr = document.createElement('tr');
    const ratioCell = parseFloat(ratio) >= 1 ? 'ratio' : 'ratio worse';
    tr.innerHTML = `<td>${s.step}</td><td>${esc(s.phrase)}</td><td>${s.code}</td><td>${s.newEntry ? esc(s.newEntry) : '—'}</td><td class="${ratioCell}">${ratio}×</td>`;
    tbody.appendChild(tr);
  });

  const overallRatio = result.inputBits > 0
    ? (result.inputBits / result.outputBits).toFixed(2)
    : '—';
  const statsEl = document.getElementById('stats');
  statsEl.classList.remove('hidden');
  statsEl.innerHTML =
    fmt('Input: <span>%length% chars / %inputBits% bits</span> &nbsp;Output: <span>%outputBits% bits (%v% bytes)</span> &nbsp;Dictionary entries: <span>%dictSize%</span> &nbsp;Overall ratio: <span>%overallRatio%×</span>', { length: input.length, inputBits: result.inputBits, outputBits: result.outputBits, v: (result.outputBits/8).toFixed(1), dictSize: result.dictSize, overallRatio: overallRatio });

  console.log('LZW result:', { inputLen: input.length, dictSize: result.dictSize, outputBits: result.outputBits, ratio: overallRatio });
}

function esc(s) {
  return s.replace(/&/g,'&amp;').replace(/</g,'&lt;').replace(/>/g,'&gt;');
}

document.getElementById('runBtn').addEventListener('click', run);
document.getElementById('clearBtn').addEventListener('click', () => {
  document.getElementById('inputText').value = 'ABABABABAB';
  document.getElementById('dictBody').innerHTML = '';
  document.getElementById('stats').classList.add('hidden');
});
// Run on load
run();

<div class="controls">
  <label for="inputText">Input text:</label>
  <textarea id="inputText" rows="2" spellcheck="false">ABABABABAB</textarea>
  <button id="runBtn" type="button">Compress</button>
  <button id="clearBtn" type="button" class="ghost">Reset</button>
</div>
<div id="stats" class="stats hidden"></div>
<div class="table-wrap">
  <table id="dictTable">
    <thead><tr><th>Step</th><th>Matched phrase</th><th>Code emitted</th><th>New entry</th><th>Ratio so far</th></tr></thead>
    <tbody id="dictBody"></tbody>
  </table>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; flex-wrap: wrap; align-items: flex-end; gap: .5rem; margin-bottom: .6rem; }
label { font-weight: 600; font-size: .85rem; margin-bottom: .15rem; display: block; }
textarea { flex: 1 1 180px; min-width: 120px; padding: .4rem .55rem; border: 1px solid #bcc4cc;
           border-radius: 7px; font: 14px ui-monospace, monospace; resize: none; line-height: 1.35; }
button { font: 600 13px system-ui, sans-serif; padding: .42rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; white-space: nowrap; }
button.ghost { background: #fff; color: #1d3557; }
.stats { background: #e9f0f7; border-radius: 7px; padding: .45rem .75rem; margin-bottom: .55rem;
         font-size: .88rem; display: flex; flex-wrap: wrap; gap: .4rem 1.2rem; }
.stats span { color: #1d3557; font-weight: 600; }
.hidden { display: none; }
.table-wrap { overflow-x: auto; max-height: 260px; overflow-y: auto; border: 1px solid #d6dde4; border-radius: 8px; }
table { border-collapse: collapse; width: 100%; font-size: .82rem; }
thead th { position: sticky; top: 0; background: #1d3557; color: #fff; padding: .4rem .65rem;
           text-align: left; font-weight: 600; white-space: nowrap; }
tbody tr:nth-child(even) { background: #f4f7fa; }
tbody tr:hover { background: #dde8f2; }
td { padding: .32rem .65rem; border-bottom: 1px solid #e5eaef; font-family: ui-monospace, monospace; }
td.ratio { color: #0a7d33; font-weight: 600; }
td.ratio.worse { color: #c92f3c; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// LZW encoder: standard algorithm (Welch 1984).
// Initial dictionary = all single chars in the input alphabet (codes 0..k-1).
// On each step: find the longest match W in the dictionary, emit code(W),
// add W + next_char as a new entry, advance past W.
function lzwEncode(input) {
  if (!input.length) return { steps: [], dictSize: 0, outputBits: 0, inputBits: 0 };

  // Build initial dictionary from unique chars in input
  const chars = [...new Set(input.split(''))].sort();
  const dict = {};
  chars.forEach((c, i) => { dict[c] = i; });
  let nextCode = chars.length;

  const steps = [];
  let i = 0;
  let bitsNeeded = (n) => Math.max(1, Math.ceil(Math.log2(n + 1)));

  while (i < input.length) {
    let W = input[i];
    // extend W as far as possible while W is in the dictionary
    while (i + W.length < input.length && dict[W + input[i + W.length]] !== undefined) {
      W = W + input[i + W.length];
    }
    const code = dict[W];
    const nextChar = input[i + W.length] || null;
    const newEntry = nextChar !== null ? W + nextChar : null;
    const dictSizeNow = nextCode;
    // bits: ceil(log2(dictSize)) per code
    const bits = bitsNeeded(dictSizeNow);
    const ratio = ((i + W.length) / (steps.reduce((a, s) => a + s.bits, 0) + bits) * (bits / 8)).toFixed(3);

    steps.push({ step: steps.length + 1, phrase: W, code, newEntry, dictSizeNow, bits });

    if (newEntry !== null) {
      dict[newEntry] = nextCode++;
    }
    i += W.length;
  }

  // Compute overall ratio: input chars (8 bits each) vs output (variable bits per code)
  const inputBits = input.length * 8;
  let bitPos = 0;
  steps.forEach(s => { bitPos += s.bits; });
  return { steps, dictSize: nextCode, outputBits: bitPos, inputBits };
}

function run() {
  const input = document.getElementById('inputText').value;
  if (!input.trim()) return;
  const result = lzwEncode(input);
  const tbody = document.getElementById('dictBody');
  tbody.innerHTML = '';

  let cumBits = 0;
  result.steps.forEach(s => {
    cumBits += s.bits;
    const cumBytes = cumBits / 8;
    const origBytes = /* chars processed so far */ (function() {
      let pos = 0;
      for (let j = 0; j < s.step; j++) pos += result.steps[j - 1] ? result.steps[j-1].phrase.length : 0;
      pos += s.phrase.length;
      return pos;
    })();
    const ratio = (origBytes / cumBytes).toFixed(2);
    const tr = document.createElement('tr');
    const ratioCell = parseFloat(ratio) >= 1 ? 'ratio' : 'ratio worse';
    tr.innerHTML = `<td>${s.step}</td><td>${esc(s.phrase)}</td><td>${s.code}</td><td>${s.newEntry ? esc(s.newEntry) : '—'}</td><td class="${ratioCell}">${ratio}×</td>`;
    tbody.appendChild(tr);
  });

  const overallRatio = result.inputBits > 0
    ? (result.inputBits / result.outputBits).toFixed(2)
    : '—';
  const statsEl = document.getElementById('stats');
  statsEl.classList.remove('hidden');
  statsEl.innerHTML =
    fmt('Input: <span>%length% chars / %inputBits% bits</span> &nbsp;Output: <span>%outputBits% bits (%v% bytes)</span> &nbsp;Dictionary entries: <span>%dictSize%</span> &nbsp;Overall ratio: <span>%overallRatio%×</span>', { length: input.length, inputBits: result.inputBits, outputBits: result.outputBits, v: (result.outputBits/8).toFixed(1), dictSize: result.dictSize, overallRatio: overallRatio });

  console.log('LZW result:', { inputLen: input.length, dictSize: result.dictSize, outputBits: result.outputBits, ratio: overallRatio });
}

function esc(s) {
  return s.replace(/&/g,'&amp;').replace(/</g,'&lt;').replace(/>/g,'&gt;');
}

document.getElementById('runBtn').addEventListener('click', run);
document.getElementById('clearBtn').addEventListener('click', () => {
  document.getElementById('inputText').value = 'ABABABABAB';
  document.getElementById('dictBody').innerHTML = '';
  document.getElementById('stats').classList.add('hidden');
});
// Run on load
run();

Result

Console

Notice how the first pass through unique characters adds many entries quickly, but once the algorithm has seen a phrase before it starts emitting single codes for multi-character strings. Heavy repetition — like "ABABAB…" — produces dramatic compression. Random text with few repeated patterns barely shrinks at all.

The Real Complexity

LZW sits in a sweet spot that is rare in algorithm design: it is simultaneously simple, fast, and provably near-optimal.

Time complexity: $O(n)$ . Encoding and decoding each walk the input once, doing $O(1)$ dictionary work per symbol via a hash table. There is no heavy preprocessing and no search over candidates.
Asymptotic optimality. Ziv and Lempel proved that LZ78 (LZW's parent) approaches the entropy rate of any stationary ergodic source as the input grows. In the limit, no compressor can do better on average — this is a consequence of Shannon's source-coding theorem.
Fixed-width code limit. Classic LZW uses codes of a fixed bit-width (typically 12 bits → 4096 dictionary entries). Once the table fills, many implementations freeze it, which can hurt performance on very long or varied inputs. Modern variants clear and restart the dictionary when it fills.
The patent era. Unisys held a patent on LZW until 2003–2004, which made GIF legally complicated for open-source software and accelerated development of the patent-free compression alternative PNG (which uses DEFLATE, combining LZ77 with Huffman coding).
Versus arithmetic coding. LZW is word-based (whole codes per phrase), while arithmetic coding works at the bit level and can approach entropy more tightly. For text and structured data, modern compressors like zstd and brotli combine LZ-family sliding-window matching with entropy coders, pushing past what LZW can achieve alone.

The fundamental lesson: LZW is theoretically tight and practically fast, but "asymptotically optimal" means it reaches its ceiling only on long inputs — short or highly varied data may compress poorly, and newer hybrids do better in practice.

Where It Matters

LZW was one of the first compression algorithms to leave academia and land directly in millions of everyday files:

GIF (1987): LZW is the compression layer inside every GIF image and animation. The pixel sequences of cartoon-style art with flat colors repeat heavily, giving LZW excellent ratios. Unisys's patent saga later pushed image authors toward PNG.
TIFF files: The TIFF format includes LZW as one of its optional compression schemes, common for scanned documents where runs of the same color dominate.
PDF internal streams: PDF uses LZWDecode and FlateDecode filters on embedded streams; older PDFs lean on LZW.
Unix compress / .Z files: The original Unix compression tool used LZW with 16-bit codes, making it the default archive format on Unix workstations through the 1980s and early 90s.
Modems and early networking: V.42bis, the modem compression standard used over dial-up links, is based on a variant of LZW, letting modems squeeze data in hardware at high speed.
Teaching ground: Because LZW is so transparent — you can trace every dictionary entry by hand — it is the canonical teaching example for dictionary-based compression and for understanding why LZ77/LZ78, DEFLATE, zlib, gzip, and their successors work the way they do. Once you understand LZW, the optimal compression limits and the design of modern codecs click into place.

Conclusion

LZW is a masterpiece of economy. It reads your data once, builds a dictionary neither side ever explicitly sends, and proves — in the limit — that repetition alone is enough to reach the theoretical floor set by Shannon's entropy. All of that in $O(n)$ time.

Its history is equally instructive: the same patent system that locked away GIF for a decade inadvertently launched PNG, and the same asymptotic-optimality result that crowns LZW also shows its ceiling — modern compressors like zstd and brotli push past it by layering LZ matching with arithmetic coding.

The next time you open a GIF or unzip a legacy .Z file, remember: a tiny self-building dictionary, a rule that encoder and decoder follow in lock-step, and the unstoppable power of repetition are behind it all. For a deeper look at what limits any compressor, see our article on optimal compression.

Comments

Loading comments...

https://www.kipuhub.com/en/article/lzw/Content licensed under CC BY-NC 4.0.

Cookies & privacy

A dictionary that writes itself — one repeated pattern at a time