Compress by building a dictionary of phrases as you read — no table shipped ahead. Emit each phrase as a pair: the index of the longest known prefix, plus the next character; then add that new phrase to the table. The decoder replays the exact same growth. Welch’s tuned descendant (LZW) became the patent that nearly killed the GIF.
THE TECHNIQUE a trie that grows on itself
Scan the input; take the longest prefix already in the dictionary (index i), read the next char c, emit (i, c), and add “that phrase + c” as a new numbered entry. The decoder does the same construction from the tokens, so no dictionary is ever transmitted. Type a string and watch the tokens and dictionary build. live demo
HISTORY & CREDIT the idea is Ziv-Lempel’s; the patent was Welch’s
“Welch invented dictionary compression” — he invented tuned Ziv & Lempel’s LZ78 (1978); LZW is a refinement, not the idea. cited
1977 / 1978 · Jacob Ziv & Abraham Lempel publish LZ77 (sliding window → zip, gzip, PNG) then LZ78 (the explicit phrase dictionary). Note: Ziv is first author, yet the eponym flips to “Lempel-Ziv.” 1983 / 1984 · Terry Welch (Sperry) files a patent and publishes LZW — pre-load every single char, emit one index per phrase — without disclosing the pending patent. (IBM’s Miller-Wegman filing beat his by 19 days.) 1987 / 1994 · CompuServe ships GIF using LZW, believing it free; then Unisys (which inherited the patent) demands licensing — the holiday-timed “GIF tax.” 1996 / 2003 · PNG is designed patent-free (it uses LZ77+Huffman, not LZW); the LZW patent finally expires 2003.
Ziv won the Shannon Award (1997) and the IEEE Medal of Honor (2021); Lempel the IEEE Hamming Medal (2007) — both honoured, while “LZW” and the GIF drama overshadow them. Ziv & Lempel, 1978
RECOMMEND FOR I-13 indices run; the dictionary is the string wall
The index arithmetic and the emit/decode loop run on arrays — and the round-trip is exact:
Recommend: the numeric spine runs — the dictionary can be a trie in parallel arrays (a parent-index array + an edge-char array as f64 code points), and matching / appending / emitting (index, char) tokens are bounded-array bookkeeping (verified round-trip above). The wall is the standing one: the dictionary holds growing strings (the aggregate/string want, with Boyer-Moore-061, KMP-063, BWT-065, the trie-074). Note: token 4 = (3,A) reuses entry 3, itself built one step earlier — the trie growing on itself is the whole idea, and it is the pointerless node-arena shape the corpus already uses.