Dictionary coding: synchronize the history

LZ77 sends references to already decoded output. LZW sends indices into a phrase table that both sides construct. Both exploit repetition, but the decoder states and synchronization rules differ.

Trace an overlapping LZ77 match

Encode ABABABA with a window at least two and lookahead at least five. At positions 0 and 1 no three-byte match exists, so emit literals A and B. At position 2, distance two matches five bytes: ABABA. Emit (distance=2,length=5) and advance to the end.

The decoder starts with AB. For every copied byte compute index=len(output)-distance again:

Copy	Source index	Byte	Output afterward
1	0	A	ABA
2	1	B	ABAB
3	2	A	ABABA
4	3	B	ABABAB
5	4	A	ABABABA

Copies three through five read bytes created by this same match. Copying an old fixed slice of five bytes is impossible because only two bytes existed when the match began. A single bulk-copy operation with a source truncated to old output also fails to fill all five positions. This forward, byte-at-a-time dependency is why overlap is legal. RFC 1951 section 3.2.3 describes overlapping backward references in DEFLATE; this exercise uses smaller configurable bounds.

At input position i, consider distances 1..min(window,i) and compare at most min(lookahead,n-i) bytes. The original input lets the encoder compare data[i+k] with data[i-distance+k] even when the latter reaches i: equality describes exactly the periodic copy the decoder will perform. Choose longest length, then smallest distance. Emit a match only at length at least three. Nonpositive window or lookahead gives all literals.

This naive search costs O(nwindowlookahead) in the worst case and needs no explicit dictionary beyond input/history. Longest matching is this exercise's deterministic parse rule; it is not a proof of minimum encoded bit cost. The standalone decoder assumes valid tokens, while the capstone's error-returning decoder validates distance and stream structure.

Build the LZW dictionary on both sides

Initialize byte strings 0..255 at their byte-valued codes; the next code is 256. Let w be the current phrase. For each next byte k:

if w+k is in dictionary: w = w+k
else: emit code(w); add w+k if room; w = k
at end: emit code(w), if nonempty

For ABABABA, the emitted codes are [65,66,256,258]:

Failed extension / finish	Emit	New entry
A+B absent	65 (A)	256=AB
B+A absent	66 (B)	257=BA
AB+A absent	256 (AB)	258=ABA
End with ABA	258 (ABA)	none

The decoder outputs the first code's phrase, then processes each subsequent code. After resolving the new phrase entry, it adds previous + first(entry) and sets previous=entry. Decode the example:

Code	Entry	Added dictionary entry	Output
65	A	none	A
66	B	256=AB	AB
256	AB	257=BA	ABAB
258	not yet present	258=ABA	ABABABA

Derive the missing-entry case

Before reading 258, the decoder knows previous=AB and nextCode=258. The encoder could already have emitted the entry the decoder is about to create. That entry must be previous + first(previous), hence ABA. This is the KwKwK case. The exception applies only when the incoming code equals nextCode; arbitrary larger unknown codes are not justified by the derivation.

Both sides stop adding at dictionary size 4096, while continuing to emit/decode existing entries. Neither resets the dictionary silently. This exercise returns integer codes, so variable-width bit packing and clear/end codes are outside its interface. Do not infer GIF compatibility from the name LZW.

Reconstruct and diagnose

1. Decode literals X,Y then match (2,4).
2. Decode LZW [90,256] from a fresh byte dictionary.
3. Two three-byte matches have distances 4 and 9. Which does this encoder choose?
4. Why must a decoder freeze additions at the same capacity as its encoder?

Model answers

1. XYXYXY; bytes copied later may refer to bytes copied earlier.
2. First output Z; code 256 equals nextCode, so entry=ZZ. Output is ZZZ.
3. Distance 4, by the explicit smallest-distance tie rule.
4. Different additions change which phrase a later code denotes; a round trip can break long after the first disagreement.

Implement LZ77 Lite and LZW Coding, checking these independently derived tokens before broad round trips.