LZW Dictionary Compression

Lempel–Ziv–Welch (LZW) is a lossless dictionary compression algorithm that parses input text greedily into the longest recognized phrase w, emits its numeric code, and appends w + k (where k is the next lookahead character) as a new dictionary entry.

Experiment

Compare regular dictionary growth with the KwKwK special branch in https://riano.app/module/lzw-compression:

1. Use default input ABABABA and press Step four times to watch codes 0, 1, 3, 5 emit and observe Decoder special case used switch to true on the final step.
2. Enter ABCABCABCA and press Finish to verify emitted codes 0, 1, 2, 3, 5, 4, 0 where every phrase is already in the decoder table (special case false).
3. Enter the 12-symbol constant run AAAAAAAAAAAA and press Finish to see phrase lengths grow from 1 to 4 with codes 0, 3, 4, 5, 3.