LZW Dictionary Compression

Greedy Longest-Prefix Parsing

Both encoder and decoder begin with the same initial alphabet table: A = 0, B = 1, and C = 2, with new phrase codes assigned sequentially starting at 3. Because the encoder only emits existing codes and extends the dictionary by one lookahead character at each boundary, the decoder can reconstruct the exact same dictionary on the fly without transmitting the table.

The KwKwK Decoder Special Case

During decoding, each received code usually indexes a phrase already present in the decoder dictionary. However, when the input contains an immediately overlapping pattern of the form K + w + K + w + K, the encoder emits the newly created code for K + w + K on the very next step before the decoder has finished inserting it. Whenever the incoming code equals the current decoder dictionary size, the phrase must begin and end with the first character of the previous phrase, so the decoder outputs previous + first(previous).

Worked Example

Trace the encoding and decoding of ABABABA with initial dictionary A = 0, B = 1, C = 2:

1. Match A, lookahead B: Phrase AB is absent. Emit 0 (for A), insert AB = 3, set w = B.
2. Match B, lookahead A: Phrase BA is absent. Emit 1 (for B), insert BA = 4, set w = A.
3. Match AB, lookahead A: Phrase AB is present (code 3), but ABA is absent. Emit 3 (for AB), insert ABA = 5, set w = A.
4. Match ABA, end of input: Remaining suffix ABA matches code 5. Emit final code 5.
5. Decoding [0, 1, 3, 5]: Code 0 decodes to A; code 1 decodes to B (adds AB = 3); code 3 decodes to AB (adds BA = 4). When code 5 arrives, dictionary size is 5, triggering previous + first(previous) = AB + A = ABA.

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.

Limitations

This educational module restricts the alphabet to uppercase A, B, C (up to 12 characters) and emits raw integer codes. Production formats such as GIF or Unix compress pack codes into variable-width bit streams and reserve control codes for dictionary reset (CLEAR) and end-of-stream (EOS).

Common Pitfalls

Omitting the code == dict.length branch in an LZW decoder causes immediate decompression failure on repetitive runs like ABABABA or AAAAAAAAAAAA.

References

The LZW dictionary construction and KwKwK decoding rule follow standard compression specifications:

• W3C GIF89a Specification, Appendix F: Variable-Length-Code LZW Compression