Using codes for variable-length phrases
The dictionary begins with permitted single symbols. The encoder outputs the code for the longest dictionary prefix of remaining input, then adds that phrase followed by the next character as a future entry.
Rather than assigning shorter codes to frequent individual symbols, it grows reusable multi-symbol phrases. Dictionary contents depend on input already processed, allowing later phrase occurrences to use one code.
References: [1]
Rebuilding the dictionary while decoding
The decoder starts with the same initial symbols, expands codes, and adds the preceding phrase followed by the first character of the current phrase. It reconstructs the dictionary without receiving the complete final table separately.
A special case occurs when a code denotes the entry the decoder is just about to create. Princeton reconstructs it as the preceding phrase plus its own first character before continuing, rather than rejecting every not-yet-entered code as corruption.
References: [1]
Code widths and full-dictionary policies
Princeton’s teaching version uses 12-bit codes and 4096 slots, stops adding when full, and reserves an end code. Other formats can grow widths or reset dictionaries, but both sides must implement the same policy.
Savings depend on repeated phrases and code overhead; runtime also depends on lookup and representation. The Java example explicitly warns that repeatedly copying remaining substrings produces quadratic compression time. The design idea does not erase allocation costs in a concrete implementation.