Dictionary Coding Checkpoint

LZ77 and LZW rules, overlaps, and dictionary growth.

1. An LZ77 match token is:

(distance, length) (length, next-byte) (symbol, probability) (code, checksum)

2. LZ77 distances refer to:

Bytes back from current output position Bytes forward in the input Absolute indices in the file Huffman code lengths

3. Overlapping matches in LZ77 are:

Allowed Forbidden Undefined Always invalid

4. LZW starts with a dictionary containing:

All single-byte strings Only the empty string All bigrams Only ASCII letters

5. The KwKwK case occurs when:

A code refers to the entry being defined A code is zero The dictionary is empty A distance is negative

6. When the LZW dictionary is full, the encoder should:

Stop adding new entries Reset the dictionary to empty Error out immediately Reverse the dictionary

7. Greedy longest match can be suboptimal because:

The encoding cost of length/distance may outweigh the gain It violates Kraft's inequality It changes entropy It is always optimal

Auto-advance on pass